透彻剖析确定型图灵机和非确定型图灵机

姜咏江

千禧大奖的头号难题p与np问题是在确定型图灵机和非确定型图灵机上提出来的。要解决p与np问题，就需要彻底搞清楚确定型图灵机与非确定型图灵机的概念。实际研究中，许多人因为不能够透彻理解这两种类型的图灵机，而产生种种歧义。到底图灵机和现代计算机有何共同之处？怎样认识这两种图灵机？这是本文论述的焦点。关于p与np问题已在其它博文中有述（请参考附录）。

1.              图灵机的逻辑结构

图灵机的模型如图1所示，主要有字符带子、读写头和状态转移表等构成。现代计算机是在图灵机的基础上发展起来的，现代计算机在结构上可分为：运算器、控制器、存储器、输入和输出装置五部分。图灵机也有这五部分吗？

图1  图灵机模型

图灵机的带子能够读写字符，同时还兼有输入输出功能，它就是存储器兼输入输出装置。图灵机的运算器和控制器在哪里？就在它的状态转移表当中。状态转移表如何就成为了它的运算器和控制器了？为了说明这个问题，我们举逻辑或运算的例子。

表1是逻辑或运算的图灵机状态转移表。通过这张表我们不难得出0+0=0；0+1=1；1+0=1；1+1=1这些逻辑或运算的真值。因而这个状态转移表是运算器。为何又是控制器呢？从表上可以看出，状态的转移是受带子上读入符号0、1和空格控制的，输入字符不同，图灵机的读写头和状态都会有不同的变化。读入非空格，图灵机就会在带子上右移（R）一位，并在带子上打印（P）出0或1。当读写头读到的是空格时，图灵机总会回到b状态，并且在b状态读写头会右移（R）一格，当读入是其它符号时，就会进入到错误状态。

表1图灵机逻辑或运算状态转移表

学习过计算机设计原理的人是不难将这个图灵机的状态转移表写成逻辑或运算的真值表吧？如果写成真值表的形式，可不可以带着状态的转移形式？

表2是逻辑或又是的真值表和依据输入x、y而设定的状态及其转移形式。这张表不包括表1的空格输入，因为逻辑运算可以不考虑空格的输入。我们这里将图灵机的输入分成了两段，实质上与表1的表达形式相同。

从表2 我们不难认识到，运算器设计的真值表与图灵机的状态转移表就是一个东西。我们将各种运算过程设计成真值表，然后载用逻辑电路表达，那就是运算器了。真值表带上状态变化，也就有了控制的基本形式。

表2  逻辑或真值表与状态转移

到此，我们应该就能够理解图灵机是具有存储器、运算器、控制器和输入输出装置的计算机了。不过由于图灵机构造简单，能够实现的运算单一，所以不能象现代计算机那样，可以完全将计算机的各个逻辑器件分开，也不能象现代计算机那样完成诸多方面的工作。

图灵是否真的将运算状态转移表放到了图灵机中，我们不得而知。但图灵的计算机思想使人们找到了一条设计计算机之路。

图灵机没有做到象现代计算机那样，将各种运算器都放置在一台计算机之中，我们所见到的都是单一的运算情况和一些特殊的数字信息处理，还没有将状态转移表之类的东西转换成象今天的计算机使用要设计那样的程序，所以图灵机用起来并不方便。

图灵机的状态转移表虽然可以认为是运算器和控制器，但却没有用机器方法实现状态识别和控制的方法，而是这方面的问题多数都存在于人的脑中。现代电子计算机通过逻辑电路设计彻底地解决了这方面的工作，使计算机能够成为了依据程序执行就可以完成诸多方面任务的机器。

2.              确定型图灵机定义

前面说的图灵机称为确定型图灵机，其定义如下：

一台图灵机M是一个七元组，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中 Q，Σ，Γ 都是有限集合，且满足：

（1）Q 是有限状态集合；

（2）Σ是输入字母表，其中不包含特殊的空白符 □；

（3）Γ 是带子上字母表，其中 □∈Γ且ΣΓ ；

（4）δ：Q×Γ→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移；

（5）q0∈Q是起始状态；

