这里自然地产生了这样的问题：我们如何决定任何特殊的图灵机（在
得到特定输入时）会停止否？对于许多图灵机回答这个问题并不难：但是
偶尔地，正如我们上面得到的，这答案会涉及到一个杰出的数学问题的解
决。这样，存在某种完全自动地回答一般问题，即停机问题的算法步骤吗？
图灵指出这根本不存在。
他的论证的要点如下所述，我们首先假定，相反地，存在这样的一种
算法①。那么必须存在某台图灵机
H，它能“决定”第
n台图灵机作用于数
m时，最终是否停止。我们假定，如果它不停的话，其输出磁带编号为
0，
如果停的话为
1：
0如果T (m) =
n □
H(n；m)=
1如果T (m)停止。
n
在这里人们可采取对普适图灵机
U用过的同样规则给对(n,m)编码。然而，
这会引起如下技术问题，对于某些数
n（例如
n=7），T
n不是正确指定的，
②我们记得，质数
2，3，5，7，11，13，17，.是那些只能分别被它们自己和
1整除的自然数。0和
1都
不认为是质数。
①这是熟知的并且有力的被称为反证法的数学步骤。利用这种办法，人们首先假定所要证明的东西是错的，
然后从这里推出一个矛盾，就这样证明所需要的结果实际上是对的。
而且在磁带上记号
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
n对
m作用之前而作到；然后只有如果
H(n；m)=1时
（也就是说，只有如果计算
T
n(m)实际上给出一个答案时），我们才允许
TT作用到
m上，而如果
H(n；m)=0（也就是如果
T
n(m)=□），则简单地写
为
0。我们可把新的步骤（也就是把
H(n；m)的作用放在
T
n(m)之前得到的）
写成
Tn(m)×H(n；m)。
（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我
们在符号运算上有：□×0=0。）
现在这张表变成：
我们注意到，假定
H存在，该表的行由可计算的序列组成。（我用一个可
计算序列表明一个其接连的值可由一个算法产生出来的一个无限序列；也
就是存在一台图灵机，当它依序地应用于自然数
m=0，1，2，3，4，5，.
上时，就得到了这个序列的接续元素。）现在，我们从该表中可以注意到
两个事实。首先自然数的每一可计算序列必须在它的行中出现在某处（也
许出现好几回）。这个性质对于原先的带有□的表已经是真的。我们只不
过是简单地加上一些行去取代“伪品”的图灵机（也就是至少产生一个□
的那些）。其次，我们已经假定，图灵机
H实际上存在，该表已被计算地
（也就是用某个确定的算法）由步骤
T
n(m)×H(n；m)产生。换言之，存在
某一台图灵机
Q，当它作用于一对数(n；m)时就会在表中产生合适的元素。
为此我们可以在
Q的磁带上以和在
H中一样的方式对
n和
m编码。我们得
到
Q(n；m)=T
n(m)×H(n；m)。
现在我们应用乔治·康托的“对角线删除法”的天才的和强有力的技
巧的变种。（下一章将看到康托对角线删除法的原型。）考虑现在用粗体
字标明的对角线元素：
列
0，0，1，2，1，0，3，7，1，..现在把它的
每一元素都加上
1就得到
1，1，2，3，2，1，4，8，2，..
假设我们的表是计算地产生的，那么这就清楚地是一个可计算的步骤，而
且它为我们提供了某一个新的可计算的序列，事实上为
1+Q(n；n),也就是
1+Tn(n)×H(n；n)
（由于对角线是令
m等于
n而得到的）。但是，我们的表包括了每一可计
算的序列，所以我们新的序列必须在表中的某一行。然而，这是不可能的！
由于我们新序列和第一行在第一元素处不同，和第二行在第二元素处不
同，和第三行在第三元素处不同等等。这是一个明显的冲突。正是这个冲
突，建立了我们所要证明的，即在事实上图灵机
H不存在！不存在决定一
台图灵机将来停止与否的普适算法。
另一种重述这个论证的方法是注意到，在假定
H存在时，对于算法
1+Q(n；n)(对角线步骤！)存在某一图灵机号码，譬如
k，这样我们有
1+Tn(n)×H（n；n）=T
n(n)。
但是，如果我们在这个关系中代入
n=k就得到
1+Tk(k)×H(k；k)=T
k(k)。
因为如果
T
k(k)停止我们就得到了不可能的关系式
1+Tk(k)=Tk(k)，
(由于
H(k；k)=1)，而如果
T
k(k)不停止（这样
H(k；k)=0)，我们有同样
不协调的结果
1+0=□，
所以前面的假定导致一个矛盾。
一台特定的图灵机是否停止是一个定义完好的数学问题（反过来，我
们已经看到，各种有意义的数学问题可被重述成图灵机的停机问题）。这
样，依靠显示不存在决定图灵机停机问题的算法，图灵（正如撤屈用自己
十分不同的手段）指出，不存在决定数学问题的一般算法。希尔伯特的判
决问题没有解答！
这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题
的真理或非真理；或者决定某一台给定的图灵机是否会停止。我们可以利
用一些技巧或者仅仅是常识，就能在一定情况下决定这种问题。（例如，
如果一台图灵机的程序表中不包括
STOP指令，或者只包含
STOP指令，那
么常识就足以告诉我们它会不会停止！）但是，不存在一个对所有的数学
问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个算
法。
我们似乎现在已经建立了，至少存在某些非决定的数学问题。然而，
我们从未做过这种事！我们还没有展示过，存在某种特别尴尬的数时，它
在某种绝对的意义上，不可能决定该机器是否停止。的确，正如我们很快
就要看到的，情况刚好相反。我们关于单独问题的不可解性一点也没提，
仅仅是说关于问题的族的算法的不可解性。在任何单独的情形下，答案或
者为“是”或者为“非”，所以肯定存在一个决定那个特定情形的算法，
也就是在它面临该问题时，依情况而定，会简单地讲“是”或“非”。当
然，困难在于我们可能不知道用这些算法中的哪一个。那就是决定一个单
独陈述而不是决定一族陈述的数学真理的问题。重要的是要意识到，算法
本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起
来。
如何超过算法
如何超过算法
ìí.
这样，当T
(m)=□时H(n；m)=□是一种可能性。实际上存在许多这种算法n
该论证就会发现，我们步骤本身实际上已经隐含地告诉我们，对这利用图
灵步骤建造的似乎“极端荒谬”的机器的答案！
我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉
我们什么时候一台图灵机将不停止。正如在上面概述的，图灵步骤将明白
地展现了一台图灵机计算，对这计算那个特殊算法不能决定其是否停止。
然而，在这样做的同时，它实际上使我们在这情况下看到了答案！我们展
现的特殊的图灵机计算的确不会停止。
为了仔细考查这怎么引起的，假定我们具有一个这样有时有效的算
法。正如以前那样，我们用
H来标志这个算法（图灵机），但是现在允许
该算法有时不能告诉我们一台图灵机在实际上将不停止：
0或□如果T (m) = □
H(n；m) =
如果nn
1 T (m)停止。
H(n；m)。（例如，只要
T
n(m)一停止，H(n；m)就能简单地产生
1，尽管那
个特殊的算法几乎没有什么实际的用处！）
除了不把所有的□用
0来取代而留下一些以外，我们可以像上述那样
仔细地顺着图灵的步骤。正如以前那样，对角线过程提供了对角线上的第
n个元素
1+Tn(n)×H(n；n)。
（只要
H(n；m)=□，我们就将得到一个□。注意□×□=□，1+□=□。）
这是一个完好的计算，所以它是由某一台，譬如讲第
n台图灵机得到的，
而且现在我们确实有
1+Tn(n)×H(n；n)=T
k(n)。
我们看第
k个对角元素，也就是
n=k，就会得到
1+Tk(k)×H(k；k)=T
k(k)。
如果计算
T
k(k)停止，我们就有了一个矛盾（由于假定只要
T
k(k)停止
H(k；
k)就为
1，则方程导致不协调性：1+T
k(k)=Tk(k)。所以
T
k(k)。不能停止，
也就是
Tk(k)=□。
但是，算法不能“知道”这个。因为如果该算法给出
H(k；k)=0，则我们
应该又导致矛盾（我们得到了在符号上不成立的关系：1+0=□)。
这样，如果我们能找到
k，就将知道如何去建造击败我们知道其答案
的算法的特别计算！我们怎么找到
k呢？这是一项艰巨的工作。我们需要
做的是仔细考察
H（n；m）和
T
n(m)的构造，然后仔细弄清
1+T
n(n)×H(n；
n)作为一台图灵机是如何动作的。我们发现这台图灵机的号码为
k。要把
这一切要弄透彻肯定是复杂的，但它是可以办得到的①。由于这种复杂性，
若不是因为我们为了击败H而特地制造T
k(k)的这个事实，我们对计算T
k(k)
毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的
H是哪一个，
该步骤都能找到合适的
k，使得
T
k(k)击败
H，因此这样我们可以比该算法
做得更好。如果我们认为自己仅仅比算法更好些，也许会给我们带来一些
小安慰！
事实上，该过程被定义得如此之好，以至于在给定的
H下，我们可找
到产生
k的一个算法。这样，在我们过于得意之前必须意识到，由于这个
算法事实上“知道”T
k(k)=□，所以它能改善
9H，是不是？在上面提到一
个算法时，用拟人化的术语“知道”是有助的。然而，该算法仅仅是跟随
我们预先告诉它去跟随的法则，这难道不是我们在“知道”吗？或者我们
自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去跟
随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为
真何为伪的问题。这是我们必须重新讨论的中心问题。数学真理（以及其
非算法性质）的问题将在第四章考虑。现在我们至少对术语“算法”和“可
计算性”的意义以及某些相关的问题已有些领略。
①事实上，由于在上面建造普适图灵机
U已使我们能把
Tn(n)写成作用于
n上的一台图灵机，所以已经得
到这个最难的部分。
撤屈拉姆达计算法
撤屈拉姆达计算法
有一件事要弄清楚。可计算性是一个真正“绝对的”数学概念。它是
一种抽象的观念，它完全超越按照我们描述的“图灵机”的任何特别实现
之外。正如我在以前所评论的，我们不必对表征图灵的天才而特别的手段
的“磁带”和“内态”等等赋予任何特别的意义。还有表达可计算性观念
的其他方法，历史上最早的是美国逻辑学家阿伦佐·撤屈在斯蒂芬·C·克
利涅协助下提出的杰出的“拉姆达计算法”。撤屈的步骤和图灵的完全不
同，并且更为抽象得多。事实上，在撤屈陈述他观念的形式中，在它们和
任何可以称作“机械的”东西之间只有一点明显的连接。撤屈步骤背后的
关键观念在其最本质上的确是抽象的，实际上撤屈把这步骤称为“抽象
化”的一个数学运算。
不仅是因为撤屈方案强调可计算性是一个独立于计算机器的任何特别
概念的数学观念，而且它阐明了在数学中抽象观念的威力，所以我感到值
得花一点时间来简要地描述它。对数学观念不熟悉或者对这件事本身不感
好奇的读者，在这一阶段可以跳到下一章去，这不会对论证的过程产生多
少损失。尽管如此，这样的读者若愿意和我多忍受一阵会得到好处，并且
能见证撤屈方案的某些魔术般的经济性（参见撤屈
1941）。
人们在此方案中关心的是，譬如由以下表示的对象的“宇宙”
a，b，c，d，.，z，a′，b′，.，z′，a′′，b′′，.，a′′
′，.，a′′′′，.
其中每一元素代表一个数学运算或函数。（带撇字母的原因简单地是，无
限地提供以表示这种函数的符号。）这些函数的“自变量”，即它们所作
用的东西，是同一类型的其他东西，也就是函数。此外，一个这种函数作
用于另一个函数的结果（或“值”）仍是一个函数。（在撤屈的系统中的
