谈谈图灵机上的求解与验证问题

姜咏江

   在讨论千禧大奖的所谓世界头号难题P/NP，涉及到求解和验证两个问题。图灵机是有限状态转换的部分函数，这种状态转移借助于输入字符集，而这个输入字符集也是有限的。不输入字符时，图灵机用输入空格表示。现代计算机用编码替代字符集，空格用特殊的编码替代了。

   一个图灵机的可求解是有限的，可以通过状态每次惟一转换来最后确定结果。当将结果求出来之后（这需要用特殊的状态来表达），求解过程所经历的全部输入输出就构成了该图灵机的可解问题。

   沿着一个确定的图灵机设计的状态某个状态转移下去，最终未必能够得到所谓的结果。这种情况图灵机要设置拒绝状态明确地指出。前面状态转移中涉及的输入和输出形成的问题，称为在此图灵机上无解。

   图灵机以字符集的字符排列称为问题的标识，但不见得字符集的所有字符都会在标识的最后出现。例如四进制数的数码有0、1、2、3，在图灵机的所有可解问题中，最后出现的字符没有2，我们说2不是这台图灵机可解问题的结果。这就是图灵机的状态转移表被说成是“部分函数”的原因。

   按照图灵机的状态转移表动作下去，最后到达接受状态，则问题有解；若最后到达拒绝状态，则问题无解。

   图灵机有解的问题，状态转移的形式总可以表达成幂多项式的形式，因为状态转移至多能够形成部分状态有限循环，也就是计数表达式中会出现an^k这样的幂项。产生状态转移循环一定是出现了多于一个字符的选择性转移，这是函数变化中所允许的。不论何种情况，图灵机的可解问题中的a、k、n最后一定是确定数。

现在来看在这台四进制图灵机上如何验证一个猜测的结果。

  假如就想猜测2是不是它的可解问题的结果。第一步，我们要从开始状态分别输入0、1、2、3，从而转移到4个不同的状态；第二步，从第一步产生的4个状态，逐一输入0、1、2、3，这再产生16个不同的状态；以后再从16个状态产生64个状态；…，如此继续。如果某个状态是接受状态或拒绝状态，反向推到开始状态的所有状态是解题路线。如果解题路线最后是接受状态，并且输出是猜测的结果，那么反推的全部输入输出就是图灵机的可解问题。解题路线的最后是拒绝状态或者结果字符与猜测字符不同，那么验证要到另外的解题路线去找。如果这个图灵机的所有解题路线都不是猜测的结果，那么可以断定开始猜测的结果不是这台图灵机问题的结果。

   如果图灵机的输入输出字符集有k个字符，而状态树的最高层次是n，那么图灵机最多有kⁿ个不同的可解问题。

   从图灵机的猜测验证过程来看，这似乎是一台不确定的图灵机。图灵机解题路线形成了一棵树的枝杈结构，最后的接受状态和拒绝状态连接在前级相应的树叶上。

   通过以上分析，不难看出验证一个问题，远比一个已知条件存在的情况下求解复杂的多。要区分这种复杂程度，必须找准影响复杂程度的因素，进而准确地把握两种问题求解的本质，从中寻找出最佳的算法。

        最后，验证问题和验证问题结果应该是不同的。如果一个图灵机的全部结果都在某集合中，只要看看猜测的字符是不是在解集中就可以完成验证，那问题就简单多了。这种简单的验证必须事先求出全部的解问题，然后才有这种简单省事的验证，其实也叫查询。