接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限 地继续下去，但是只有有限个１。我还假定１的数目为非零（也就是说至 少有一个１）。我们可以选择去读在第一个和最后一个 1（包括在内）之 中的有限的符号串，在上述的情况是为一自然数的二进位写法
１１０１１１００１，
它在十进位表示中为 441。然而，这一过程只能给我们奇数（其二进位表 示以１结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走 最后的１的简单方案（这个１仅仅被当作表示这一程序的终止记号），而 把余下来的当成二进位数来读 5。因此，对于上述的例子，我们有二进位
数
１１０１１１００，
它是十进位的 220。这个步骤具有零也用磁带上的记号代表的好处，也就 是
?００００００１００００００?
我们考虑图灵机 Tn 对我们从右边提供给它的磁带上（有限的）０和１
的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数， 譬如 m 的二进位代表。我们假定，机器 Tn 在进行了一系列的步骤后最终到 达停止（即到达 STOP）。现在机器在左边产生的二进位数串是该计算的答
案。让我们也以同样方式把这当作，譬如是 p 的二进位代表来读。我们把 表达当第 n 台图灵机作用到 m 上时产生 p 的关系写成：
Tn(m)=p。
　　现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一 对数 n 和 m 以得到数 p 的一个特别运算。（这样，若给定两个数 n 和 m， 视第 n 台图灵机对 m 作用的结果而得出 p。）这一特别运算是一个完全算 法的步骤。所以它可由一台特殊的图灵机 U 来执行。也就是说，U 作用到 一对(n，m)上产生 p。由于机器 U 必须作用于 n 和 m 两者以产生单独结果 p， 我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定
n 以通常二进位记号写出并紧接着以序列１１１１１０终结。（我们记得， 任一台正确指明的图灵机的二进位数都是仅仅由０，１０，１１０，１１
１０和１１１１０组成的序列，因此它不包含比四个１更多的序列。这样， 如果 Tn 是正确指明的机器，则１１１１１０的发生的确表明数 n 的描述已 终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表 m 的磁
带（也就是，紧跟二进位数 m 的是１０００?）。这样，这第二个部分简 单地就是 Tn 假设要作用的磁带。
　　作为一个例子，如果我们取 n=11 和 m=6 当作 U 要作用的磁带，其记号 序列为
?０００１０１１１１１１１０１１０１００００? 这是由以下组成的：

?００００（开始的空白带）
１０１１（11 的二进位表示）
１１１１１０（终结 n）
１１０?（6 的二进位表示）
１００００?（余下的磁带）。
在 Tn 作用到 m 上的运算的每一接续的步骤，图灵机 U 要做的是去考察
n 的表达式中的接续数位的结构，以使得在 m 的数位（也就是 Tn 的磁带）
上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人 们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在 每一阶段读到被编码到数 n 中的“表”中，应用到 m 给出的磁带的位数时， 合适元素的手段。肯定在 m 和 n 的数位之间要有许多前前后后的进退，其 过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把 它称为普适图灵机。把该机器对一对数 n 和 m 的作用表为 U(n,m)，我们得 到：
U(n,m)=Tn(m)。
这儿 Tn 是一台正确指明的图灵机 6。当首先为 U 提供数 n 时，它准确地摸
拟第 n 台图灵机！
因为 U 为一台图灵机，它自身也必须有一号码；也就是说，我们有 U=Tu
此处号码 u 待定。u 究竟是多少呢？事实上我们可以准确地给出
u=72448553353393175771983950396157112379523606725565596311081447
9660650505940424109031048361363235936564444345838222688327876762
6556144692814117715017842551707554085657689753346356942478488597
0469347257399885822838277952946834605210611698359459387918855463
2644092552550582055598945189071653741489603309675302043155362503
4984529832320651583047664142130708819329717234151056980262734686
4299218381721573334828230734537134214750597403451843723595930906
4002432107734217885149276079759763441512307958639635449226915947
9654614711345700145048167337562172573464522731054482980784965126
9887889645697609066342044779890219144379328300194935709639217039
0483327088259620130177372720271862591991442827543742235135567513
4084222299889374410534305471044368695876405178128019437530813870
6399427728231564252892375145654438990527807932411448261423572861
9311833261065612275553181020751108533763380603108236167504563585
2164214869542347187426437544428790062485827091240422076538754264
4541334517485662915742999095026230097337381377241621727477236102
0678685400289356608569682262014198248621698902609130940298570600
1743006700868967590344734174127874255812015493663938996905817738

