非确定型图灵机

维基百科，自由的百科全书

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为

$\delta: Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}$

其中 $Q$ 是状态集合， $Γ$ 是带字母表， $L, R$ 分别表示读写头向左和向右移动；符号 $2 A$ 表示集合 $A$ 的幂集，即

$2^A = \{ S~|~S \subseteq A \}$

例如，设非确定型图灵机 $M$ 的当前状态为 $q$ ，当前读写头所读的符号为 $x$ ，若

$\delta(q,x) = \{ (q_1, x_1, d_1), (q_2, x_2, d_2), \ldots , (q_k, x_k, d_k)\}$

则 $M$ 将任意地选择一个 $(q i, x i, d i)$ ，按其进行操作，然后进入下一步计算。

非确定型图灵机 $M$ 在输入串 $ω$ 上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称 $M$ 接受 $ω$ ；只要有任意一个分支进入拒绝状态，则称 $M$ 拒绝 $ω$ ；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说 $M$ 在输入 $ω$ 上可停机。注意，我们规定 $M$ 必须是无矛盾的，即它不能有某个分支接受 $ω$ 而同时另一个分支拒绝 $ω$ ，这样有矛盾的非确定型图灵机是不合法的。

定理：对于任意一个非确定型图灵机 $M$ ，存在一个确定型图灵机 $M'$ ，使得它们的语言相等，即 $L (M) = L (M')$ 。

证明： 因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历 $M$ 的计算树，但这样行不通，因为 $M$ 的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为迭带加深搜索的技巧来遍历 $M$ 的计算树。具体证明如下：

对于非确定型图灵机 $M$ ，构造一个确定型图灵机 $M'$ 如下：