非确定性图灵机

在非确定性图灵机中，对于每个状态和符号，图灵机都有一组可以执行的操作。因此，这里的转换不是确定性的。非确定性图灵机的计算是一个从起始配置可以到达的配置树。

如果树中至少有一个节点是接受配置，则接受输入，否则不接受。如果计算树的所有分支在所有输入上都停止，则非确定性图灵机称为**判定器**，如果对于某些输入，所有分支都被拒绝，则该输入也被拒绝。

非确定性图灵机可以正式定义为一个 6 元组 (Q, X, ∑, δ, q₀, B, F)，其中 -

• Q 是一个有限的状态集

• X 是带字母表

• ∑ 是输入字母表

• δ 是一个转移函数；

  δ : Q × X → P(Q × X × {左移, 右移}).

• q₀ 是初始状态

• B 是空白符号

• F 是最终状态集