读这本书时遭遇了一个问题以及想出的答案

    读《Introduction to Automata Theory、Languages and Computation》（自动机理论、语言和计算导论）时候。遇到了一个问题。这个问题是这样的。

      书在讲到P与NP时，首先要给“时间复杂性”下一个定义。那就是，对于一台图灵机，首先要求它不论接受与否总会停机（也就是说它是一个“算法”），并且，对于全体长度为n的输入，它运行的步数不超过T(n)。T(n)是n的多项式函数。这样的话就说这台图灵机的时间复杂度是T(n)。它接受的那个语言属于P。

      但在432页的框中，作者又说道，这个定义可以改一下：不必要求图灵机对于任何输入总停机，只要求它在”接受“的情况下停机，并且是在T(n)步之内，就可以了。因为，既然存在这个”接受“情况下的步数上限T(n)，那么我们可以构造一台新图灵机：一开始这台新图灵机先数一下输入有多长，也就是n，然后计算T(n)，把这个上限记下来。之后新图灵机模拟原来那台图灵机，每模拟一步计数加一。如果新图灵机没有进入接受状态，但是步数超了上限T(n)。由于原来那台机器只要”接受“，就一定会在T(n)步之内就进入接受状态并停机了。如此看来，现在已经超了上限，原来那台机器不可能”接受“了，那么这台新机器就可以停机了（但不进入接受状态，也就是说，停机并拒绝输入字符串）。这样就构造了一台无论如何总会停机的图灵机。这台新机器用了附加的带进行计数和草稿。随后把多带图灵机转成单带图灵机时，运行时间会增长，但是增长是多项式的。于是新机器是一台多项式时间内总会停机的机器。这就说明了上面说的两种定义其实是等价的。

      这时候我忽然想到一个问题。上面说对于长为n的输入在T(n)内”接受“的图灵机，都可以修改构造出一台永远停机的图灵机。那么对于一般的图灵机呢？对于任何图灵机，长度为n的输入只有有有限个，其中它”接受“的输入自然也只有有限个，”接受“的情况下图灵机总会停机。也就是说，对于所有长度为n的输入，图灵机”接受“的话，总存在一个的最大步数T(n)。T(n)是一个自然数到自然数的映射：任何一个n（输入串的长度），都对应着一个T(n)（就是某台图灵机对于所有长度n的输入，"接受”的情况下运行的最大步数）。这个映射也许不能写成一个方程（一个等式），但它确实是一个映射。那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)。这样用上面那段里，也就是书中432页框里的方法，不是就可以构造一台永远停机的图灵机了么？

      如果上面说的成立的话，那么任何图灵机都可以构造一台接受相同语言的总停机的图灵机。也就是任何可被图灵机接受的语言，都可以构造一台永远停机的图灵机接受它。也就是任何递归可枚举语言都是递归语言。通用语言Lu是可判定的。对角线语言Ld是图灵机可接受的。可是这些都是不可能的。

     上面说的构造法必有错误。后来我想出来错在哪儿了。就错在：“那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)” 上。这个问题就变成了：对于任意一个n -> n的映射T(n)，是否存在一个 f(n)，使得对于所有n，f(n) >= T(n)。注意 f(n)是可以写成一个等式的，而T(n)有可能写不成，而只能写成一对一对的映射，比如，T(1)=5,T(2)=888,T(3)=1000,T(4)=1,......无穷无尽写下去。如果存在，上面那些矛盾就都存在。下面可以证明，这样的f(n)，并不一定存在。

      因为，用那种构造法，需要从n计算出上限T(n)，这个计算也是由这个新图灵机的一部分完成的。这个“部分”可以看做是一个子程序、子图灵机。它单拎出来也是一台图灵机。也就是我们说的那个在所有n上大于等于T(n)、好被我们用来计算图灵机运行步数上限的f(n)，必得是一个图灵机能计算的函数。这样我这台新图灵机才有能力根据输入长度计算这个上限f(n)。后面说的计数、超上限就停机等等才能做到。但是是否对于任何映射T(n)，都能找到一个“盖过”它的、可以被图灵机计算的f(n)呢？

      不能！理由如下：全体图灵机是可列的，其中可以用来算f(n)的图灵机也是可列的（可列集的子集还可列），那么我们画一个矩阵:
                                            

—————— 1——2—— 3—— 4—— 5—— 6——7——8 ......
 图灵机1—— 23
 图灵机2—— —— 43
 图灵机3—— —— —— —45—— —— —— 178
 图灵机4—— —— —— —— —65
 图灵机5—— —— —— —— —— ——76
 图灵机6—— —— —— —— —— —— —— 78
   ......

（请无视那些 —— 它们只是为了把格式撑开）

       这个矩阵，横向上涵盖所有自然数，纵向上涵盖所有算各种f(n)的图灵机（这些图灵机可列）。每一个元素，就是该行的图灵机把该列的那个自然数算成什么。比如图中看到：图灵机3，它计算的函数就叫f3(n)吧，把6算成178，f3(6)=178。这个矩阵对角线上的元素，就是n号图灵机把n算成什么值。

      利用对角线法，构造一个映射T(n)，T(n)把每个n，映射为比n行n列对角线交点上那个值大1的值。比如T(3)=46（比 3 行 3 列上的 45 大 1）。这个映射T(n)是存在的（因为我们构造出它来了）。但是这个映射，找不到任何图灵机可计算的f(n)，使得在所有n上，f(n)>=T(n)。因为对于每一个f(n)，我的T(n)总在一个n上比f(n)大（对角线上那些值）就是说是：“那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)”是不对的。准确点说是对于我们如此构造的T(n)，不存在一个图灵机可计算的 f(n)，使得对于所有n，f(n)都大于等于T(n)。

      不是所有的图灵机都可以构造一台与它接受同样语言的、且永远停机的图灵机。那些矛盾的结论就都出不来了。