5916540553567040928213322216314109787108145997866959970450968184
1906299443656015145490488092208448003482249207730403043188429899
3931352668823496621019471619107014619685231928474820344958977095
5356110702758174873332729667899879847328409819076485127263100174
0166787363477605857245036964434897992034489997455662402937487668
8397514044516657077500605138839916688140725455446652220507242623
9237921152531816251253630509317286314220040645713052758023076651
83351995689139748137504926429605010013651980186945639498
（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但 是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是 相当合理和简单的，但是在一台实际的普适图灵机的编码中仍然不可避免 地导向这么大的一个数 7。
　　我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说， 这种电脑的逻辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常 相似。其要点可以简述为，首先为任一台普适图灵机提供一段适当的程序
（输入磁带的开始部分）可使它摸拟任何图灵机的行为！在上面的描述中， 程序简单地采取单独的数（数 n）的形式。但是，其他的步骤也是可能的， 图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏 离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。

希尔伯特问题的不可解性


　　我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广 泛的判决问题：是否存在某种回答属于某一广泛的、但是定义得很好的集 合的所有数学问题的机械步骤？图灵发现，他可以把这个问题重述成他的 形式，即决定把第 n 台图灵机作用于数 m 时实际上是否会停止的问题。该 问题被称作停机问题。很容易建造一个指令表使该机器对于任何数 m 不 停。（例如，正如上面的 n=1 或 2 或任何别的在所有地方都没有 STOP 指令 的情形）。也有许多指令表，不管给予什么数它总停（例如 n=11）；有些 机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象 中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算
法。所以一个重要的问题是，决定 Tn 应用在 m 时是否真正地给出答案！如
果它不能（也就是该计算不停止），则就把它写成 Tn(m)=□。
（在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适 的告诉其下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器 T4
和 T7。还有不幸得很，我们粗看起来似乎成功的机器 T3 现在也必须被归于 伪品：T3(m)=□，这是因为 T3 作用的结果总是空白带，而为使计算的结果 可赋予一个数，在输出上至少有一个 1！然而，由于机器 T11 产生了单独的
1，所以它是合法的。这一输出是编号为 0 的磁带，所以对于一切 m，我们 都有 T11(m)=0。）
能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程： (x+1)w+3+(y+1)w+3=(z+1)w+3。
（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个 例子，没有必要详细地理解它。）这一特殊的方程和数学中著名的或许是 最著名的未解决的问题相关。该问题是：存在任何满足这方程的自然数集
合 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 日宣布证明了费马最后定理（译者）。

事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四 数组，直到方程被满足时才停下。（我们已经看到，存在于一根单独磁带 上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这 样，我们只要跟随着这些单独的数的自然顺序就能“跑遍”所有的四数组。） 如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。 可以用类似的办法把许多未解决的数学问题按图灵机停机问题来重 述。“哥德巴赫猜想”即是这样的一个例子，它断言比 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：
?0如果Tn (m) = □
H(n；m) = ?
?1如果Tn (m) 停止。
在这里人们可采取对普适图灵机 U 用过的同样规则给对(n,m)编码。然而， 这会引起如下技术问题，对于某些数 n（例如 n=7），Tn 不是正确指定的，




② 我们记得，质数 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)叫放在 Tn 对 m 作用之前而作到；然后只有如果 H(n；m)=1 时
（也就是说，只有如果计算 Tn(m)实际上给出一个答案时），我们才允许

Tn 作用到 m 上，而如果 H(n；m)=0（也就是如果 Tn(m)=□），则简单地写
为 0。我们可把新的步骤（也就是把 H(n；m)的作用放在 Tn(m)之前得到的）
写成
Tn(m)×H(n；m)。
（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我 们在符号运算上有：□×0=0。）
现在这张表变成：






















