可能是完备的。由于哥德尔所关心的形式系统的类型只对算术命题而不是对一般的数学命题足够，所以事实上哥德尔定理比上述的更特定。我们是否能安排只用算术的运算去实现图灵机的所有必须的运算呢？换句话说，是否所有自然数的可计算功能 （也就是图灵机动作的结果，递推的或算法的功能）可按通常的算术表达呢？我们几乎真的可以，但还不是。我们需要在算术和逻辑（包括$和"）的标准法则外加上一个额外的运算。这个运算简单地选择为“使得K （x）成立的最小自然数x”，这儿 K （）是任何给出的算术地可计算的命题函数——并假定存在这样的一个数，也就是$x 〔k （x）〕为真的。（如果没有这样的一个数，则①我们的运算在试图寻求所需的不存在的x 时就会“无限地算下去”。）无论如何，在图灵结果的基础上前面的论证确认了，把数学的一切分支归结为某个形式系统中的计算的希尔伯特规划的确是不成立的。就此而言，这一步骤并没有这么清楚地显示，在这系统中我们具有真的、但不能证明的一个哥德尔命题 （例如P （k））。然而，如果我们回k忆在第二章给出的关于 “如何超过算法”（参阅72 页）的论证，我们就看到了可以做非常类似的事情。我们在那个论证中指出，如果有决定图灵机动作是否停止的任何算法，我们便能制造图灵机的一个动作，我们看到该动作不停止，但是该算法看不到这一点。 （记得我们坚持过，当一台图灵机将要停止时，该算法必须正确地通知我们，虽然在图灵机动作不停止——它会永远运行下去的情形，有时它不能告诉我们。）鉴于上述的哥德尔定理的情形，我们具有利用洞察可以看到实际上必须为真的命题 （图灵机的不停运行），但是给定的算法动作不能告诉我们这些。① “集合”和 “族”之间存在有差异，集合可允许集中在一起而形成另外的集合或族，但是族不能允许集中在一起而形成任何种类的更大的聚合，这被认为 “太大”了。然而除了这种循环的论述，即集合是那种确能聚集成另外聚合的聚合之外，不存在决定何时聚合可被当作集合或只能被当作族考虑的法则。----------------------- Page 121-----------------------递归可列集存在一种按照集论的语言形象地描述图灵和哥德尔基本结果的方法。这就使得我们可以避免按照特别的符号主义或形式系统的任意描述，而使本质问题呈现出来。我们将只考虑 （有限或无限的）自然数的集合0，1，2，3，4，…，这样我们将考察这些聚合，诸如 ｛4，5，8｝， ｛0，57，100003｝，｛6｝，｛0｝，｛1，2，3，4，…，9999｝，｛1，2，3，4，…｝，｛0，2，4，6，8，…｝，甚至整个集合N= ｛0，1，2，3，4，…｝或者空集φ= ｛｝。我们将只关心可计算性的问题，也就是： “自然数的何种集合可由算法产生，何种不能？”为了提出这样的问题，如果愿意的话，我们可把每一单独的自然数n，在一特别的形式系统中，以特定的符号串来表示。按照系统中 （“语法正确”地表达的）命题的某一字典顺序，n表示 “第n个”符号串，譬如讲Q 。则每一自然数代表一个命题。形式系统的所有命题的集合是由整个集n合 N 来代表，例如，形式系统的定理可被认为自然数的某一个更小的集合，例如集合 P。然而，命题的任何特殊编号系统细节不是重要的。为了在自然数和命题之间建立一种对应，我们需要的是能从任一个自然数n得到它对应的 （在一种适当的符号记法中写出的）命题Q 的已知算法，以及从Qn n得到 n 的另一个已知算法。假定已知这两种算法，我们就能随心所欲地把一个特定形式系统的命题集合和自然数集合N相等同。让我们选择一个形式系统，它是协调的，并广泛得足以包括所有图灵机的所有动作——并且在以下的意义上是 “有意义的”，即它的公理和步骤法则可认为是 “自明地真的”。现在，这形式系统的命题Q ，Q ，Q ，0 1 2Q ，…中的一些实际上在该系统中有证明。这些 “可证明的”命题有一些3属于N 的某一个子集的数字，这事实上就是上面考虑的定理的集P。我们事实上已经看到了在某一个给定形式系统中存在一种一个接一个产生具有证明的所有命题的算法。（正如早先概述的， “第n个证明”’ n 是从n算法地得到的。所有我们要做的是去看第n个证明的最后一行，以发现在系统中可证明的第n个命题，也就是第 n个 “定理”。）这样，我们就有了一个接一个 （也许会有重复——但这无所谓）产生P 的元素的算法。一个可用某种算法以这种方式产生的集合，譬如P，叫做递归可列的。注意，在系统中可被证伪——也就是其否定的命题可被证明的命题的集合也类似地为递归可列的，因为我们可简单地列举这可证明的命题。在此过程中取它们的否定。存在许多N 的其他递归可列的集，我们不想介绍把它们定义出来的形式系统。递归可列集的简单例子是偶数。｛0，2，4，6，8，…｝，和平方的集合｛0，1，4，9，16，…｝，----------------------- Page 122-----------------------以及质数的集合｛2，3，5，7，11，…｝。很清楚，我们可以利用算法把这些集中的每一个元素产生出来。在这三个例子中还有这种情形，即集合的补集——也就是不在该集中的自然数的集为递归可列的。三种情形的补集分别为｛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“T （n）停止”n是一道命题——让我把它写作S （n）——也就是对于每一自然数 ，我们n可在我们的形式系统中把它表达出来。对于某些n值命题S （n）是真的，对于另外的 n值它是错的。n跑过自然数0，1，2，3，…时所有 S （n）的----------------------- Page 123-----------------------集合将由N 的某一个子集S 所代表。现在回忆一下图灵的基本结果 （第二章71 页），在 T （n）事实上不停的情形下，不存在作“T （n）不停”断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的补集是递归可列的吗？事实上对所有这些问题的答案都是 “否”。一种看到这一点的方法是注意到形式“T （n）停止”n的错的命题不能由算法产生，正如我们前面所注意到的。所以，错的命题作为整体来说不能由任何算法产生，因为任何这种算法特别会列举出上面所有错的 “T （n）停止”的命题。类似地，不能由一个算法产生所有真的n命题 （由于可轻易地修改任何这种算法以得到所有错误的命题，只要简单地把它产生的每一命题都取一个负命题即可）。由于真的命题因此不是递归可列的 （错的也不能），它们构成了比系统中可证明的命题更复杂和深广得多的陈列。这再一次阐明了哥德尔定理的结论：形式论证只是得到数学真理的部分手段。存在一定的真的算术命题的简单的族，却的的确确能形成递归可列集。例如，不难看出，具有如下形式的真的命题$w，x……，z 〔f （w，x…，z）＝0〕8组成递归可列集 （我把它记作A） 。这儿f （）是由通常的加、减、① 之所以这么称呼直觉主义是因为认为它反映了人类的思维。----------------------- Page 124-----------------------乘、除和升幂等算术运算所构造成的。这种形式命题的一例——虽然我们不知它是否真的——是 “费马最后定理”的否定，此处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 中的情形。----------------------- Page 125-----------------------孟德勒伯洛特集是递归的吗？非递归集必须具有这样的性质，即它们在非常本质的方式上是复杂的。在某种意义上看，它们的复杂性应当公然抵抗任何系统化的企图，否则该系统化就会导致某种适当的算法步骤。对于一个非递归的集合，不存在一般的算法的方式去决定一个元素 （或一“点”）是否属于这个集合。我们在第三章的开头肯定是见证到一个非同寻常地复杂的集合，也就是孟德勒伯洛特集。虽然提供其定义的规则是令人吃惊地简单，但集合本身却呈现出高度繁复的结构和无穷的变化。这难道真的是呈现在我们眼前的非递归集合的例子？然而，读者会很快地指出，现代高速电脑的魔术把这些模式的复杂性呈现于我们的面前。难道电脑不就是算法行为的体现吗？的确，这肯定是对的。但是，我们必须记住电脑实际上产生此图的方式。为了检验阿伽德平面上的一点——一个复数C——是否属于孟德勒伯洛特集 （涂成黑色）或它的补集 （涂成白色），电脑就要从0 开始，然后利用2z—→z +c2 2 4 3 2把0 映射到C，然后从z=C得到 C +C，然后从z=C +C 得到 C +2C +C +C 等2 4 3 2等。如果序列0，C，C +C，C +2C +C +C，…维持有界，则由C代表的点就涂成黑色；否则涂成白色。机器如何告知我们说这样的序列维持有界呢？这个问题原则上牵涉到知道在序列的无限项后会发生什么，这本身不是电脑的事体。幸运的是，若序列是无界的，总存在有限项后就使人们得知的方法。（事实上，只要它达到以原点为中心以1+ 2为半径的圆周就能肯定该序列是无界的。）这样，在一定的意义上讲，孟德勒伯洛特集的补集 （也就是白的区域）是递归可列的。如果复数C 在白的区域中，就有确定此事实的算法。孟德勒伯洛特集本身也就是黑的区域的情况又如何呢？是否有确切告知一个被怀疑处于黑区域的点果真是在黑区域的算法呢？迄今看来这一问题的答案9仍是未知的 。我询问了许多同事和专家，似乎没有人知道存在这样的算法。他们也从未表明过不存在这样的算法。对于黑区域至少还没有已知的算法。孟德勒伯洛特集的补集也许真正是一个递归可列但不是递归的集合！在进一步探索这个设想之前，必须先讨论我掩饰的某些问题。这些问题对于以后讨论物理的可计算性具有某种重要性。我前面的讨论实际上有