确具有美妙的概念经济性。）这样，当我们写
a=bc
①一种更熟悉的记号是写成
a=b(c)，但这些特别的括号不是真正必要的，在习惯上把它们忽略去更好些。
时，我们是指函数
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
的级数展开表达式
x－1
x3 + 1
x5 -.。
6 120
然后我们可以定义
11
3 x5]
sin =lx.[x -
6x +
120
－.。
请注意，我们甚至可以更简单地定义，譬如讲“六分之一立方”的运算，
它并没有标准的“函数”记号
Q =l x.[
1
x3]，
6
而且发现，例如
如果把它们一律都保留着，就会导致相当的繁琐，诸如表达式(f(p))(q)和((f(p))(q))(r)可分别简化成(fp)q和
((fp)q)r。
Q a ( + 1) = Q a ( + 1) = (a + 1)3 = 1a3 + 1a2+ 1a + 1 。
6 62 26
从撤屈的基本函数运算简单地构造的表达式对于现在的讨论更为贴切，例
如
λ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〕,
M=λfgx.〔f(gx)〕,
P=λfg.〔fg〕。
读者也许介意使自己或他人信服，我们的确有如下结果：
(Am)n=m+n，(Mm)n=M×n，(Pm)n=n
m，
这儿
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）中描述的一台无限记录机
器）在细节上和图灵原先的相差甚多，而且它们更实用得多。然而，不管
采用那种不同的手段，可计算性的概念仍然相同。
正如许多其他的数学观念，尤其是更美丽的、更基本的那些，可计算
性的观念似乎自身具有某种柏拉图的实在性。在下面两章，我们应该探讨
的正是数学概念的柏拉图实在性的这个神秘问题。
注释
1．1．
2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然
它们对于我们现在的目的不甚方便，数学家却熟知这些方法。例如，公
式
21((a+b) 2+3a+b) 便是用一个单独的自然数来代表一对自然数(a, b) 。
试试看！
3．我在上面没花工夫去引进某种表示起始一个数（或指令等等）的
序列的记号。这对于输入没有必要，由于当遭遇到第一个
1时事情刚刚开
始。然而，对于输出需要某些其他东西，这是由于人们预先为了达到第一
个（也就是最左边的）1不知道要沿着输出磁带看多远。尽管在往左看时
会遇到
0的很长的串，这并不能保证在左边更远处不再有
1。人们对此可
采用不同的观点。其中一种总是用特殊记号（譬如，在收缩步骤中用
6来
编码）去启始整个输出。但是为了简单起见，我在自己的描述中将采用不
同的观点，也就是总“知道”仪器实际上已遭遇到了多长的“磁带”（例
如，人们可以想象，它留下了某种痕迹），在原则上不必去检查无限长的
磁带，就能肯定整个输出已被查过。
4．一种把两盘磁带的信息编码到单独一盘磁带上的方法是插入法。这
样，这盘单独磁带上的奇数号码的记号可代表第一盘磁带的记号，而偶数
号码的记号可代表第二盘磁带的记号。可用类似的方案来处理三盘或更多
盘磁带。这一过程的“低效率”起因于如下事实，即阅读机必须沿着磁带
不断地来回进退，并在上面留下记号以记住在该磁带偶数和奇数部分的什
么地方。
5．这一过程只是指作过记号的磁带可解释作自然数的方法而言。它并
不改变我们特定的图灵机的编号譬如
EUC或
XN+1。
6．如果
Tn/没有被正确地指定，则
U只要在
n的二进位表示中到达多
于四个
1的第一串，就会像
n的数已被终止那样进行下去。它就会把该表
示式的余下部分当成
m的磁带的部分来读，所以它会继续进行某种毫无意
义的计算！如果需要的话，可采用扩展二进位记号来表示
n，这种特征就
能被清除。我决定不这样做，以免使这台可怜的普适机器
U更加复杂！
7．我感谢大卫·德义奇根据以下我得到的
u的二进位形式推导出十进
位形式。我还感谢他检验
u的这个二进位值实际上的确给出了一台普适图
灵机！事实上
u的二进位值为：
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
1000000001011101001101000100101010110100011010001010000011010100
1101000101010010110100001101000101001010110100100111010010100100
10111010l1001110101010010010101110101010011010001010001010110100
有进取心的读者可把一台效率高的家庭用电脑，以正文中给出的方法，应