我们注意到，假定 H 存在，该表的行由可计算的序列组成。（我用一个可 计算序列表明一个其接连的值可由一个算法产生出来的一个无限序列；也 就是存在一台图灵机，当它依序地应用于自然数 m=0，1，2，3，4，5，? 上时，就得到了这个序列的接续元素。）现在，我们从该表中可以注意到 两个事实。首先自然数的每一可计算序列必须在它的行中出现在某处（也 许出现好几回）。这个性质对于原先的带有□的表已经是真的。我们只不 过是简单地加上一些行去取代“伪品”的图灵机（也就是至少产生一个□ 的那些）。其次，我们已经假定，图灵机 H 实际上存在，该表已被计算地
（也就是用某个确定的算法）由步骤 Tn(m)×H(n；m)产生。换言之，存在
某一台图灵机 Q，当它作用于一对数(n；m)时就会在表中产生合适的元素。 为此我们可以在 Q 的磁带上以和在 H 中一样的方式对 n 和 m 编码。我们得
到
Q(n；m)=Tn(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）=Tn(n)。
但是，如果我们在这个关系中代入 n=k 就得到
1+Tk(k)×H(k；k)=Tk(k)。
因为如果 Tk(k)停止我们就得到了不可能的关系式
1+Tk(k)=Tk(k)，
(由于 H(k；k)=1)，而如果 Tk(k)不停止（这样 H(k；k)=0)，我们有同样
不协调的结果
　　　1+0=□， 所以前面的假定导致一个矛盾。
　　一台特定的图灵机是否停止是一个定义完好的数学问题（反过来，我 们已经看到，各种有意义的数学问题可被重述成图灵机的停机问题）。这 样，依靠显示不存在决定图灵机停机问题的算法，图灵（正如撤屈用自己 十分不同的手段）指出，不存在决定数学问题的一般算法。希尔伯特的判 决问题没有解答！
这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题

的真理或非真理；或者决定某一台给定的图灵机是否会停止。我们可以利 用一些技巧或者仅仅是常识，就能在一定情况下决定这种问题。（例如， 如果一台图灵机的程序表中不包括 STOP 指令，或者只包含 STOP 指令，那 么常识就足以告诉我们它会不会停止！）但是，不存在一个对所有的数学 问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个算 法。
　　我们似乎现在已经建立了，至少存在某些非决定的数学问题。然而， 我们从未做过这种事！我们还没有展示过，存在某种特别尴尬的数时，它 在某种绝对的意义上，不可能决定该机器是否停止。的确，正如我们很快 就要看到的，情况刚好相反。我们关于单独问题的不可解性一点也没提， 仅仅是说关于问题的族的算法的不可解性。在任何单独的情形下，答案或 者为“是”或者为“非”，所以肯定存在一个决定那个特定情形的算法， 也就是在它面临该问题时，依情况而定，会简单地讲“是”或“非”。当 然，困难在于我们可能不知道用这些算法中的哪一个。那就是决定一个单 独陈述而不是决定一族陈述的数学真理的问题。重要的是要意识到，算法 本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起 来。
　　
如何超过算法


　　我们在以后论及哥德尔定理时再回到决定数学陈述的真理性问题（参 阅第四章）。我希望在此刻指出，图灵的论证比我迄今仿佛所暗示的更具 建设性而更少负面性。我们肯定还没有展示出一台特殊的图灵机，它在某 种绝对的意义上不能决定其是否停止的问题。的确，如果我们仔细地考察 该论证就会发现，我们步骤本身实际上已经隐含地告诉我们，对这利用图 灵步骤建造的似乎“极端荒谬”的机器的答案！
　　我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉 我们什么时候一台图灵机将不停止。正如在上面概述的，图灵步骤将明白 地展现了一台图灵机计算，对这计算那个特殊算法不能决定其是否停止。 然而，在这样做的同时，它实际上使我们在这情况下看到了答案！我们展 现的特殊的图灵机计算的确不会停止。
　　为了仔细考查这怎么引起的，假定我们具有一个这样有时有效的算 法。正如以前那样，我们用 H 来标志这个算法（图灵机），但是现在允许 该算法有时不能告诉我们一台图灵机在实际上将不停止：
?0或□如果Tn (m) = □
H(n；m) = ?
?1如果Tn (m) 停止。
这样，当 Tn(m)=□时 H(n；m)=□是一种可能性。实际上存在许多这种算法
H(n；m)。（例如，只要 Tn(m)一停止，H(n；m)就能简单地产生 1，尽管那
个特殊的算法几乎没有什么实际的用处！）
　　除了不把所有的□用 0 来取代而留下一些以外，我们可以像上述那样 仔细地顺着图灵的步骤。正如以前那样，对角线过程提供了对角线上的第
n 个元素
1+Tn(n)×H(n；n)。
（只要 H(n；m)=□，我们就将得到一个□。注意□×□=□，1+□=□。） 这是一个完好的计算，所以它是由某一台，譬如讲第 n 台图灵机得到的， 而且现在我们确实有
1+Tn(n)×H(n；n)=Tk(n)。
我们看第 k 个对角元素，也就是 n=k，就会得到
1+Tk(k)×H(k；k)=Tk(k)。
如果计算 Tk(k)停止，我们就有了一个矛盾（由于假定只要 Tk(k)停止 H(k；
k)就为 1，则方程导致不协调性：1+Tk(k)=Tk(k)。所以 Tk(k)。不能停止，
也就是
Tk(k)=□。
但是，算法不能“知道”这个。因为如果该算法给出 H(k；k)=0，则我们 应该又导致矛盾（我们得到了在符号上不成立的关系：1+0=□)。
这样，如果我们能找到 k，就将知道如何去建造击败我们知道其答案

