深入理解非确定型图灵机的概念与P＝NP

姜咏江

研究千禧大奖头号难题p与np问题，最难让人理解的是非确定性图灵机的概念。非确定型图灵机并不是任意一个图灵机这种概念，而是在一个确定型图灵机存在的情况下，用读入字符可能是图灵机带上任意一个字符，来确定某个猜测的结果是否是该图灵机实际运算结果的计算方式的概念。

下表是一个或运算图灵机，假定其带子上只允许出现空格、0和1，那么用这个图灵机运算需要在带子上事先写上参加运算的数码0或1。由于这是一个二元运算，故计算出结果需要2次输入，即需要2次状态演变才能输出结果。即状态变化或者为b→c，或者为b→d。

能够确定一个图灵机运算结果的状态数，我们不妨称为状态演变层次。二元运算有2个层次，n元运算一般应该有n个层次。

针对这个确定型图灵机我们要回答数码2是不是这个图灵机的运算结果？我们该如何做呢？在我们已经知道其结果只能是｛0，1｝这个集合中的数，也就是用2能够直接与结果集合元素比较的时候，就可以给出确定的回答。但是在我们都不知道这个图灵机运算结果的情况下，如何来验证？这就需要分层对可能输入的字符进行验证。具体地说，先要在b状态下考虑输入是0，再到c状态下考虑输入是0，运算的结果是不是2（下图的红线）；如果结果不是2，再在c状态考虑输入是1的情况（下图的橙线）。

图1  非确定型图灵机上的猜测验证

如果从b状态0输入出发未得到结果是2的答案，则还要从b状态输入是1的情况出发再去逐层验证，这样会有图中的蓝线和浅蓝线表示的情况。

确定型图灵机如果是n元运算，那么状态是层次也应该是n，其中运算的中间结果也应该在带子字符集当中，状态输出字符可以打印之后，再做为下一状态的输入字符。做为n元运算的非确定性图灵机，每个状态的转移仍然受字符集的限制。如果带子上的字符集有k个不同字符，那么猜测运算结果的查找象图1那样，最多可能进行kⁿ次，这样才能够确定给出的结果是否是该图灵机能够计算出的结果。

2015-5-11

非确定型图灵机会因为参加运算的字符出现的次数n的增加，而使全部可能状态kⁿ趋向无穷大。在猜测验证或称为判定问题中，由于字符序列中字符出现次数不定，即n可能趋于无穷大，就会出现总是不能够获得肯定或否定的过程，进而产生了趋于无穷的状态转移，也就是出现了所谓无穷多状态的理论图灵机。这个理论图灵机就是一般理解的非确定型图灵机。

这样，在非确定型图灵机上验证一个问题，随着n的不断增大，就可能出现三种情况：

1.       过程最终是接受状态；

2.       过程最终是拒绝状态；

3.       过程永远不会完结（例如出现了死循环）。

前两种情况n最终是有限数，称为问题是可验证的，第3中情况称为问题是不可验证的。第1种情况的问题称为可验证解。而由非确定型图灵机输入的无穷性知道，第2种情况的输入也不能认为问题已经验证了，它只能回答的是：这个输入条件下，验证过程本次最终得到的不是猜测的结果。

由上面的分析不难得出：确定型图灵机状态集是非确定型图灵机的状态有限子集。

确定型图灵机不会出现不可验证的情况。而非确定型图灵机任意一个可验证解的问题必然属于某个确定型图灵机的解。

如果要用数学方法去证明这些结论，也并不困难。

“类NP由所有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合”。至此，不论多项式时间如何，我们难道还没有理由说P=NP吗？

2015-6-3