非确定型图灵机 如果不加特殊说明通常所说的图灵机都是确定型图灵机非确定型图灵机和确定型图灵机的不同之处在于在计算的每一时刻根据当前状态和读写头所读的符号机器存在多种状态转移方案机器将任意地选择其中一种方案继续运作直到最后停机为止具体而言其状态转移函数为 δ  Q  Γ   Q  Γ   L  R  displaystyle delta Qtimes Gamma to Qtimes Gamma times LR 其中 Q displaystyle Q 是状态集合 Γ displaystyle Gamma  是带字母表 L  R displaystyle LR 分别表示读写头向左和向右移动符号  A displaystyle A 表示集合 A displaystyle A 的幂集即  A   S      S  A  displaystyle ASSsubseteq A 例如设非确定型图灵机 M displaystyle M 的当前状态为 q displaystyle q 当前读写头所读的符号为 x displaystyle x 若 δ  q  x     q   x   d     q   x   d       q k  x k  d k   displaystyle delta qxqxdqxdldots qkxkdk 则 M displaystyle M 将任意地选择一个  q i  x i  d i  displaystyle qixidi 按其进行操作然后进入下一步计算 非确定型图灵机 M displaystyle M 在输入串 ω displaystyle omega  上的计算过程可以表示为一棵树不同的分支对应着每一步计算的不同的可能性只要有任意一个分支进入接受状态则称 M displaystyle M 接受 ω displaystyle omega  只要有任意一个分支进入拒绝状态则称 M displaystyle M 拒绝 ω displaystyle omega  某些分支可能永远无法停机但只要有一个分支可以进入接受或拒绝状态我们就说 M displaystyle M 在输入 ω displaystyle omega  上可停机注意我们规定 M displaystyle M 必须是无矛盾的即它不能有某个分支接受 ω displaystyle omega  而同时另一个分支拒绝 ω displaystyle omega  这样有矛盾的非确定型图灵机是不合法的 定理对于任意一个非确定型图灵机 M displaystyle M 存在一个确定型图灵机 M  displaystyle M 使得它们的语言相等即 L  M   L  M   displaystyle LMLM  证明因为非确定型图灵机的计算过程就是一棵树因此我们只需遍历该树就可以模拟其计算过程一个简单的想法是利用深度优先搜索来遍历 M displaystyle M 的计算树但这样行不通因为 M displaystyle M 的某些计算分支可能永远不停机所以我们可以采用一种在算法设计中称为迭代加深搜索的技巧来遍历 M displaystyle M 的计算树具体证明如下 对于非确定型图灵机 M displaystyle M 构造一个确定型图灵机 M  displaystyle M 如下 令 k   displaystyle k  深度优先地模拟 M displaystyle M 的每个分支的计算但每个分支最多只计算 k displaystyle k 步如果某个计算分支在 k displaystyle k 步内可以停机则 M  displaystyle M 也停机并将该计算分支的计算结果输出 令 k displaystyle k 增加 跳转到上一步继续执行 显然若 M displaystyle M 有某个分支可以停机则此 M  displaystyle M 也一定会找到该分支并停机因此 L  M   L  M   displaystyle LMLM  定理如果语言L被非确定型图灵机 M displaystyle M 在多项式时间内接受则一定存在多项式P使得语言L被时间复杂度为 O   P  n   displaystyle OPn 的确定型图灵机程序所接受 定理说明了为什么在证明P  NP之前所有的NPC问题都只有指数时间复杂度算法