的算法的特别计算！我们怎么找到 k 呢？这是一项艰巨的工作。我们需要 做的是仔细考察 H（n；m）和 Tn(m)的构造，然后仔细弄清 1+Tn(n)×H(n； n)作为一台图灵机是如何动作的。我们发现这台图灵机的号码为 k。要把
这一切要弄透彻肯定是复杂的，但它是可以办得到的①。由于这种复杂性， 若不是因为我们为了击败H而特地制造Tk(k)的这个事实，我们对计算Tk(k) 毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的 H 是哪一个，
该步骤都能找到合适的 k，使得 Tk(k)击败 H，因此这样我们可以比该算法
做得更好。如果我们认为自己仅仅比算法更好些，也许会给我们带来一些 小安慰！
　　事实上，该过程被定义得如此之好，以至于在给定的 H 下，我们可找 到产生 k 的一个算法。这样，在我们过于得意之前必须意识到，由于这个 算法事实上“知道”Tk(k)=□，所以它能改善 9H，是不是？在上面提到一
个算法时，用拟人化的术语“知道”是有助的。然而，该算法仅仅是跟随 我们预先告诉它去跟随的法则，这难道不是我们在“知道”吗？或者我们 自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去跟 随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为 真何为伪的问题。这是我们必须重新讨论的中心问题。数学真理（以及其 非算法性质）的问题将在第四章考虑。现在我们至少对术语“算法”和“可 计算性”的意义以及某些相关的问题已有些领略。

































① 事实上，由于在上面建造普适图灵机 U 已使我们能把 Tn(n)写成作用于 n 上的一台图灵机，所以已经得
到这个最难的部分。

撤屈拉姆达计算法