（6）qaccept是接受状态；

（7）qreject是拒绝接收状态，且qreject≠qaccept。

表1的或运算图灵机中，Q=｛b,c,d,erro｝；Σ=｛0，1｝; Γ=｛0，1，□｝；δ：Q×Γ→Q×Γ×{L,R}的转移函数是表1表示的函数；q0=b。表1中的状态b、c、d都是接受状态qaccept；输入不是Γ中字符的状态都是拒绝接收状态qreject=erro。

3.              确定型图灵机的特点

图灵机是在带子上的有顺序的格子上进行读写的，因而其动作的每一步都是一个顺序过程，解题时的每一步的输入都是惟一的Γ中的符号，因而选择状态只有1种，那么有限次状态选择就可以用自然数n表示。如果图灵机能够解决的问题复杂到需要重复地对带子上的符号进行读写，那么这种读写至多也是有限次k。这样图灵机能够计算问题的状态变化总数至多为n^k。因为重复的长度不同，包含的状态多少也不同，故而可以用a₀n₀^k0+a₁n₁^k1+…+a_nn_n^kn这样的多项式来表示状态变化数。

我们可以假定图灵机每次读写的时间是确定的，那么就可以认为图灵机解决任何问题所经历的时间都是n^k型的时间，即现在通行所说的“多项式时间”。

4.              非确定型图灵机

我们现在使用的计算机编码是图灵机符号集Σ=｛0，1｝的发展，将0、1组成的限位数做为读写头能够一次处理的“符号”。例如8位的二进制数有256个，故图灵机的符号集就是｛00000000，00000001，…，11111111｝这个集合。如此，通过这256个数的输入，图灵机的可能变化状态就多了去了。

为了简单，我们还是回到表1的图灵机解释什么叫非确定型图灵机吧。

表1的图灵机状态是确定的b、c、d、erro，每一个状态转换到下一个状态都是依据输入符号来确定的，这就是确定型图灵机的含义。如果对每个状态来说都不知道输入的符号是什么，或者说每个可能输入的符号都要考虑，那么这个图灵机叫什么？自然就应该叫非确定型图灵机！

将表1的“读入”项认为是不确定的，是在查找问题的时候要用到。例如，“这个或运算的图灵机什么情况下结果为1？”一般的情况，我们要对每种状态可能情况的输入进行“遍历”，逐一找出结果为1的那些“条件”。实际上这是图灵机运算的倒推过程。因为图灵机产生某个结果的条件可能有多个，因而倒推的过程是一棵树结构。依据乘法原理，表1的图灵机不考虑空格和其它符号，那么判定结果是1问题需要经历2²次查找。不难想象，图灵机如果输入的可能符号有k个，每个结果的转移状态选择有n步，那么这种查找结果产生条件的过程最多就要进行kⁿ次。

由图灵机字符集的有限性，我们不难推出图灵机的状态可依指数型变化。例如字符集Σ有256个元素，那么状态会按照256ⁿ的形式变化。我们将n称为状态演变层次。从图灵机的定义我们知道，状态演变层次不能无限大，因而任何的图灵机都是一个有限状态机，因为当状态假定为无限的时候，能够解决问题的图灵机已经不存在了。

5.              非确定型图灵机的定义

从维基百科上下载的非确定型图灵机定义如下：

A non-deterministic Turing machine can be formally defined as a 6-tuple

Μ=(Q，Σ，β，□，Α，δ）, where

（1）Q is a finite set of states

（2）Σis a finite set of symbols (the tape alphabet)

（3）β∈Q is the initial state

（4）□∈Σis the blank symbol

（5）ΑQ  is the set of accepting (final) states

（6）δ( QΑ×Σ)×(Q×Σ×{L,R}) is a relation on states and symbols called the transition relation.

有了上面的解释，研究数学和计算机的读者应该不难理解这个非确定型图灵机的定义了。确定型图灵机的状态转移表是一个函数表达形式，而非确定型图灵机的状态转移表是一个关系表达式，这是两者最根本的区别。

附录：http://blog.sciencenet.cn/blog-340399-887347.html

2015-05-09