[科普中国]-非确定型图灵机

非确定型图灵机(non-deterministic Turingmachine)确定型图灵机的一种推广。设P为一个由图灵机指令组成的有穷集合，P不一定满足相容性条件，如果把P作为程序，依类似于确定型图灵机的模式进行运行，则可能会在某个时刻有两条或更多的指令可以用，而它们所规定的动作又不一致。例如P中含有qaBq, BR和qoBq1BL两条指令。则当内部状态为q。且所指单元为空白时，这两条指令都可用，但一个要右移，另一个则要左移。机便称为非确定型图灵机.对不确定型图灵机M来说，对同一个输人可能有不同的运行过程。

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

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

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

则 M将任意地选择一个 ，按其进行操作，然后进入下一步计算。

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

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

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

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

1.令；

2.深度优先地模拟 M的每个分支的计算，但每个分支最多只计算 k步，如果某个计算分支在 k步内可以停机，则M'也停机，并将该计算分支的计算结果输出。

3.令 k增加 1，跳转到上一步继续执行。

显然，若 M有某个分支可以停机，则此 M'也一定会找到该分支并停机。因此。

定理2：如果语言L被非确定型图灵机 M在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为的确定型图灵机程序所接受。

定理2说明了为什么在证明P=NP之前，所有的NPC问题都只有指数时间复杂度算法。1

图灵机图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。1

通用图灵机对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用表示图灵机 M的编码。

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M的编码，然后模拟 M的运作，这样的图灵机称为通用图灵机（Universal Turing Machine）。现代电子计算机的计算模型其实就是这样一种通用图灵机，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所