　　可计算性的概念是一个非常重要和美丽的数学观念。它又是相当近代 的，具有这样基本性质的事体进入数学的王国是本世纪三十年代的事。这 个观念已经渗透到数学的所有领域中去（虽然这一点确实是真的，但是大 多数数学家通常不去忧虑可计算性的问题）。该观念的威力有一部分来自 于这一个事实，即数学中一些定义得很好的运算实际上不是可计算的（例 如图灵机的停机问题；第四章还可以看到其他例子）。因为如果不存在这 种不可计算的事体，则可计算性的概念便没有多少数学的兴趣。数学家毕 竟喜欢困惑的东西。让他们决定某些数学运算是否为可计算的可能是非常 迷人的困惑。因为那个困惑的一般解答本身是不可计算的，这一点尤其迷 人！
　　有一件事要弄清楚。可计算性是一个真正“绝对的”数学概念。它是 一种抽象的观念，它完全超越按照我们描述的“图灵机”的任何特别实现 之外。正如我在以前所评论的，我们不必对表征图灵的天才而特别的手段 的“磁带”和“内态”等等赋予任何特别的意义。还有表达可计算性观念 的其他方法，历史上最早的是美国逻辑学家阿伦佐·撤屈在斯蒂芬·C·克 利涅协助下提出的杰出的“拉姆达计算法”。撤屈的步骤和图灵的完全不 同，并且更为抽象得多。事实上，在撤屈陈述他观念的形式中，在它们和 任何可以称作“机械的”东西之间只有一点明显的连接。撤屈步骤背后的 关键观念在其最本质上的确是抽象的，实际上撤屈把这步骤称为“抽象 化”的一个数学运算。
　　不仅是因为撤屈方案强调可计算性是一个独立于计算机器的任何特别 概念的数学观念，而且它阐明了在数学中抽象观念的威力，所以我感到值 得花一点时间来简要地描述它。对数学观念不熟悉或者对这件事本身不感 好奇的读者，在这一阶段可以跳到下一章去，这不会对论证的过程产生多 少损失。尽管如此，这样的读者若愿意和我多忍受一阵会得到好处，并且 能见证撤屈方案的某些魔术般的经济性（参见撤屈 1941）。
人们在此方案中关心的是，譬如由以下表示的对象的“宇宙”
a，b，c，d，?，z，a′，b′，?，z′，a′′，b′′，?，a′′
′，?，a′′′′，? 其中每一元素代表一个数学运算或函数。（带撇字母的原因简单地是，无 限地提供以表示这种函数的符号。）这些函数的“自变量”，即它们所作 用的东西，是同一类型的其他东西，也就是函数。此外，一个这种函数作 用于另一个函数的结果（或“值”）仍是一个函数。（在撤屈的系统中的 确具有美妙的概念经济性。）这样，当我们写 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 x 3 ?
6
然后我们可以定义

1
120

x 5 ? ?。

sin ? ?x.[x ? 1 x 3 ?
6

1
120

x 5 －?]。

请注意，我们甚至可以更简单地定义，譬如讲“六分之一立方”的运算， 它并没有标准的“函数”记号
Q ? ?x.[ 1 x 3 ]，
6
而且发现，例如




如果把它们一律都保留着，就会导致相当的繁琐，诸如表达式(f(p))(q)和((f(p))(q))(r)可分别简化成(fp)q 和
((fp)q)r。

Q(a ? 1) ? 1 (a ? 1) 3 ? 1 a 3 ? 1 a2 ? 1 a ? 1 。
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〕,

M=λfgx.〔f(gx)〕, P=λfg.〔fg〕。
读者也许介意使自己或他人信服，我们的确有如下结果： (Am)n=m+n，(Mm)n=M×n，(Pm)n=nm，
　　这儿 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．我是采用当代通常的术语，它现在把零包括在“自然数”之中。
　　2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然 它们对于我们现在的目的不甚方便，数学家却熟知这些方法。例如，公
式 1 ((a + b) 2 + 3a + b)便是用一个单独的自然数来代表一对自然数(a, b)。
2
试试看！
　　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


有进取心的读者可把一台效率高的家庭用电脑，以正文中给出的方法，应 用于不同的简单的图灵机号码中验证上面的号码事实上的确给出了一台普 适图灵机的动作行为！
　　对图灵机的不同明记方法可使 u 的值降低一些。例如，我们可以免除 stop，而相反地采取这样的规则，即只要机器在某个其他非 0 的内态后重 新进入内态 0 时它就停止。这样做没有太多收益（如果有的话）。如果我 们允许磁带有比仅仅 0 和 1 的更多的记号，则能得到更大的收益。在文献 中的确描述过显得非常简洁的普适图灵机。但是，由于它们一般地依赖于 图灵机描述的极其复杂的编码，所以这种简洁性是骗人的。
8．参阅德伏林(1988)的和这一著名断言相关事体的非技术性讨论。
9．我们再次简单地应用前面进行的步骤，当然也能击败这个改善了的

算法。然后我们可以用这新的知识去进一步改善我们的算法；但是我们又 可将其击败等等。这一递归步骤所导致的这类考虑将在第四章第 125 页的 和哥德尔定理联系起来讨论。

第三章数学和实在

托伯列南国


　　想象我们到某一遥远世界作远程旅行。我们称这一遥远世界为托伯列 南国。现在把我们的遥感仪器收集到的信息展现在面前的屏幕上。调好焦 距后就看到了图 3.1。

