非确定型图灵机
维库，知识与思想的自由文库
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机 的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为 止。具体而言，其状态转移函数为
其中Q是状态集合，Γ是带字母表，L,R分别表示读写头向左和向右移动；符号2A 表示集合A的幂集，即
例如，设非确定型图灵机M的当前状态为q，当前读写头所读的符号为x，若
则M将任意地选择一个(qi,xi,di)，按其进行操作，然后进入下一步计算。
非确定型图灵机M在输入串ω上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称M接受ω；只要有任意一个分支进入拒绝状态，则称M拒绝ω；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说M在输入ω上可停机。注意，我们规定M必须是无矛盾的，即它不能有某个分支接受ω而同时另一个分支拒绝ω，这样有矛盾的非确定型图灵机是不合法的。
定理：对于任意一个非确定型图灵机M，存在一个确定型图灵机M'，使得它们的语言相等，即L(M) = L(M')。
证明： 因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历M的计算树，但这样行不通，因为M的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为迭代加深搜索的技巧来遍历M的计算树。具体证明如下：
对于非确定型图灵机M，构造一个确定型图灵机M'如下：
- 令k = 1；
- 深度优先地模拟M的每个分支的计算，但每个分支最多只计算k步，如果某个计算分支在k步内可以停机，则M'也停机，并将该计算分支的计算结果输出。
- 令k增加 1，跳转到上一步继续执行。
显然，若M有某个分支可以停机，则此M'也一定会找到该分支并停机。因此L(M) = L(M')。
