1，Q2，Q3，.中的一些实际上在该系统中有证明。这些“可证明的”命题有一些属于N的某一个子集的数字，这事实上就是上面考虑的定理的集P。我们事实上已经看到了在某一个给定形式系统中存在一种一个接一个产生具有证明的所有命题的算法。（正如早先概述的，“第个证明”n 是从nn .算法地得到的。所有我们要做的是去看第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的情况如何呢？它是一个递归集吗？我们已知它是递归可列的，所以我们必须决定其补集是否也为递归可列的。事实上它不是！我们何以知道呢？我们知道图灵机的动作被假定为在我们形式系统中允许的运算。我们用Tn来标志第n台图灵机，则陈述“Tn（n）停止”是一道命题——让我把它写作S（n）——也就是对于每一自然数n，我们可在我们的形式系统中把它表达出来。对于某些n值命题S（n）是真的，对于另外的n值它是错的。n跑过自然数0，1，2，3，.时所有S（n）的集合将由N的某一个子集S所代表。现在回忆一下图灵的基本结果（第二章71页），在Tn（n）事实上不停的情形下，不存在作“Tn（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）停止”的错的命题不能由算法产生，正如我们前面所注意到的。所以，错的命题作为整体来说不能由任何算法产生，因为任何这种算法特别会列举出上面所有错的“Tn（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得到C2+C，然后从z=C2+C得到C4+2C3+C2+C等等。如果序列0，C，C2+C，C4+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单位圆盘肯定被当作“递归的”，但是这里需要一个适当的观点。这肯定不是我们所需要的。单位圆盘当然必须被当作递归的！没有很多集合比单位圆盘更简单！一种躲避这一问题的办法是不理睬边界。对实际上处于内部或外部的点肯定存在确认这些事实的算法。（简单地一个接一个地产生x2+y2的数位，最终会发现在小数展开0.99999.后面出现非9或1.00000.后面出现非0）。在这个意义上讲，单位圆盘是递归的。但是，这种观点是相当粗劣的，因为人们经常需要按照在边界上的行为来进行论证。另一方面，这种观点或许对物理学是合适的。我们以后还要再考虑这些问题。人们或许还会采用另一种紧密相关的观点，它根本未涉及可计算复数的问题。我们简单地要求可对给定的复数决定其是否在该集中或在补集中的算法，而不试图去列举该问题的集外或集内的复数。我在这里的“给定”的意义是，对于我们检验的每一个复数，也许用某种魔术的办法，实部和虚部的连续位数可一个接一个地写出以供使用，要多长就有多长。我不要求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一样，这种观点“不理睬”边界。这样，单位圆盘的内部和外部分别都在这个意义上被当作递归可列的，而边界本身不是。求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一样，这种观点“不理睬”边界。这样，单位圆盘的内部和外部分别都在这个意义上被当作递归可列的，而边界本身不是。需10。把它应用到孟德勒伯洛特集时，“不理睬边界”的哲学可能将该集合的许多复杂性都损失了。该集合一部分包括具有内部区域的“点”，还有部分是“卷须”。其极端复杂性似乎存在于极其剧烈地弯曲的卷须之中。然而，卷须不在集合的内部，所以如果我们采用了上述的任一种哲学，则这些卷须都被忽略了。尽管如此，当只考虑斑点时，仍然不清楚孟德勒伯洛特集是否为“递归的”。这个问题似乎依赖于某个未被证明的有关孟德勒伯洛特集的猜测：它是所谓的“局部连通”的吗？我不想在此解释此术语的意义及其关联之处。我只想指出这些是困难的问题，它们引起了有关孟德勒伯洛特集的未解决的问题，而且其中一些正是当前某些数学研究的最前沿的问题。为了绕过复数是不可列的问题，人们还可以采用其他的观点。人们不去考虑所有可计算的复数，而去考虑这样的一个适当的子集，该子集的数具有去决定其中两个数相等与否仍是可计算的问题的性质。“有理”复数即为这样的一种简单的子集，实部和虚部均为有理数的复数即为有理复数。我认为它并不在孟德勒伯洛特集中占多少，而这种观点又是非常局限的。考虑代数数也许会更令人满意些——这就是那些为整系数的代数方程的解的那些复数。例如，方程129z7－33z5+725z4+16z3－2z－3=0所有z的解为代数数。代数数是可列的并且是可计算的。实际上去决定它们中的两个是否相等正是可计算的问题。（它们其中许多处于单位圆的边界和孟德勒伯洛特集的须蔓上。）如果需要的话，我们可把这问题表述成，孟德勒伯洛特集按照它们是否为递归的。在刚才考虑的两个集合的情况下代数数也许是合适的，但它实在不能一般地解决我们所有的困难。考虑由关系y≥ex所定义的集合（图4.5中的黑的区域）。这里z=x+iy是阿伽德平面上的点。按照上面所表述的任何观点，该集合的内部以及其补集的内部，都是递归可列的。但是（从F·林德曼在1882年证明的一个著名定理）边界y=ex，只包含一个代数点，即z=i。代数数对于这种情形下的边界的算法性质的研究毫无用处！不难去寻找其他的可计算数的子集以对付这特殊情形，但人们会强烈地感到，我们还没得到正确的观点。