图 3.1 奇异世界之第一瞥。 它为何物？它是一只形状古怪的昆虫吗？也许它是一个深颜色的并有
许多山溪注入的湖泊。也许它是一座巨大的形状奇特的异国城市，公路沿
着不同方向散开到附近的小镇和乡村去。它也许为一个岛屿——让我们寻 找看在附近是否有和它相连接的陆地。我们可以后退一些，把我们的感觉 仪器的放大倍数减少十五倍左右。嗬，整个世界进入了我们的视界之内（图
3.2）。


图 3.2 整个“托伯列南国”。箭头这下标出了在图 3.1、图 3.3 和图
3.4 中的放大部分的位置。


　　我们在“岛”在图 3.2 中看起来成为标记“图 3.1”下的小斑点。除 了一条连接到右手的裂缝上去的以外，从原先岛上出发的小片断（溪流、 路径、桥梁？）全部都终结了。该裂缝最终接到我们在图 3.2 画出的大得 多的物体上去。这个更大的物体虽然和我们第一次看到的岛不完全一样， 但明显地相似。如果我们更仔细地审视这一物体和海岸线相像的东西，就 发现多得数不清的圆形的瘤状结构。每一结构自身又具有类似的瘤。似乎 每一小瘤都在某一微小的地方附在一个更大的瘤上，由此在大瘤上产生出 许许多多的小瘤。当图像变得更清楚时，人们就看到了从这个结构发出的 成千上万根的细丝。这些细丝在不同的地方分叉并常常剧烈地弯折。在细 丝的某些点，我们似乎看到了具有现有的放大倍数的感觉仪器所不能分析 的复杂扭结。很显然，这物体不是实际的岛屿或陆地，也不是任何风景。 或许我们看到了某种怪诞的甲虫。我们首先看到的是它的婴儿，它用某种 丝线状的脐带安静地把自己连接在母体上面。
　　让我们把感觉仪器的放大倍数提高十倍，再来考察这个怪物的一个瘤 的性质（图 3.3——其位置在图 3.2 中的“图 3.3”的标志的下面）。这个 瘤本身和怪物整体非常相似——除了在接触点以外。请注意在图 3.3 中的 不同地方五根细丝并到一块。这个特定的瘤似乎有一确定的“五性”（正 如在最上面的瘤具有“三性”一样）。如果我们考察下一个相当尺度的瘤， 在图 3.2 中稍微向左下方一点，我们就会在附近发现“七性”，再下一点 为“九性”，并以此类推。当我们进入图 3.2 中的两个最大区域之间的裂
　　
缝，就会发现右边的瘤以奇数来表征，每回增加二。让我们钻到裂缝深处， 把图 3.2 再放大十倍左右（图 3.4）。我们看到其他许多小瘤以及扭转的 结构。在右边称为“海马谷”的区域可鉴别出某些微小的涡旋状的“海马 尾巴”。——如果放大倍数足够大的话，我们就将看到不同的“海乌贼” 或者别具花样的区域。这也许的确是某种奇异的海岸线——也许是所有各 色各样生命产生的珊瑚。看起来像是花的东西在更高的放大倍数下显得是 由成千上万个微小，但同时却是不可思议的复杂的结构组成，每一结构都 有极多的丝状物和扭转的涡旋尾巴。让我们稍微仔细地考察一个较大的海 马的尾巴，也就是在图 3.4 中刚好能见到标志为“图 3.5”的那个（它附 在具有“二十九性”的瘤上面！）。大约再放大 250 倍左右，我们就得到 了画在图 3.5 中的涡旋。我们发现这个尾巴非同寻常，它是由最复杂的、 前后扭曲的、无数的小涡旋以及像章鱼和海马那样的区域组成。


图 3.3 一个具有“五性”的细丝的瘤。


图 3.4 主狭缝：在右下方可见到“海马谷”。 图 3.5 海马尾巴的近窥。

　　图 3.6 两个涡旋会合处的进一步放大细节。在中心点处刚刚可以见到 一个小婴儿。

