若不是因为我们为了击败H而特地制造T (k)的这个事实，我们对计算T (k)
k k
毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的H 是哪一个，
该步骤都能找到合适的 k，使得T (k)击败H，因此这样我们可以比该算法
k
做得更好。如果我们认为自己仅仅比算法更好些，也许会给我们带来一些
小安慰！
事实上，该过程被定义得如此之好，以至于在给定的H 下，我们可找
到产生 k 的一个算法。这样，在我们过于得意之前必须意识到，由于这个
9
算法事实上 “知道”T (k)=□，所以它能改善 H，是不是？在上面提到一
k
个算法时，用拟人化的术语 “知道”是有助的。然而，该算法仅仅是跟随
我们预先告诉它去跟随的法则，这难道不是我们在 “知道”吗？或者我们
自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去跟
随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为
真何为伪的问题。这是我们必须重新讨论的中心问题。数学真理 （以及其
非算法性质）的问题将在第四章考虑。现在我们至少对术语“算法”和“可
计算性”的意义以及某些相关的问题已有些领略。
① 事实上，由于在上面建造普适图灵机U 已使我们能把Tn(n)写成作用于n 上的一台图灵机，所以已经得
到这个最难的部分。
----------------------- Page 75-----------------------
撤屈拉姆达计算法
可计算性的概念是一个非常重要和美丽的数学观念。它又是相当近代
的，具有这样基本性质的事体进入数学的王国是本世纪三十年代的事。这
个观念已经渗透到数学的所有领域中去 （虽然这一点确实是真的，但是大
多数数学家通常不去忧虑可计算性的问题）。该观念的威力有一部分来自
于这一个事实，即数学中一些定义得很好的运算实际上不是可计算的 （例
如图灵机的停机问题；第四章还可以看到其他例子）。因为如果不存在这
种不可计算的事体，则可计算性的概念便没有多少数学的兴趣。数学家毕
竟喜欢困惑的东西。让他们决定某些数学运算是否为可计算的可能是非常
迷人的困惑。因为那个困惑的一般解答本身是不可计算的，这一点尤其迷
人！
有一件事要弄清楚。可计算性是一个真正 “绝对的”数学概念。它是
一种抽象的观念，它完全超越按照我们描述的 “图灵机”的任何特别实现
之外。正如我在以前所评论的，我们不必对表征图灵的天才而特别的手段
的 “磁带”和“内态”等等赋予任何特别的意义。还有表达可计算性观念
的其他方法，历史上最早的是美国逻辑学家阿伦佐·撤屈在斯蒂芬·C ·克
利涅协助下提出的杰出的 “拉姆达计算法”。撤屈的步骤和图灵的完全不
同，并且更为抽象得多。事实上，在撤屈陈述他观念的形式中，在它们和
任何可以称作 “机械的”东西之间只有一点明显的连接。撤屈步骤背后的
关键观念在其最本质上的确是抽象的，实际上撤屈把这步骤称为 “抽象
化”的一个数学运算。
不仅是因为撤屈方案强调可计算性是一个独立于计算机器的任何特别
概念的数学观念，而且它阐明了在数学中抽象观念的威力，所以我感到值
得花一点时间来简要地描述它。对数学观念不熟悉或者对这件事本身不感
好奇的读者，在这一阶段可以跳到下一章去，这不会对论证的过程产生多
少损失。尽管如此，这样的读者若愿意和我多忍受一阵会得到好处，并且
能见证撤屈方案的某些魔术般的经济性 （参见撤屈1941）。
人们在此方案中关心的是，譬如由以下表示的对象的 “宇宙”
a，b，c，d，…，z，a′，b′，…，z′，a′′，b′′，…，a′′
′，…，a′′′′，…
其中每一元素代表一个数学运算或函数。 （带撇字母的原因简单地是，无
限地提供以表示这种函数的符号。）这些函数的 “自变量”，即它们所作
用的东西，是同一类型的其他东西，也就是函数。此外，一个这种函数作
用于另一个函数的结果 （或“值”）仍是一个函数。（在撤屈的系统中的
确具有美妙的概念经济性。）这样，当我们写 a=bc
① 一种更熟悉的记号是写成a=b(c)，但这些特别的括号不是真正必要的，在习惯上把它们忽略去更好些。
----------------------- Page 76-----------------------
时，我们是指函数b作用于函数 c 的结果为另一函数a。要在这个方案中
表达两个或更多变量的函数的观念并没有困难。如果我们希望把f 认为两
个变量，譬如讲p和q 的函数，我们可以简单地写
(fp)q
（这是函数fp作用于 q 的结果）。对于三变量函数我们考虑
((fp)q)r，
等等。
让我们引进抽象化的有力的运算。为此我们使用希腊字母λ （拉姆
达），而且有它后面紧跟着的是代表一个撤屈函数的一个字母，譬如讲x，
我们把它当成 “哑变量”。任何发生于紧跟在这后面的方括号内的表达式
中的变量x 是仅仅被当作一个 “口”，可以往里面代入任何跟在整个表达
式后的任何东西。这样，如果我们写
λx． 〔fx〕，
我们是说，当它作用到譬如讲函数a 上时，就产生结果fa。那就是
(λx． 〔fx〕)a=fa。
换言之，λx． 〔fx〕简单地就是函数f,即
λx． 〔fx〕=f。
这里只用一点思维就够了。数学的一个美妙在于，初看起来是如此卖
弄学识的、琐碎的东西，也是人们非常容易完全失去要点的东西。让我们
考虑从中学数学取来的一个熟悉的例子。我们取函数f 为对一个角度取正
弦的三角运算，这样抽象的函数 “sin”被定义为
λx． 〔sinx〕=sin。
（不必为何以“函数”x 可当作一个角度而忧虑。我们很快就会看到数可
被当成函数的某种方法；而一个角度只是一个数。）迄今为止的一切的确
是相当无聊的。让我们设想，记号“sin”还没被发明，但是我们熟悉sinx
的级数展开表达式
1 3 1 5
x－ x + x - …。
6 120
然后我们可以定义
1 3 1 5
sin = lx.[x - x + x －…]。
6 120
请注意，我们甚至可以更简单地定义，譬如讲 “六分之一立方”的运算，
它并没有标准的 “函数”记号
1 3
Q = lx.[ x ]，
6
而且发现，例如
如果把它们一律都保留着，就会导致相当的繁琐，诸如表达式(f(p))(q)和((f(p))(q))(r)可分别简化成(fp)q 和
((fp)q)r。
----------------------- Page 77-----------------------
1 3 1 3 1 2 1 1
Q(a + 1) = (a + 1) = a + a + a + 。
6 6 2 2 6
从撤屈的基本函数运算简单地构造的表达式对于现在的讨论更为贴切，例
如
λf. 〔f(fx)〕。
这是一个函数，当它作用于另一函数，譬如讲 g 时，产生g 两次递归地作
用于x 上的函数，也就是
(λf. 〔f(fx)〕)g=g(gx)。
我们也可以首先 “抽象化走”x 以得到
λf. 〔λx. 〔f(fx)〕〕,
此式可以缩写成
λfx 〔f(fx)〕。
这是当作用于 g 时产生 “g被递归两次”的函数。事实上，这正是撤屈将
其和自然数2相等同的函数。
2=λfx． 〔f(fx)〕，
这样，(2g)y=g(gy)。他类似地定义：
3=λfx． 〔f(f(fx))〕，4
=λfx 〔f(f(f(fx))〕，等等，
以及
1=λfx． 〔fx〕，0=λfx， 〔x〕。
撤屈的 “2”真的更像 “两次”，它的“3”是 “三次”等等。这样3在一
个函数f 上的作用，也就是3f 是 “把f递归三次”的运算。因此，3f在y
上的作用是 （3f)y=f(f(f （y)))。
让我们看看，一个非常简单的算术运算，也就是如何把 1加到一个数
上的运算在撤屈方案中表达出来。定义
S=λabc． 〔b((ab)c)〕。
为了阐明S 的确简单地把１加到用撤屈记号表示的一个数上，让我们做这
样的检验：
S3=λabc． 〔b((ab)c)〕3=λbc．〔b((3b)c)〕=λbc. 〔b(b(b(bc)))〕
=4，
这是由于(3b)c=b(b(bc))。很清楚，这可同样好地适用于任何其他自然数。
（事实上λabc． 〔(ab)(bc)〕可以和S 一样好地做到。）
把一个数乘二又如何呢？这种加倍可由
D=λabc． 〔(ab)((ab)c)〕
获得，它可再次由作用于３上而得到验证：
D=λabc. 〔(ab)((ab)c)〕3=λabc. 〔(3b)((3b)c)〕
=λabc. 〔(3b)(b(b(bc)))〕=λabc. 〔b(b(b(b(b(bc)))))〕=6。
事实上，加法、乘法和升幂的基本算术运算可分别定义为
A=λfgxy. 〔((fx)(gx))y〕,
----------------------- Page 78-----------------------
M=λfgx. 〔f(gx)〕,
P=λfg. 〔fg〕。
读者也许介意使自己或他人信服，我们的确有如下结果：
m
(Am)n=m+n，(Mm)n=M×n，(Pm)n=n ，
这儿m 是n 是撤屈的两个自然数的函数，m+n 是它们和的相应函数，
等等。最后那个公式是最令人惊异的。让我们仅仅检验其m=2，n=3 的情形：
(p2)3=((λfg. 〔fg〕)2)3=(λg. 〔2g〕)3
=(λg. 〔λfx. 〔f(fx)〕g〕)3
=λgx. 〔g(gx)〕3=λx. 〔3(3x)〕
=λx. 〔λfy. 〔f(f(fy))〕(3x)〕
=λxy. 〔(3x)((3x)((3x)y))〕
=λxy. 〔(3x)((3x)(x(x(xy)))))〕
=λxy. 〔(3x)(x(x(x(x(xy)))))〕
=λxy. 〔x(x(x(x(x(x(x(x(xy))))))))〕
=9=32
减法和除法不是这么容易定义的 （我们的确需要某种当m 比n 小时
“m-n”以及当m 不能被n整除时 “m÷n”的惯例。事实上，二十世纪三十
年代早期克利涅发现如何在撤屈的方案中表达减法运算被认为是这一学科
的重要里程碑！后来接着又有其他的运算。最后，撤屈和图灵在1937年独
立地指出，不管什么样的可计算的 （或算法的）运算（现在在图灵机的意
义上）都可以按照撤屈的一种表达式获得 （而且反之亦然）。
这是一个真正惊人的事实，它被用来强调可计算性思想的基本客观性
以及数学特征。初看起来，撤屈的可计算性概念和计算机器没有什么关系。
然而，它和实际计算具有某些基本关系。尤其是，有力而灵活的电脑LISP
语言以一种根本的方式参与到撤屈计算法的基本结构中来。
正如我早先指出的，还有其他定义可计算性概念的方法。波斯特的计
算机器的概念和图灵的非常接近，并且几乎是同时独立提出的。近世还有
更有用的可计算性 （递归性）的定义，这是J ·赫伯拉德和哥德尔提出的。
H ·B ·邱雷在1929年，以及M ·轩芬克勒在1924年稍早些时候提出了不
同的方法，撤屈计算法就是部分地由此发展而来 （参见甘迪1988）。现在
研究可计算性的手段 （诸如在（卡特兰1980）中描述的一台无限记录机
器）在细节上和图灵原先的相差甚多，而且它们更实用得多。然而，不管
采用那种不同的手段，可计算性的概念仍然相同。
正如许多其他的数学观念，尤其是更美丽的、更基本的那些，可计算
性的观念似乎自身具有某种柏拉图的实在性。在下面两章，我们应该探讨
的正是数学概念的柏拉图实在性的这个神秘问题。
注 释
----------------------- Page 79-----------------------
1．我是采用当代通常的术语，它现在把零包括在 “自然数”之中。
2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然
它们对于我们现在的目的不甚方便，数学家却熟知这些方法。例如，公
1 2
式 ((a + b) + 3a + b)便是用一个单独的自然数来代表一对自然数(a,b) 。
2
试试看！
3．我在上面没花工夫去引进某种表示起始一个数 （或指令等等）的
序列的记号。这对于输入没有必要，由于当遭遇到第一个 1时事情刚刚开
始。然而，对于输出需要某些其他东西，这是由于人们预先为了达到第一
个 （也就是最左边的）1不知道要沿着输出磁带看多远。尽管在往左看时
会遇到0 的很长的串，这并不能保证在左边更远处不再有 1。人们对此可
采用不同的观点。其中一种总是用特殊记号 （譬如，在收缩步骤中用6来
编码）去启始整个输出。但是为了简单起见，我在自己的描述中将采用不
同的观点，也就是总 “知道”仪器实际上已遭遇到了多长的“磁带”（例
如，人们可以想象，它留下了某种痕迹），在原则上不必去检查无限长的
磁带，就能肯定整个输出已被查过。
4．一种把两盘磁带的信息编码到单独一盘磁带上的方法是插入法。这
样，这盘单独磁带上的奇数号码的记号可代表第一盘磁带的记号，而偶数
号码的记号可代表第二盘磁带的记号。可用类似的方案来处理三盘或更多
盘磁带。这一过程的 “低效率”起因于如下事实，即阅读机必须沿着磁带
不断地来回进退，并在上面留下记号以记住在该磁带偶数和奇数部分的什
么地方。
5．这一过程只是指作过记号的磁带可解释作自然数的方法而言。它并
不改变我们特定的图灵机的编号譬如EUC或XN+1。
6．如果T 没有被正确地指定，则 U 只要在n 的二进位表示中到达多
n/
于四个 1 的第一串，就会像n 的数已被终止那样进行下去。它就会把该表
示式的余下部分当成m 的磁带的部分来读，所以它会继续进行某种毫无意
义的计算！如果需要的话，可采用扩展二进位记号来表示n，这种特征就
能被清除。我决定不这样做，以免使这台可怜的普适机器U 更加复杂！
