查看“︁非确定型图灵机”︁的源代码

{{unreferenced|time=2010-08-21T07:01:16+00:00}}
如果不加特殊说明，通常所说的[[图灵机]]都是确定型图灵机。'''非确定型图灵机'''和[[确定型图灵机]]的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为
:<math>
\delta: Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}
</math>
其中<math>Q</math>是状态集合，<math>\Gamma</math>是带字母表，<math>L, R</math>分别表示读写头向左和向右移动；符号<math>2^{A}</math> 表示集合<math>A</math>的幂集，即 
:<math>
2^A  = \{ S~|~S \subseteq A \}
</math>

例如，设非确定型图灵机<math>M</math>的当前状态为<math>q</math>，当前读写头所读的符号为<math>x</math>，若
:<math>
\delta(q,x) = \{ (q_1, x_1, d_1), (q_2, x_2, d_2), \ldots , (q_k, x_k, d_k)\}
</math>
则<math>M</math>将''任意地''选择一个<math>(q_i, x_i, d_i)</math>，按其进行操作，然后进入下一步计算。

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

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

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

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

# 令<math>k= 1</math>；
# 深度优先地模拟<math>M</math>的每个分支的计算，但每个分支最多只计算<math>k</math>步，如果某个计算分支在<math>k</math>步内可以停机，则<math>M'</math>也停机，并将该计算分支的计算结果输出。
# 令<math>k</math>增加 1，跳转到上一步继续执行。

显然，若<math>M</math>有某个分支可以停机，则此<math>M'</math>也一定会找到该分支并停机。因此<math>L(M) = L(M')</math>。

'''定理2'''：如果语言L被非确定型图灵机<math>M</math>在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为<math>O(2^{P(n)})</math>的确定型图灵机程序所接受。

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

== 参见 ==

* [[图灵机]]
* [[P (複雜度)|複雜度類P]]
* [[NP (複雜度)|複雜度類NP]]
* [[P/NP问题]]

{{复杂度类}}
[[Category:图灵机]]