图 3.7 婴儿在放大之后就显得和整个世界很相似。 在这个结构的许多地方刚好有两个涡旋碰到一起。让我们把放大倍数
增加三十倍左右，以考察其中一处（在图 3.5 中的标志“图 3.6”的下面）。
请注意，我们是否发现了中间有个奇怪但非常熟悉的对象？再放大六倍左 右（图 3.7）就能揭示出一个怪物的小婴儿——它几乎和我们考察过的整 个结构完全一样！如果我们细看，就会发现从它那里出发的细丝和从主结 构那里出来的略有差别。它们扭曲并延伸到更远得多的距离去。然而比细 小结构本身几乎和它的上一代毫无差别，甚至在非常相应的地方拥有自己 的后代。如果我们还进一步放大，就能继续考察这些东西。孙子们又非常 类似于它们的共同祖先——人们很容易相信，这些现象会无限地延续下 去。只要不断地提高我们感觉仪器的放大倍数，就可随心所欲地探索托伯 列南的奇异世界。我们发现了无穷尽的变化：没有两个区域是完全相像的
——但是我们很快就会习惯于存在的一些普遍的风格。而熟知的类甲虫的 结构以越来越小的尺度重新出现。每一回它的附近的细丝结构都和早先看 到的不同，并以不可置信的复杂的美妙的新景象呈现在我们的面前。

　　使我们目瞪口呆地奇异的、变化多端的、美妙的、复杂的国土究竟为 何物呢？许多读者无疑已经知道。但还有一些读者不知道。这世界只不过 是一点抽象数学——称为孟德勒伯洛特集 1 的集合。尽管它无疑是复杂 的，却是由极其简单的规则产生的！为了恰当地解释该规则，我首先得解 释什么是复数。除了这里以外，在将来还有用。它对于量子力学的结构， 所以也就是我们生活其中的世界的运行是绝对基本的。它们构成了数学中 的一个伟大奇迹。为了解释何为复数，首先得提醒读者何为“实数”。另 外，弄清概念和“真实世界”的实在的关系也是非常有益的。
　　
　　　　　　　　　　　　　　实 数


我们知道自然数可被罗列如下：
　　0，1，2，3，4，5，6，7，8，9，10，11，? 这些是不同种类数中最初等和最基本的。任何分立的对象都可以用自然数 予以量化：我们可以讲田地里有二十七只绵羊，可以讲两次闪电，十二个 晚上，一千个词，四次谈话，零个新观念，一个错误，六位缺席者，两次 方向改变等等。自然数可以相加或相乘以得到新的自然数。它便是上一章 给出的关于算法的一般讨论的对象。
　　然而某些重要的运算会把我们带到自然数王国之外——最简单的是减 法。为了系统地定义减法，我们需要负数；为此目的我们建立了整数的整 个系统
　　?，-6，-5，-4，-3，-2，-1，0，1，2，3，4，5，6，7，?。 一定的事物，譬如电荷、银行的存款或者年份①可用这类数来量化。然而， 这些数的范围仍然过于局限。这是由于把一个数除以另一个数时，我们仍 然不能畅通无阻。相应地，我们需要分数或有理数。
0，1，-1，1/2，-1/2，2，-2，3/2，-3/2，1/3，?。 这一些对于有限算术的运算已经足够。但是为了许多更好的目的，我
　　们还得走得更远些，以包括无限或极限运算。例如，大家熟悉的在数学上 极其重要的量π就在许多这类无限的表式中出现。我们有如下特例： π=2｛(2/1)(2/3)(4/3)(4/5)(6/5)(6/7)(8/7)(8/9)?｝
以及
π=4(1-1/3+1/5-1/7+1/9-1/11+?)。
（这些是著名的表式。第一式是由英国数学家、语法学家兼速算家约翰·瓦 里斯在 1655 年首次得到的；而第二式实际上是苏格兰数学家兼天文学家
（以及第一台反射望远镜的发明者）詹姆斯·格里高里在 1671 年得到的。） 正如π那样，以这种方法定义的数不必是有理数（也就是不具有 n/m 的形 式，这里 n 和 m 是整数，m 不为零）。为了包括这样的量，数的系统必须 被推广。
　　这个推广的数的系统被称为“实”数系统——就是那些可以无限小数 展开的熟悉的数，譬如
　　　　-583.70264439121009538? 按照这样的表述，π可写成众所周知的表式
π=3.14159265358979323846? 正有理数的平方根（或立方根或四次方根等等）是还能以这种方法表达的 数的类型，例如