（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个例子，没有必要详细地理解它。）这一特殊的方程和数学中著名的或许是最著名的未解决的问题相关。该问题是：存在任何满足这方程的自然数集合w，x，y，z 吗？这个著名的称作“费马最后定理”的陈述被伟大的十七世纪法国数学家皮埃尔·德·费马(1601—1665)写在丢番都的 《代数》一①8书空白的地方。费马宣布这方程永远不能被满足 。虽然费马以律师作为职业 （并且是笛卡尔的同时代人），他却是那个时代最优秀的数学家。他宣称得到了这一断言的 “真正美妙的证明”，但那里的空白太小写不下。可惜迄今为止既没有人能够重新证明之，也没有人能找到任何和费马断言①相反的例子 ！很清楚，在给定了四个数(w,x,y,z)后，决定该方程是否成立是计算的① 记住我说的自然数是指0，1，2，3，4，5，6，…。我写成 “x+1”和 “w+3”等等，而不写成费马断言的更熟知的形式(xw+yw=xw ，x，y ，z ＞0，w ＞2)的原因是，我们允许x,w 等等为从零开始的所有自然数。① 普林斯顿大学的英籍数学家安德鲁·怀尔斯在 1993 年6 月23 日宣布证明了费马最后定理 （译者）。----------------------- Page 68-----------------------事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四数组，直到方程被满足时才停下。 （我们已经看到，存在于一根单独磁带上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这样，我们只要跟随着这些单独的数的自然顺序就能“跑遍”所有的四数组。）如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。可以用类似的办法把许多未解决的数学问题按图灵机停机问题来重述。 “哥德巴赫猜想”即是这样的一个例子，它断言比2 大的任何偶数都②是两个质数之和 。决定给定的自然数是否为质数是一个算法步骤，由于人们只需要检验它是否能被比它小的数整除，所以这只是有限计算的事体。我们可以设计跑遍所有偶数6，8，10，12，14，…的一台图灵机，尝试把它们分成奇数的对的所有不同的方法：6=3+3，8=3+5，10=3+7=5+5，12=5+7，14=3+11=7+7，…对于这样的每一个偶数检验并确认其能分成都为质数的某一对数。（我们显然不需要去检验除了2+2之外的偶的被加数对，由于除了 2之外所有质数都是奇的。）只有当我们的机器达到一个由它分成的所有的任何一对数都不是质数对的偶数为止才停止。我们在这种情形就得到了哥德巴赫猜想的反例，也就是说一个 （比2 大的）偶数不是两个质数之和。这样，如果我们能够决定这台图灵机是否会停，我们也就有了决定哥德巴赫猜想真理性的方法。这里自然地产生了这样的问题：我们如何决定任何特殊的图灵机 （在得到特定输入时）会停止否？对于许多图灵机回答这个问题并不难：但是偶尔地，正如我们上面得到的，这答案会涉及到一个杰出的数学问题的解决。这样，存在某种完全自动地回答一般问题，即停机问题的算法步骤吗？图灵指出这根本不存在。他的论证的要点如下所述，我们首先假定，相反地，存在这样的一种①算法 。那么必须存在某台图灵机H，它能 “决定”第n 台图灵机作用于数m 时，最终是否停止。我们假定，如果它不停的话，其输出磁带编号为0，如果停的话为 1：I0如果T (m) = □nH(n；m) = ì1如果T (m)停止。ó n在这里人们可采取对普适图灵机 U 用过的同样规则给对(n,m)编码。然而，这会引起如下技术问题，对于某些数 n （例如n=7），T 不是正确指定的，n② 我们记得，质数2，3，5，7，11，13，17，…是那些只能分别被它们自己和 1 整除的自然数。0 和 1 都不认为是质数。① 这是熟知的并且有力的被称为反证法的数学步骤。利用这种办法，人们首先假定所要证明的东西是错的，然后从这里推出一个矛盾，就这样证明所需要的结果实际上是对的。----------------------- Page 69-----------------------而且在磁带上记号 111110不足以把n从m 分开。为了排除这一个问题，让我们假定 n 是用扩展二进位记号而不仅仅是二进位记号来编码，而 m 正和以前一样用通常的二进位记号。那么记号110实际上将足够以把n和m 区分开来。在H(n；m)中用分号，而在U(n,m)中用逗号就是为了表明这个改变。现在让我们想象一个无限的阵列，它列出所有可能的图灵机作用于所有可能的不同输入的所有输出。阵列的 n行展现当第 n 台图灵机应用于不同的输入0，1，2，3，4，……时的输出：我在上表中稍微有些欺骗，并且没有把图灵机按它们的实际编号列出。由于所有n 比11小的机器除了□外没有得到任何东西，而对于n=11只得到0，所以那样做的话就会得到一张一开始就显得过于枯燥的表。为了使此表一开始就显得更有趣，我假定已得到某种更有效得多的编码。事实上我只是相当随机地捏造这张表的元素，仅仅是为了给出有关它的外表的大体印象。我不要求用某一个算法实际计算过这一个阵列。 （事实上，正如我们很快就要看到的，不存在这样的算法。）我们仅仅是假想，真正的表不知怎么搞的已经摆在我们面前，也许是由上帝吧！如果我们试图计算这一个阵列，正是□的发生引起了困难。因为既然那些计算简单地一直永远算下去，我们也许弄不清什么时候把□放在某一位置上！然而，如果我们允许使用假想的H，由于H会告诉我们□实际上在什么地方发生，我们就可以提供一种产生该表的计算步骤。但是相反地，我们用0 来取代每一次□的发生，就这样地利用H 把□完全除去。这可由把计算H(n；m)叫放在T 对m 作用之前而作到；然后只有如果 H(n；m)=1 时n（也就是说，只有如果计算T (m)实际上给出一个答案时），我们才允许n----------------------- Page 70-----------------------T 作用到m 上，而如果H(n；m)=0 （也就是如果T (m)=□），则简单地写n n为0。我们可把新的步骤（也就是把H(n；m)的作用放在T (m)之前得到的）n写成T (m)×H(n；m)。n（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我们在符号运算上有：□×0=0。）现在这张表变成：我们注意到，假定H存在，该表的行由可计算的序列组成。 （我用一个可计算序列表明一个其接连的值可由一个算法产生出来的一个无限序列；也就是存在一台图灵机，当它依序地应用于自然数m=0，1，2，3，4，5，…上时，就得到了这个序列的接续元素。）现在，我们从该表中可以注意到两个事实。首先自然数的每一可计算序列必须在它的行中出现在某处 （也许出现好几回）。这个性质对于原先的带有□的表已经是真的。我们只不过是简单地加上一些行去取代 “伪品”的图灵机（也就是至少产生一个□的那些）。其次，我们已经假定，图灵机H 实际上存在，该表已被计算地（也就是用某个确定的算法）由步骤T (m)×H(n；m)产生。换言之，存在n某一台图灵机Q，当它作用于一对数(n；m)时就会在表中产生合适的元素。为此我们可以在Q 的磁带上以和在H 中一样的方式对n和m 编码。我们得到Q(n；m)=T (m)×H(n；m)。n现在我们应用乔治·康托的 “对角线删除法”的天才的和强有力的技巧的变种。 （下一章将看到康托对角线删除法的原型。）考虑现在用粗体字标明的对角线元素：----------------------- Page 71-----------------------这些元素提供了某一序列0，0，1，2，1，0，3，7，1，……现在把它的每一元素都加上 1就得到1，1，2，3，2，1，4，8，2，……假设我们的表是计算地产生的，那么这就清楚地是一个可计算的步骤，而且它为我们提供了某一个新的可计算的序列，事实上为 1+Q(n；n),也就是1+T (n)×H(n；n)n（由于对角线是令m 等于n 而得到的）。但是，我们的表包括了每一可计算的序列，所以我们新的序列必须在表中的某一行。然而，这是不可能的！由于我们新序列和第一行在第一元素处不同，和第二行在第二元素处不同，和第三行在第三元素处不同等等。这是一个明显的冲突。正是这个冲突，建立了我们所要证明的，即在事实上图灵机H 不存在！不存在决定一台图灵机将来停止与否的普适算法。另一种重述这个论证的方法是注意到，在假定H存在时，对于算法1+Q(n；n)(对角线步骤！)存在某一图灵机号码，譬如 k，这样我们有1+T (n)×H （n；n）=T (n)。n n但是，如果我们在这个关系中代入 n=k就得到1+T (k)×H(k；k)=T (k)。k k因为如果T (k)停止我们就得到了不可能的关系式k1+T (k)=T (k)，k k(由于H(k；k)=1)，而如果T (k)不停止 （这样H(k；k)=0)，我们有同样k不协调的结果1+0=□，所以前面的假定导致一个矛盾。一台特定的图灵机是否停止是一个定义完好的数学问题 （反过来，我们已经看到，各种有意义的数学问题可被重述成图灵机的停机问题）。这样，依靠显示不存在决定图灵机停机问题的算法，图灵 （正如撤屈用自己十分不同的手段）指出，不存在决定数学问题的一般算法。希尔伯特的判决问题没有解答！这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题----------------------- Page 72-----------------------的真理或非真理；或者决定某一台给定的图灵机是否会停止。我们可以利用一些技巧或者仅仅是常识，就能在一定情况下决定这种问题。 （例如，如果一台图灵机的程序表中不包括STOP 指令，或者只包含STOP 指令，那么常识就足以告诉我们它会不会停止！）但是，不存在一个对所有的数学问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个算法。我们似乎现在已经建立了，至少存在某些非决定的数学问题。然而，我们从未做过这种事！我们还没有展示过，存在某种特别尴尬的数时，它在某种绝对的意义上，不可能决定该机器是否停止。的确，正如我们很快就要看到的，情况刚好相反。我们关于单独问题的不可解性一点也没提，仅仅是说关于问题的族的算法的不可解性。在任何单独的情形下，答案或者为 “是”或者为“非”，所以肯定存在一个决定那个特定情形的算法，也就是在它面临该问题时，依情况而定，会简单地讲 “是”或“非”。当然，困难在于我们可能不知道用这些算法中的哪一个。那就是决定一个单独陈述而不是决定一族陈述的数学真理的问题。重要的是要意识到，算法本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起来。----------------------- Page 73-----------------------如何超过算法我们在以后论及哥德尔定理时再回到决定数学陈述的真理性问题 （参阅第四章）。我希望在此刻指出，图灵的论证比我迄今仿佛所暗示的更具建设性而更少负面性。我们肯定还没有展示出一台特殊的图灵机，它在某种绝对的意义上不能决定其是否停止的问题。的确，如果我们仔细地考察该论证就会发现，我们步骤本身实际上已经隐含地告诉我们，对这利用图灵步骤建造的似乎 “极端荒谬”的机器的答案！我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉我们什么时候一台图灵机将不停止。正如在上面概述的，图灵步骤将明白地展现了一台图灵机计算，对这计算那个特殊算法不能决定其是否停止。然而，在这样做的同时，它实际上使我们在这情况下看到了答案！我们展现的特殊的图灵机计算的确不会停止。为了仔细考查这怎么引起的，假定我们具有一个这样有时有效的算法。正如以前那样，我们用H 来标志这个算法 （图灵机），但是现在允许该算法有时不能告诉我们一台图灵机在实际上将不停止：I0或□如果T (m) = □nH(n；m) = ì1如果T (m)停止。ó n这样，当 T (m)=□时H(n；m)=□是一种可能性。实际上存在许多这种算法nH(n；m)。 （例如，只要T (m)一停止，H(n；m)就能简单地产生 1，尽管那n个特殊的算法几乎没有什么实际的用处！）除了不把所有的□用0 来取代而留下一些以外，我们可以像上述那样仔细地顺着图灵的步骤。正如以前那样，对角线过程提供了对角线上的第n个元素1+T (n)×H(n；n)。n（只要H(n；m)=□，我们就将得到一个□。注意□×□=□，1+□=□。）这是一个完好的计算，所以它是由某一台，譬如讲第 n 台图灵机得到的，而且现在我们确实有1+T (n)×H(n；n)=T (n)。n k我们看第 k个对角元素，也就是 n=k，就会得到1+T (k)×H(k；k)=T (k)。k k如果计算T (k)停止，我们就有了一个矛盾 （由于假定只要T (k)停止 H(k；k kk)就为 1，则方程导致不协调性：1+T (k)=T (k)。所以T (k)。不能停止，k k k也就是T (k)=□。k但是，算法不能 “知道”这个。因为如果该算法给出H(k；k)=0，则我们应该又导致矛盾 （我们得到了在符号上不成立的关系：1+0=□)。这样，如果我们能找到 k，就将知道如何去建造击败我们知道其答案----------------------- Page 74-----------------------的算法的特别计算！我们怎么找到k 呢？这是一项艰巨的工作。我们需要做的是仔细考察 H （n；m）和T (m)的构造，然后仔细弄清1+T (n)×H(n；n nn)作为一台图灵机是如何动作的。我们发现这台图灵机的号码为 k。要把①这一切要弄透彻肯定是复杂的，但它是可以办得到的 。由于这种复杂性，