1，Q
2，
Q3，.中的一些实际上在该系统中有证明。这些“可证明的”命题有一些
属于
N的某一个子集的数字，这事实上就是上面考虑的定理的集
P。我们
事实上已经看到了在某一个给定形式系统中存在一种一个接一个产生具有
证明的所有命题的算法。（正如早先概述的，“第个证明”n 是从n
n .
算法地得到的。所有我们要做的是去看第
n个证明的最后一行，以发现在
系统中可证明的第
n个命题，也就是第
n个“定理”。）这样，我们就有
了一个接一个（也许会有重复——但这无所谓）产生
P的元素的算法。
一个可用某种算法以这种方式产生的集合，譬如
P，叫做递归可列的。
注意，在系统中可被证伪——也就是其否定的命题可被证明的命题的集合
也类似地为递归可列的，因为我们可简单地列举这可证明的命题。在此过
程中取它们的否定。存在许多
N的其他递归可列的集，我们不想介绍把它
们定义出来的形式系统。递归可列集的简单例子是偶数。
｛0，2，4，6，8，.｝，
和平方的集合
｛0，1，4，9，16，.｝，
以及质数的集合
以及质数的集合
｛1，3，5，7，9，.｝；
｛2，3，5，6，7，8，10，.｝；
以及
｛0，1，4，6，8，9，10，12，｝。
为这些补集提供算法是轻而易举的事。我们的确可以算法地决定，对於给
定的自然数
n，它是否为偶数，是否为平方或者是否为质数。这就为我们
提供了既产生集合又产生补集的算法，因为我们可以顺序地跑过自然数，
并在每种情况下决定它是否属于原先的集合或它的补集。一个本身及其补
集都是递归可列的集合称为递归集。很清楚递归集的补集仍为递归集。
现在，是否存在递归可列但不是递归的集合呢？我们暂停一下，注意
一下它的推论。由于这种集合的元素可由算法产生，我们就有一种对于怀
疑属于该集合的元素决定其是否真的属于该集合的手段。这一时刻，我们
暂且假定它实际上属于该集合。所有我们要做的是允许我们的算法跑过集
合中的所有元素，直到它最终找到我们所考察的特殊的元素。但是假如我
们怀疑的元素实际上不在这集合中，则我们的算法就无济于事了。由于它
会不断地进行下去，永远得不出一个决断。在这种情形下，我们需要一个
产生补集的算法。如果它发现了我们所怀疑的，则我们肯定地知道该元素
不在这集合中。我们用两种算法就应该是万无一失了。我们可以简单地交
替使用这两种算法，并用任何一种方法找到所怀疑的。然而，这种快乐的
情形只发生在递归集的情形下。我们这里只假定集合为递归可列的而不是
递归的：我们提议的产生补集的算法不存在！这样，我们就面临着这等古
怪的情形，即对于在集合中的一个元素，我们可算法地决定它的确是在这
集合中；但是我们用任何算法都不能保证决定恰巧不在这集合中的元素的
这一个问题！
这种古怪的情形是否发生过呢？也就是说，是否的确存在不是递归的
递归可列集呢？关于集合
P的情况如何呢？它是一个递归集吗？我们已知
它是递归可列的，所以我们必须决定其补集是否也为递归可列的。事实上
它不是！我们何以知道呢？我们知道图灵机的动作被假定为在我们形式系
统中允许的运算。我们用
T
n来标志第
n台图灵机，则陈述
“Tn（n）停止”
是一道命题——让我把它写作
S（n）——也就是对于每一自然数
n，我们
可在我们的形式系统中把它表达出来。对于某些
n值命题
S（n）是真的，
对于另外的
n值它是错的。n跑过自然数
0，1，2，3，.时所有S（n）的
集合将由
N的某一个子集
S所代表。现在回忆一下图灵的基本结果（第二
章
71页），在
T
n（n）事实上不停的情形下，不存在作“T
n（n）不停”断
言的算法。这表明错的S（n）的集合不是递归可列的。
我们观察到
S在
P中的部分刚好包括了那些是真的
S（n）。为什么会
这样子呢？如果任何特别的
S（n）是可证明的，那么它必须是真的（因为
我们已选择了“有意义的”形式系统！），所以
S在
P中的部分必须只包
括真的命题
S，而且没有真的命题
S（n）能处在
P的外头，因为如果
T（n）
停止，那我们便可在这系统内提供证明说它是真的这样①。
现在，假定
P的补集是递归可列的。那我们就应有某种产生这种补集
的算法。我们可以使这些算法运行并在其经过每一命题
S（n）时记下来。
这些都是错的
S（n），所以我们的步骤实际上为我们递归地列举了错的
S
（n）的集合。但是，我们在上面注意到错的
S（n）不是递归可列的。这
一矛盾显示了，P的补集根本不是递归可列的；所以集
P不是递归的，这
就是我们所需要的结果。
这些性质在实际上表明了我们的形式系统不能是完备的，也就是说，
在系统中必有一些既不能证明又不能证伪的命题。因为如果没有这样“不
可决定的”命题，则集
P的补集就必须为可证伪的命题（任何不能证明的
东西都必须为可证伪的）。但是，我们已看到可证伪的命题包含一个递归
可列集，所以这就使得
P成为递归的。然而，P不是递归的，这一个矛盾
导致了不完备性。这就是哥德尔定理的主要突破。
现在关于
N中的代表我们形式系统的真的命题的子集
T能说些什么
呢？T是递归的吗？T是递归可列的吗？T的补集是递归可列的吗？事实上
对所有这些问题的答案都是“否”。一种看到这一点的方法是注意到形式
“Tn（n）停止”
的错的命题不能由算法产生，正如我们前面所注意到的。所以，错的命题
作为整体来说不能由任何算法产生，因为任何这种算法特别会列举出上面
所有错的“T
n（n）停止”的命题。类似地，不能由一个算法产生所有真的
命题（由于可轻易地修改任何这种算法以得到所有错误的命题，只要简单
地把它产生的每一命题都取一个负命题即可）。由于真的命题因此不是递
归可列的（错的也不能），它们构成了比系统中可证明的命题更复杂和深
广得多的陈列。这再一次阐明了哥德尔定理的结论：形式论证只是得到数
学真理的部分手段。
存在一定的真的算术命题的简单的族，却的的确确能形成递归可列
集。例如，不难看出，具有如下形式的真的命题
$wx zfwxz0
，..，〔（，.，）＝〕
组成递归可列集（我把它记作
A）
8。这儿
f（）是由通常的加、减、
①之所以这么称呼直觉主义是因为认为它反映了人类的思维。
乘、除和升幂等算术运算所构造成的。这种形式命题的一例——虽然我们
不知它是否真的——是“费马最后定理”的否定，此处
f可取作
f（w，x，y，z）＝（x＋1）
w+3＋（y＋1）
w+3＋（z＋1）
w+3。
然而，人们发现集合
A不是递归的（这是不容易看到的事实——虽然它是
哥德尔原先论证的一个推论）。这样，我们并没有任何算法手段哪怕在原
则上决定“费马最后定理”的真伪！
我试图在图
4.1中极其概略地把所有具有好的简单的边界的区域代表
一个递归集合，这样人们可以想象，告知某一给定的点是否属于该集是件
直截了当的事。图中的每一点都认为代表一个自然数。而其补集也为一个
显得简单的区域所代表。我在图
4.2中试图用具有复杂边界的集合来代表
递归可列但非递归的集合。此处边界一边的集合——递归可列的那一边—
—被认为比另一边简单。这些图是非常概略的，一点也没有在任何意义上
的“几何准确性”的企图。尤其是用平坦的二维平面来代表这些图像在实
际上没有任何意义。
图
4.1一个递归集的高度概略的图示。
图
4.2一个递归可列的、但不是递归的集合（黑区域）的高度概略的
图示。其思想是，白的区域定义为当可计算地产生的黑的区域被取走后所
“余下的”；断定一点是否在白的区域中不是一个可计算的问题。
图
4.3不同命题集合的高度概略的图示。在系统中可证明的命题集合
P，正如集合
A那样，是递归可列但不是递归的；真的命题集合
T甚至不是
递归可列的。
我在图
4.3中概略地指出了区域
P，T和
A处在集合
N中的情形。
孟德勒伯洛特集是递归的吗？
孟德勒伯洛特集是递归的吗？
然而，读者会很快地指出，现代高速电脑的魔术把这些模式的复杂性
呈现于我们的面前。难道电脑不就是算法行为的体现吗？的确，这肯定是
对的。但是，我们必须记住电脑实际上产生此图的方式。为了检验阿伽德
平面上的一点——一个复数
C——是否属于孟德勒伯洛特集（涂成黑色）
或它的补集（涂成白色），电脑就要从
0开始，然后利用
z—→z2+c
把
0映射到
C，然后从
z=C得到
C
2+C，然后从
z=C
2+C得到
C
4+2C3+C2+C等
等。如果序列
0，C，C
2+C，C
4+2C3+C2+C，.维持有界，则由
C代表的点就
涂成黑色；否则涂成白色。机器如何告知我们说这样的序列维持有界呢？
这个问题原则上牵涉到知道在序列的无限项后会发生什么，这本身不是电
脑的事体。幸运的是，若序列是无界的，总存在有限项后就使人们得
知的方法。（事实上，只要它达到以原点为中心以1+ 2为半径的圆周就
能肯定该序列是无界的。）
这样，在一定的意义上讲，孟德勒伯洛特集的补集（也就是白的区域）
是递归可列的。如果复数
C在白的区域中，就有确定此事实的算法。孟德
勒伯洛特集本身也就是黑的区域的情况又如何呢？是否有确切告知一个被
怀疑处于黑区域的点果真是在黑区域的算法呢？迄今看来这一问题的答案
仍是未知的
9。我询问了许多同事和专家，似乎没有人知道存在这样的算
法。他们也从未表明过不存在这样的算法。对于黑区域至少还没有已知的
算法。孟德勒伯洛特集的补集也许真正是一个递归可列但不是递归的集
合！
在进一步探索这个设想之前，必须先讨论我掩饰的某些问题。这些问
题对于以后讨论物理的可计算性具有某种重要性。我前面的讨论实际上有
些不精确。我把诸如“递归可列的”和“递归的”这样的术语应用于阿伽
德平面也就是复数的集合上。严格地讲，这些术语只能适用于自然数或其
他可列的集合。我们已经在第三章（98页）看到实数是不可列的，所以复
数也不是可列的——由于实数可考虑作特殊种类的复数，也就是虚部为零
的复数。事实上，刚好存在和实数“一样多”数目的复数，也就是
C那么
多。（粗略地讲，为了建立复数和实数之间的一一对应，我们可以把每一
复数的实虚部各作小数展开，然后将其交叉地塞到相应实数的奇数和偶数
位上去：例如复数
3.6781.+i512.975.对应于实数
50132.6977851.。）
逃避这个问题的一种办法是只管可计算的复数。我们在第三章看到，
可计算的实数——并因此可计算的复数——的确是可列的。然而，这里有
严重的困难：事实上不存在决定两个按照它们相应的算法给出的可计算数
是否相等的一般算法！（我们可以算法地形成它们的差，但我们不能算法
地决定这个差是否为
0。想象两个分别产生
0.99999.和
1.00000.的算
法，我们也许永远不会知道这些
9和
0是否无限地继续下去，因此这两个
数相等，或最终某些其他的数会出现，因此这两个数不等。）这样，我们
也许永远不能知道这些数是否相等。其中的一个含义是，甚至对诸如阿伽
德平面上的单位圆盘这么简单的集合（所有到原点的距离不大于一个单位
的点的集合，也就是图
4.4中的黑的区域）都没有决定复数是否实际上处
于圆上的算法。当点在内部（或在外部）时不会引起这个问题，但点处于
圆盘的边缘时，也就是在单位圆本身上时就有了问题。单位圆被认为是圆
盘的部分。假定我们简单地给出产生某复数的实部和虚部的位数的算法。
如果我们怀疑该复数实际上处于单位圆上，我们并不能肯定这个事实。不
存在去决定可计算数
x2+y2
是否实际上等于或不等于
1的算法，也就是决定该可计算复数
x+iy是否在
单位圆上的判据。
图
4.4单位圆盘肯定被当作“递归的”，但是这里需要一个适当的观
点。
这肯定不是我们所需要的。单位圆盘当然必须被当作递归的！没有很
多集合比单位圆盘更简单！一种躲避这一问题的办法是不理睬边界。对实
际上处于内部或外部的点肯定存在确认这些事实的算法。（简单地一个接
一个地产生
x
2+y2的数位，最终会发现在小数展开
0.99999.后面出现非
9
或
1.00000.后面出现非
0）。在这个意义上讲，单位圆盘是递归的。但是，
这种观点是相当粗劣的，因为人们经常需要按照在边界上的行为来进行论
证。另一方面，这种观点或许对物理学是合适的。我们以后还要再考虑这
些问题。
人们或许还会采用另一种紧密相关的观点，它根本未涉及可计算复数
的问题。我们简单地要求可对给定的复数决定其是否在该集中或在补集中
的算法，而不试图去列举该问题的集外或集内的复数。我在这里的“给定”
的意义是，对于我们检验的每一个复数，也许用某种魔术的办法，实部和
虚部的连续位数可一个接一个地写出以供使用，要多长就有多长。我不要
求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集
合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集
中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说
“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一
样，这种观点“不理睬”边界。这样，单位圆盘的内部和外部分别都在这
个意义上被当作递归可列的，而边界本身不是。
求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集
合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集
中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说
“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一
样，这种观点“不理睬”边界。这样，单位圆盘的内部和外部分别都在这
个意义上被当作递归可列的，而边界本身不是。
需
10。把它应用到孟德勒伯洛
特集时，“不理睬边界”的哲学可能将该集合的许多复杂性都损失了。该
集合一部分包括具有内部区域的“点”，还有部分是“卷须”。其极端复
杂性似乎存在于极其剧烈地弯曲的卷须之中。然而，卷须不在集合的内部，
所以如果我们采用了上述的任一种哲学，则这些卷须都被忽略了。尽管如
此，当只考虑斑点时，仍然不清楚孟德勒伯洛特集是否为“递归的”。这
个问题似乎依赖于某个未被证明的有关孟德勒伯洛特集的猜测：它是所谓
的“局部连通”的吗？我不想在此解释此术语的意义及其关联之处。我只
想指出这些是困难的问题，它们引起了有关孟德勒伯洛特集的未解决的问
题，而且其中一些正是当前某些数学研究的最前沿的问题。
为了绕过复数是不可列的问题，人们还可以采用其他的观点。人们不
去考虑所有可计算的复数，而去考虑这样的一个适当的子集，该子集的数
具有去决定其中两个数相等与否仍是可计算的问题的性质。“有理”复数
即为这样的一种简单的子集，实部和虚部均为有理数的复数即为有理复
数。我认为它并不在孟德勒伯洛特集中占多少，而这种观点又是非常局限
的。考虑代数数也许会更令人满意些——这就是那些为整系数的代数方程
的解的那些复数。例如，方程
129z7－33z
5+725z4+16z3－2z－3=0
所有
z的解为代数数。代数数是可列的并且是可计算的。实际上去决定它
们中的两个是否相等正是可计算的问题。（它们其中许多处于单位圆的边
界和孟德勒伯洛特集的须蔓上。）如果需要的话，我们可把这问题表述成，
孟德勒伯洛特集按照它们是否为递归的。
在刚才考虑的两个集合的情况下代数数也许是合适的，但它实在不能
一般地解决我们所有的困难。考虑由关系
y≥ex
所定义的集合（图
4.5中的黑的区域）。这里
z=x+iy是阿伽德平面上的点。
按照上面所表述的任何观点，该集合的内部以及其补集的内部，都是递归
可列的。但是（从
F·林德曼在
1882年证明的一个著名定理）边界
y=e
x，
只包含一个代数点，即
z=i。代数数对于这种情形下的边界的算法性质的
研究毫无用处！不难去寻找其他的可计算数的子集以对付这特殊情形，但
人们会强烈地感到，我们还没得到正确的观点。
