第四章 真理、证明和洞察 

数学的希尔伯特规划 
  
　 
  
　　什么是真理？我们如何对世界的真伪形成判断呢？我们是否简单地遵循着某些算法 
？这种算法由于自然选择的强有力的过程无疑地比其他效率更低的可能算法更加优越。 
或许还有其他探索真理的非算法的途径��直觉、禀性或洞察。这似乎是一个困难 
的问题。我们的判断是基于感觉数据、推理和猜测的盘根错节的结合。而且，在世间的 
许多情势中也许并没有何为真何为伪的共识。为了使问题简化，让我们只考虑数学真理 
。我们如何形成自己关于数学问题的判断或许“某些”知识呢？在这儿事情至少应该是 
更明了些。关于究竟什么为真什么为伪在这里不应成为问题一一难道会有问题吗？究竟 
什么是数学的真理呢？ 
  
　　数学的真理是一个非常古老的问题，这可回溯到早期的希腊哲学家和数学家的时代- 
-并毫无疑问地比这还要更早。但是，只有在一百多年前 
  
　　　 
  
　　们想要理解的正是这些非常基本的问题。它触及了我们的思维过程在性质上是否完 
全算法的问题。去应付这些问题是非常重要的。 
  
　　数学在十九世纪下半叶有了伟大的进展，其部分原因在于人们发展了数学证明的越 
来越有力的方法。（我们在前面提到的大卫·希尔伯特和乔治·康托，还有将要提到的 
伟大的法国数学家亨利·彭加莱是处于发展最前沿的三位。）数学家在利用如此有力的 
方法时相应地获得自信心。其中许多方法涉及到去考虑具有无限数目的元素的集合①。 
正是由于可能将这样的集合当成实在的“东西”--完全存在的整体，而不仅仅为潜在的 
存在，使证明经常得到成功。这许多强有力的观念是从康托的高度创造性的无限数的概 
念中孕育而来的。他利用无限集合系统地发展了这一切。（我们在上一章对此有所领略 
。） 
  
　　然而，1902年英国逻辑学家兼哲学家贝特朗·罗素提出其著名的佯谬，完全粉碎了 
这种自信心。（康托已预示过这一佯谬，并且它是康托“对角线删除法”的直系后代） 
。为了理解罗素的论证，我们首先对把许多集合当作完整的整体来考虑应有些了解。我 
们可以想象，某些集合是按照一个特殊的性质来表征的。例如，红的东西的集合是根据 
红性来表征的：就是说唯有当某物具有红性时才属于该集合。这样就允许我们把事情倒 
过来，按照单独对象也就是具有同一性质的事物的整个集合来谈论该性质。依照这种观 
点，“红性”是所有红的东西的集合。（我们还可以认为某一其他的集合就在“那里” 
，它们的元素为稍微复杂的性质所表征。） 
  
　　这种按照集合定义概念的思想是1884年由具有影响的德国逻辑学家哥特洛伯·弗列 
格引进的步骤的核心。他可按照集合来定义数。例如，实际的数3是什么意思呢？我们知 
道“三性”是什么性质，但是3本身是什么？现在“三性”是一群对象的性质，也就是一 
个集合的性质：惟有如果当该集合不多不少有三个成员，则它具有“三性”的特别性质 
。例如，在特定的奥林匹克比赛中，奖章获得者的集合具有“三性”。还有三轮车的轮 
子集合。正常三叶草的叶的集合或者方程x3-6x2+11x-6=0的解的集合。那么，弗列格关 
于实在的数3的定义是什么呢？依照弗列格的论点，3必须是一个集合的集合：即所有具 
有“三性”1的集合的集合。这样，一个集合如果也只有如果属于弗列格集3，才具有三 
个成员。 
  
　　　 
  
　　为对等集合的总体，这儿对等的意思是讲“具有能一一配对的元素”（用通常的术 
语也就是“具有同样多的成员”）。数3就是这些集合的一个特例，其中的一个成员可以 
是包括一个苹果、一个桔子和一个梨的集合。请注意，这和彻屈在78页给出的“3”的定 
义完全不同。还可以给出其他今日相当流行的定义。 
  
　　那么，罗素佯谬又是怎么回事呢？它是关于以如下方式定义的集合R： 
  
　　R是一自身并非其元素的所有集合的集合。 
  
　　这样，R是集合的某一整体；集X属于该整体的判据是集X自身不是它自身的成员。 
  
　　假定一个集合可以实际是它自身的一个成员，这是否非常荒谬？不见得。例如，考 
虑一个无限集合（具有无限元素的集合）的集合I。肯定存在无限多不同的无限集，这样 
I自身也是无限的。这样I确实属于自身！那么，罗素的概念又如何导致佯谬呢？我们问 
：罗素集合是它自身的一个成员或者不是它的成员？如果它不是它自身的成员，则它必 
须属于R，因为R刚好包括那些不是自身成员的集合。这样，R毕竟属于--这是矛盾。另一 
方面，如果R是它的一个成员，那么由于“自身”实际上就是R，它就属于由自身并非其 
成员所表征的集合中，也就是它根本不是自身的成员--又导致矛盾①！ 
  
　　这种考虑并不轻率。罗素只不过以相当极端的形式利用数学家们正开始在证明中使 
用的、非常一般的、数学集论的同一类型的推理。事情很清楚地失去了控制，所以去弄 
清何种推理是允许的，何种是不允许的，应是适当的。很明显，可允许的推理必须没有 
冲突，而且只有真的陈述才能允许从原先已知的真的陈述中推导而来。罗素本人和他的 
合作者阿弗列德·诺斯·怀德海着手发展一种高度形式化的公理和步骤法则的数学系统 
，野心勃勃地要把所有正确的数学推理翻译到他们的规划中去。他们非常仔细地选择法 
则以防止导致罗素自己佯谬的那种佯谬的推理类型。罗素和怀德海所完成的业绩是一部 
纪念碑式的著作。然而，它是非常繁琐的，并且它实际上统一处理的数学推理的类型是 
相当有限的。我们在第二章首次提到的伟大的数学家大卫·希尔伯特致力于一个更可行 
更广泛的规划。它囊括了所有特殊领域的一切正确的数学推理类型。而且，希尔伯特倾 
向于认为，可能证明该规划可免于矛盾冲突。那么数学就一劳永逸地处于无可争辩的安 
全基础之上。 
  
　　然而，1931年25岁的奥地利天才数学逻辑学家库尔特·哥德尔提出了一道实质上摧 
毁了希尔伯特规划的令人震惊的定理，使得希尔伯特及其追随者的希望落空。哥德尔指 
出的是，不管任何精确（“形式的”）数学的公理和步骤法则系统，假定它足够宽广于 
包容简单算术命题的描述（诸如第二章考虑过的“费马最后定理”），并且其中没有矛 
盾，则必然包含某些用在这系统内所允许的手段既不能证实也不能证伪的陈述。这种陈 
述的真理性以可允许的步骤是“不能决定的”。事实上，哥德尔能够向我们展示，公理 
系统本身的协调性的陈述被编码成适当的算术命题后，必须成为一道这样“不能决定的 
”命题。理解这个“不决定性”的性质对我们很重要。我们将要看到为何哥德尔的论证 
直接捣毁了希尔伯特规划的核心。我们还将看到哥德尔的论证如何使我们能用直觉去超 
越所考虑的任何个别的形式化的数学系统的局限。这一点理解对于下面大部分讨论至关 
重要。 
  
　 
  
形式数学系统 
  
　 
  
　　我们必须把“公理和步骤法则的形式数学系统”的含义弄得更清楚些。先必须假定 
有一符号表，我们的数学陈述用这些符号来表达。为了使算术能归并到该系统中去，这 
些符号必须足够於用来表示自然数。如果需要的话，我们可以只用通常的阿拉伯数的记 
号0，1，2，3…9，10，11，12，…，虽然这使得法则的说明比所需要的稍微复杂一些。 
我们如果譬如讲用0，01，011，0111，01111，…去表示自然数列（或，作为折衷，我们 
可以用二进位记号），则说明就会简单得多。然而，由于这会在以下的讨论中引起混淆 
，所以在我的描述中只用通常的阿拉伯记号，而不管系统在实际上用什么符号。我们也 
许需要一个“间隔”符号去把我们系统的不同的“词”或“数”分开，但这又是令人混 
淆的，所以为了必要的目的我们可以只用(，)。我们还需要用字母来表示任意（“变量 
”）自然数（或许整数、分数等等��但是让我们在这里只局限于自然数），譬如t 
，u，v，w，x，y，z，t′，t″，t′″，…。符号t′，t″…也许是需要的，因为我们 
不想对表式中可能出现的变量数目加上一个上限。我们把(′)当作形式系统的另外的符 
号，这样使符号实际数目保持为有限。我们还需要基本算术运算的符号=，+，×等等， 
也许还需要不同种类的括号 
  
　　　　　 　 
  
　　以把诸如“费马最后定理”的陈述写成 
  
　　　　 
  
　　（见第二章65页）。（我原可以用0111来表示3，或者利用“升幂”的记号使得和形 
式化符合得更好；但是正如我说过的，我只拘泥于传统的符号，以避免引进不必要的混 
淆。）上面的陈述（到第一方括号处结束）的意思为： 
　　“不存在自然数w，x，z，z使得…”。 
　　　　　 
　　　　 
　　其意思（到第一方括号的“非”符号处结束）为： 
　　“对于所有的自然数w，x，y，z下述不真…”。 
　这和前面在逻辑上是相同的。 
　 
  
　　我们需用字母来表示整个命题，为此目的我用大写字母P，Q，R，S，…。如下的一 
个命题事实上为上面的费马的断言： 
  
  
  
　　一个命题也可依赖于一个或更多的变量；例如，我们也许对某一特殊的①指数w+3下 
的费马断言感兴趣： 
  
  
  
　　这样G（0）断言“没有一个立方可代表正数立方之和”，G(1)对四次方 
  
　　G（w）对所有的w成立。 
  
　 
  
　　G（）是一个所谓的命题函数，也就是依赖于一个或多个变量的命题的例子。 
  
　　系统的公理是由一般命题的有限罗列所构成，假定在符号的意义已给定的情形下， 
这些命题的真理性是不证自明的。例如，对于任何命题或命题函数P，Q，R（），在我们 
公理之中有 
  
　 
  
　　其“自明的真理性”清楚地可由其意义所确定。（第一个简单地断言：“如果P和Q 
都为真，那么P为真”；第二个断言：“P不真的断言为不真”和“P为真”是等价的；第 
三个可用上面给出的“费马最后定理”的两种叙述方法的逻辑等价性作为例子）。我们 
还可包括基本的算术公理，诸如 
  
　 
  
　　尽管人们也许宁愿从某些更初等的东西建立这些算术运算，并将这些陈述作为定理 
导出。步骤法则是诸如这样（自明）的东西： 
　 
  
　 
　 
  
　　 
　　x而得出的任何命题”。 
　　这些是告诉我们如何从已成立的命题引出新命题的方针。 
　 
  
　　现在从公理开始，然后不断重覆应用步骤法则，就可以建立起一长串的命题。我们 
在任何阶段都可再使用这些公理，并且总可以不断使用任何我们已经添加到越来越长的 
表上的命题。任何正确地集合到表上的命题都被称作定理（虽然它们中有许多是相当无 
聊和无趣的）。如果我们有一个要证明的特定的命题P，则我们可去找一个表，这个表按 
照这些法则正确地集合起来，并用我们特定的命题P作为终结。这样的表在我们的系统中 
为我们提供了一个P的证明；而P就相应地成为一道定理。 
　　希尔伯特规划的思想是，对于任何定义好的数学领域，去找一足够广泛的公理和步 
骤法则的表，使得所有适合于该领域的正确的数学推理的形 
  
　　　 
　　做诸如“费马最后定理”的陈述）。考虑比这更一般的数学领域在这里对我们并无 
益处。算术已经是足够一般到可以应用哥德尔步骤的地步。如果我们能够接受这样的事 
实，即这个公理和步骤法则的广泛系统，按照希尔伯特规划，的确把算术给予我们，那 
么它就为我们提供对算术中任何命题数学证明的“正确性”的确定判据。人们存在过希 
望，这样的公理和法则系统也许是完备的，也就是它会使我们在原则上决定任何可在此 
系统中表述的数学陈述的真伪。 
  
　　希尔伯特的希望是，对于任何一串代表一个数学命题的符号，譬如讲P，人们应能证 
明或者P或者～P，依P是真的还是伪的而定。我们在这里必须假定该符号串在构造上是语 
法正确的，也就是满足所有形式主义的记号法则，诸如括号必须正确地配对等等�� 
;使得P具有定义清楚的真的或伪的意义。如果希尔伯特的希望能被实现，这甚至使我们 
不必为这些命题的意义忧虑！P仅仅为一语法正确的符号串。如果P为一道定理（也就是 
可在系统内证明P），则符号串P的真值就可被赋于真。另一方面，如果能证明～P为定理 
的话，则可被赋于伪。为了使这些有意义，我们除了完备性外还需要一致性。也就是说 
，不应有P和～P都为定理的符号串P。否则P会同时是真的和伪的！ 
  
　　把数学陈述中的意义抽走，只把它们当成某种形式数学系统的符号串是形式主义的 
数学观点。有些人喜欢这种观点，而数学就变成一种“无意义的游戏”。然而，我不欣 
赏这种观点。确实是“意义”而非盲目的算法计算才赋于数学以实质。庆幸的是，哥德 
尔给了形式主义以毁灭性的打击！让我们看看他是怎么做的！ 
  
　 
  
哥德尔定理 
  
　 
  
　　哥德尔论证的部分是非常繁琐和复杂的。然而我们没有必要去考察那纷乱的部分。 
另一方面，其中心思想是简单、漂亮和深刻的。这就是我们可能鉴赏的部分。其复杂的 
部分（其中不乏许多巧妙之处）仔细说明如何把形式系统的个别步骤法则以及不同公理 
的使用实际地编码成算术运算。（意识到这是一个富有成果的可进行的工作正是其深刻 
部分的一个方面！）为了实现编码，人们需要找到用自然数来对命题编号的某种方便方 
式。一种方法就是简单地对形式系统每个特定长度的符号串使用某种“字典”顺序，按 
照串的长度还有一个总的顺序。（这样，长度为1的串可按字母顺序排列，接着的是按字 
母顺序排列的长度为2的串，再后面是长度为3的串等等）。这叫做字典顺序①。哥德尔 
原先用的编号顺序更复杂，但是这种差异对我们不重要。我们将特别关心依赖于单变量 
的命题函数，譬如上述的G（w）。令应用于w 的第n个这样的命题函数（在选定的符号串 
顺序下）为 
  
　　Pn(w)。 
  
　　如果我们愿意的话，可以让编号稍微有点“草率”，这样我们的一些表式可能语法 
上不正确。（这可使算术编码比在试图略去这种语法不正确的表式时容易得多。）如果P 
n（w）是语法正确的，它就是关于两个自然数n和w的定义好的特定的算术陈述。准确的 
为哪一个算术陈述应依所选取的特定编号系统的细节而定。那是属于论证的复杂部分， 
在此不予关心。构成系统中的某一定理的证明的一串命题在选定的编序方案中也可用自 
然数编号。令 
  
  
  
　　表示第n个证明。（这里我又一次使用“草率的编号”，对于某些n的值， 
  
　　现在考虑如下的依赖于自然数w的命题函数 
  
  
  
　　在方括号中的陈述的一部分使用了文字，但它是完全精确定义的。它断言第x个证明 
实际上是Pw（）应用于值w本身的命题的证明。方括号之外的被否定的存在量衡用以移走 
一个变量（“不存在一个x使得……”），这样我们得到了一个只依赖于一个变量w的算 
术的命题函数。此整个表达式断言不存在Pw（w）的证明。我假定它的语法是正确的（甚 
至如果Pw（w）的语法不正确��在这种情形下该陈述仍然是对的，因为一个语法错 
误的表达式是不能被证明的）。由于事实上我们已假设将其转换成算术，所以上面实际 
上是关于自然数的某一算术的陈述（方括号中的部分为定义得很好的关于两个自然数x和 
w的算术描述）。该陈述是可以被编码成算术，但这一点并不假设是明显的。为了说明这 
样的陈述的确可被编码，涉及到哥德尔论证的复杂部分的主要“困难工作”。正和前面 
一样，它究竟为那个算术陈述将依赖于编号系统的细节，并大大地依赖于我们形式系统 
的公理和法则的结构细节。由于所有那些都属于复杂的部分，我们在这里不关心其细节 
。 
  
　　我们已将所有依赖于单变量的命题函数编号，所以我们刚刚写下的必须赋予一个数 
。让我们把这个数记作k。我们的命题函数是在表上的第k个。这样 
  
  
  
　　现在对特殊的w值即w＝k来考察这一个函数。我们得到 
  
  
  
　　这个特定的命题Pk（k）是完好定义（语法正确）的算术陈述。它是否可在我们形式 
系统中有一个证明呢？它的反命题～Pk（k）有证明吗？这两个问题的答案都是“否”。 
从考察作为哥德尔步骤基础的意义可以看到这一点。虽然Pk（k）仅仅是一个命题，我们 
已经把它这样的构造，使得写在左边的断言为“在这系统中不存在命题Pk（k）的证明” 
。如果我们非常仔细地设定好我们的公理和步骤法则，并假定做了正确的编号，则在这 
系统中不能存在这道Pk（k）的证明。因为如果存在这样的证明，则Pk（k）实际断言的 
陈述的意义，也就是不存在证明，将是错的，这样作为一个算术命题的Pk（k）就必须是 
错的。我们的形式系统不应构造得这么坏，使得它在实际上去允许证明错的命题！所以 
情况只能是Pk（k）在事实上无法证明。而这正是Pk（k）要告诉我们的。所以断言Pk（k 
）必须是一真的陈述，这样Pk（k）作为算术命题必须为真。这样，我们已经发现了在该 
系统中没有证明的真的命题！ 
  
　　关于它的反命题～Pk（k）我们可以说些什么呢？最好我们也不能找到它的证明。我 
们刚刚建立了～Pk（k）必须是错的（因为Pk（k）是真的），而我们假定不能在此系统 
中证明错的命题！这样无论Pk（k）还是～Pk（k）在我们的形式系统中都是不可证明的 
。哥德尔定理就这样地被建立起来了。 
  
　 
  
数学洞察 
  
　 
  
　　请注意，在这里发生了某种非常奇异的事情。人们经常把哥德尔定理当作某种负面 
的东西---显示了形式化数学推理的不可避免的局限性。不管我们自以为是多么有智慧， 
总有些命题漏网。但是，我们是否要为这一特殊的命题Pk（k）忧虑呢？在上述的论证过 
程中，事实上我们已建立了Pk（k）是一个真的陈述！尽管在该系统中不能形式地证明这 
个事实，不管怎么样我们已设法看到了这一点。真正需要忧虑的人倒是严格的数学形式 
主义者。这是因为从这推理我们已确定形式主义者的“真理”概念不可避免地是不完备 
的。不管把哪一个（一致的）形式系统应用于算术，总存在一些命题我们可以看到是真 
的，但用形式主义者提出的上述过程不能赋予真理值为真的命题。一个严格的形式主义 
者试图躲开这个情况的可能方法也许是根本不提真理的概念，而仅仅讲在某一固定的形 
式系统中的可证明性。然而，这显得非常局限。由于哥德尔论证的基本点利用关于何者 
实际上为真的何者不真的推理，人们甚至都不能作出上述的论证2。一些形式主义者采用 
更“程序化”的观点，断言不去忧虑诸如Pk（k）这样的陈述，由于它们作为算术命题来 
讲极端复杂和乏味。这些人会宣称： 
  
　　是的，存在一些诸如Pk（k）的古怪的陈述，对于这些陈述我的可证明性或真理的概 
念不和你们的真理的内禀概念相符合。但是那些陈述却不会在严肃的（至少在我所感兴 
趣的那种）数学中出现。这是因为作为数学而言，这样的陈述是荒谬绝伦地复杂和不自 
然。 
  
　　的确，像P（k）这样的作为关于数的数学描述的命题，被全部写出时，会是极端繁 
琐和古怪的。但是近年来，人们提出了一些具有非常可接受特性的相当简单的陈述，它 
们实际上等价于哥德尔类型的命题3。这些命题不能从正常的算术公理得到证明，而是从 
公理系统本身所具有的“显然正确”的性质而来。 
  
　　对我来讲，形式主义者对“数学真理”缺乏职业的兴趣，似乎是对数学哲学所采取 
的非常古怪的观点。而且，也确实不是那么切合实际。当数学家在进行推理时，他们没 
必要继续不断地检查他们的论证是否可按照某个复杂的形式系统的公理和步骤法则来表 
达。他们只要肯定其论证是确定真理的有效方法即可。哥德尔的论证是另一类有效步骤 
。这样我似乎认为，Pk（k）正和能利用预先给出的公理和步骤法则更传统地得到的数学 
真理一样好。 
  
　　建议进行如下步骤。我们把Pk（k）接受为真正有效的命题，并简单地表示为G0；这 
样可以把它作为一个额外的公理加到系统中去。当然，我们新的修改的系统又有了它自 
己的哥德尔命题，譬如讲G1，它又是一个完全有效的关于数的描述。我们相应地又把G1 
加到我们的系统，由此得到进一步修改的系统，它又有自己的哥德尔命题G2（又是完全 
有效的），我们又把它合并进去，得到了下一个哥德尔命题G3，再合并等等，无限次地 
重复这一过程。当我们允许使用整列的G0，G1，G2，G3……作为附加的公理时，结果的 
系统是什么呢？它可以是完备的吗？由于现在我们有了一个无限制（无限）的公理系统 
，哥德尔步骤能否适用也许不太清楚。然而，不断附加哥德尔命题是一个完全系统化的 
方案，我们可将其当作通常的公理和步骤法则的有限的逻辑系统来重述。这一系统又有 
它自己的哥德尔命题，譬如讲Gw，它又能被用来作为公理去附加，而形成了所得到的系 
统的哥德尔命题Gw+1。正如上面那样重复，我们得到了命题Gw，Gw+1，Gw+2，Gw+3…… 
的表，所有都是关于自然数的完全有效的陈述，并可附加到我们的形式系统中去。这又 
是完全系统化的，它导致一个包罗这一切的新系统；但是它又有自己的哥德尔命题，譬 
如讲Gw+w，我们可将其重写成Gw2，而整个步骤又可重新开始，我们得到一个新的无限的 
、却是系统的公理Gw2，Gw2+1，Gw2+2等等的表，它又导致一个新的系统以及一个新的哥 
德尔命题Gw3。重复这整个过程，我们得到Gw4然后还有Gw5等等。现在这一步骤又是完全 
系统化的，并具有自身的哥德尔命题Gw2。 
  
　　这会有终结吗？在一种意义上讲没有；但它导致我们进入不能在此作细致讨论的某 
些困难的数学考虑。1939年阿伦·图灵在一篇论文4中讨论了上面的步骤。事实上，令人 
印象深刻的是，任何真的（但普适量化的）算术命题都可由这类重复的“哥德尔化”步 
骤得到！可参阅飞费曼（1988）。然而，这在一定程度上依赖于我们如何实际上决定一 
个命题真伪的问题。在每一阶段关键的问题是如何把哥德尔命题的无限族合并，从而提 
供一个单独的（或有限数目的）附加公理。这就要求我们的无限族能以某种算术的方式 
被系统化。为了保证正确地完成所预想的系统化，我们要使用系统之外的直觉--正如我 
们首先为了看到Pk（k）是一道真的命题所做的那样。正是这些直觉是不能被系统化的-- 
它必须超越于任何算法行为！ 
  
　　我们利用直觉得出哥德尔命题Pk（k）实际上是算术中的真的陈述，是被逻辑学家称 
之为反思原理步骤的普遍类型的一个例子：这样，由“反思”公理系统和步骤法则的意 
义，并使自己坚信这些的确是得到数学真理的有效方法，人们可能把这直觉编码成进一 
步的真的、不能从那些公理和法则推导出来的数学陈述。正如上面概述的，推出Pk（k） 
的真理性依赖于这样的一个原则。另一个与原先哥德尔论证相关（虽然在上面没提及） 
的反思原则依赖于如下的事实去推出新的数学真理，即我们已经相信能有效得到数学真 
理的公理系统实际上是协调的。反思原理经常涉及有关无限集合的推理，人们使用的时 
候一定要小心，不要过于接近会导致罗素类型佯谬的论证。反思原理为形式主义推理提 
供了反题。如果人们很小心的话，就能使他跳出任何形式系统的严格限制之外，并得到 
原先似乎得不到的新的数学洞察。在我们的数学文献中会有许多完全可接受的结果，其 
证明需要远远超越原先的算术标准形式系统的法则和公理的洞察。所有这些表明，数学 
家得到真理判断的心理过程，不能简单地归结为某个特别形式系统的步骤。虽然我们不 
能从公理推出哥德尔命题Pk（k），却能看到其有效性。这类涉及反思原理的“看见”需 
要数学的洞察力，而洞察不是能编码成某种数学形式系统的纯粹算法运算的结果。我们 
将在第十章再回到这个论题上来。 
  
　　读者也许会注意到在建立Pk（k）“不可证明性”的真理和罗素佯谬的论证之间的相 
似性，还和图灵解决停机问题的图灵机不存在的论证也有相似性。这些相似性不是偶然 
的。在这三者之间存在有强大的历史连接的脉络。图灵是在研习哥德尔工作之后才找到 
它的论证的。哥德尔本人非常熟悉罗素的佯谬，并能把这一类将逻辑延伸得这么远的佯 
谬的推理转化成有效的数学论证。（所有这一切论证都起源于前一章100页描述的康托的 
“对角线删除法”。） 
  
　　为什么我们应该接受哥德尔和图灵的论证，而必须排斥导致罗素佯谬的推理呢？前 
者更直截明了得多，作为数学论证而言更出人意表，而罗素佯谬则依靠牵涉到“巨大” 
集合的更为模糊的推理。但是必须承认，其差别并不真像人们以为的那么清楚。弄清这 
些差别的企图是整个形式主义观念的强大动机。哥德尔的论断表明，严格的形式主义者 
的观点是不能成立的，但他没有向我们指出另外完整的可信赖的观点。我认为这问题仍 
未解决。当代数学中为了避免导致罗素佯谬的“巨大的”集合的推理的类型所实际采用 
①的步骤不能完全令人满意的。而且，它仍然试图以明晰的形式主义的术语来表达，换 
句话说，按照我们并不完全相信不会出现矛盾的术语来描述。 
  
　　无论情况如何，依我看来，哥德尔论证的清楚推论是，数学真理的概念不能包容于 
任何形式主义的框架之中。数学真理是某种超越纯粹形式主义的东西。甚至即使没有哥 
德尔定理，这一点也是清楚的。在我们去建立一个形式系统任何试图中，如何决定采取 
什么公理和步骤法则呢？我们在决定采取法则的指导总是，在给定系统的符号的“意义 
”下对何为“自明正确”的直觉理解。根据关于“自明”和“意义”的直观理解，我们 
如何决定采用哪个形式系统是有意义的，哪个是没意义的呢？以自身具有一贯性的概念 
来决定当然不够。人们可以有许多自身具有一贯性但在含义上没有“意义”的系统，它 
们的公理和步骤法则具有错误的意义，或者根本没有意义。甚至在没有哥德尔定理时， 
“自明”和“意义”的概念仍然是需要的。 
  
　　然而，若没有哥德尔定理，人们可能想象“自明”和“意义”的直觉概念只要在开 
始建立形式系统时用一次就好了，而此后就与决定真理的清楚的数学论证不相干。那么 
按照形式主义者的观点，这些“模糊的”直觉概念在发现适当形式的论证时，作为数学 
的初步思维、或者导引而起作用，而在实际展示数学真理时不起作用。哥德尔定理表明 
，这个观点在数学基本哲学中不能真正站住脚。数学真理的观念远远超越形式主义的整 
个概念。关于数学真理存在某些绝对的“上帝赋予”的东西。这就是在上一章结尾处讨 
论的柏拉图主义。任何特定的形式系统都具有临时和“人为”的品格，在数学的讨论中 
，这类系统的确起着非常有价值的作用，但是它只能为真理提供部分（或近似）的导引 
。真正的数学真理超越于人为的构造之外。 
  
　 
  
柏拉图主义或直觉主义？ 
  
　 
  
　　我已指出了数学哲学的两个相反的学派，我强烈地赞成柏拉图主义，而不赞成形式 
主义观点。我的划分实际上是非常朴素的。可以对此观点进行许多细致的推敲。例如， 
人们可以争论在“柏拉图主义”的总名称下，数学思维的对象是否在任何实际的“存在 
”，或者它只是绝对的数学“真理”的概念，我不想在此做任何鉴别。依我看来，数学 
真理的绝对性和数学概念的柏拉图存在性本质上是等同的一件事。例如，必须归于孟德 
勒伯洛特集的“存在”是其“绝对”性质的特征。阿伽德平面上的一点是否属于孟德勒 
伯洛特集是一个绝对的问题，与哪个数学家哪台电脑在作考察无关。正是孟德勒伯洛特 
集的“数学家无关性”赋予它柏拉图式的存在。而且，它最精细的细节超过了我们目前 
使用电脑所能得到的的极限。那些仪器只能得到具有更深刻的自身的“电脑无关”存在 
结构的近似。然而，我很欣赏对此问题的许多其他合情理的观点。在此我们不必过于忧 
虑这些差别。 
  
　　如果的确有人声称自己为柏拉图主义者，他究竟愿意把柏拉图主义贯彻到何等程度 
，也有观点上的不同。哥德尔本人是一个非常强烈的柏拉图主义者。我迄今所考虑的数 
学陈述的类型是相当“缓和的”5。特别在集论中可引入更令人争议的陈述。当考虑集论 
的所有分支时，就会遭遇到构造极其庞大的模糊的集合，以至于像我这样坚定的柏拉图 
主义者都会怀疑其存在或它为“绝对的”东西6。也许会面临着这样的阶段，集合具有如 
此繁复以及概念上可疑的定义，以至于有关它们数学陈述的真伪问题开始具有某种“个 
人品味”而非“上帝赋予”的品质。人们是否准备和哥德尔一道把柏拉图主义坚持到底 
，要求关于这么巨大集合的数学论述的真伪总为一个绝对的或“柏拉图”的事体，或者 
人们在某处停止，只有当集合为合理地构成并且没有这么巨大时才寻求绝对的真伪的解 
答，对我们的讨论关系并不重大。以我刚刚提到的标准看，对于我们具有意义的（有限 
或无限）集合，真是不可思议的微小！这样我们不必关心在这些不同柏拉图主义观点之 
间的差异。 
  
　　然而，存在诸如称为直觉主义（或称作有限主义）的其他数学观点，它走到拒绝任 
何无限集合的完整存在的另一极端①。直觉主义是1924年由荷兰数学家L．E．J．伯鲁尔 
作为对某些（诸如罗素的）佯谬的与形式主义相区别的响应而倡导的。这些佯谬是由于 
在数学推理中太过自由地应用无限集合所引起的。这种观点的根源可追溯到亚里斯多德 
。他虽然是柏拉图的学生，却否定柏拉图关于数学本体的绝对存在和无限集合的可接受 
性。直觉主义否认（无限或其他）集合自身的“存在性”，而集合仅仅被当作可能确定 
其成员的规则。 
  
　　伯鲁尔的直觉主义的一个特征是排斥“排中律”。该定律宣称，一个　　 
  
　　这是我们上面遇到的关系。）也许亚里斯多德会对在逻辑上如此“显明的”东西受 
到排斥感到不悦！排中律按照“常识”被认为是自明的真理：如果某事物不真的断言是 
错的，则该事物一定是真的！（这一个定律是被称作反证法的数学步骤的基础，参阅67 
页。）但是直觉主义者发现他们能推翻这一个定律。这基本上是因为他们对存在的概念 
采取不同的看法，他们要求一个确定的（智力上的）构造必须是数学对象实际存在性被 
接受的先决条件。这样，对于直观主义者来说，“存在”的意思是“构造存在”。在一 
个用反证法来进行的数学论证中，人们提出某种假设，试图去显示出它的推论会导致一 
个矛盾，这个矛盾为问题中假设的谬误提供了所需的证明。此假设可采用这样的一个陈 
述，具有某些必须性质的数学事体不存在。当这个陈述导致矛盾时，在通常数学中，他 
就推论说所需的事体的确存在。但是，这样的论证本身并没为实际构造这样的事体提供 
任何手段。对于直觉主义者来说，这类存在根本就不是存在。他们正是在这个意义上拒 
绝接受排中律以及反证法的步骤。伯鲁尔对此非构造性的“存在”深为不满7。他断言， 
没有一个实在的构造，这种存在的概念是无意义的。在伯鲁尔的逻辑中，人们不能从某 
种对象的不存在性的谬误推导出该物体实际上的存在！ 
  
　　我认为，虽然关于从数学的存在中寻求构造有某些令人赞赏的东西，但伯鲁尔的观 
点是过于极端了。伯鲁尔在1924年首次提出他的思想，比彻屈和图灵的工作早十多年。 
现在按照图灵的可计算性的构造性概念可在数学哲学的传统框架内研究，并没有必要走 
到像伯鲁尔那么极端的程度。我们可以把构造性的问题和数学存在性的问题分开来讨论 
。如果我们跟随直觉主义，就必须摒弃自己使用数学中非常强有力的论证的使用，而课 
题就变得有点窒息和虚弱。 
  
　　我不想细述直觉主义观点导致的种种困难的荒谬；但是仅仅提及一些问题也许是有 
益的。伯鲁尔经常关心提及的一个例子是π的小数展开： 
  
　　3．141592653589793…。 
  
　　是否在这个展开的某一处存在二十个接连的7的序列，也就是 
  
　　π=3.141592653589793…77777777777777777777…， 
  
　　或者不存在这种情形呢？按照通常的数学，现在所有能说的是，或者存在或者不存 
在--而我们不知哪个是对的！这看来是一个肯定无害的描述。然而，除非人们已经（以 
某种直觉主义者接受的构造方式）确立存在这个序列或者不存在这个序列，他们实际上 
对讲“或者π的小数展开中某处存在连续二十个7的序列或者不存在”采取否决的态度！ 
直接的计算也许足以显示在π的小数展开的某处的确存在二十个连续的7的序列，但要确 
证没有这样的序列则需要某种数学定理。迄今电脑在计算π时还不能进行足够远到能确 
认该序列的存在。在基于概率的基础上，人们预料这样的序列的确存在。但是即使利用 
一台每秒能恒定产生1010位数的电脑，大约也要需要一百或一千年左右才能找到这序列 
！我认为更可能是，不进行直接计算，该序列的存在某天会在数学上被确认（也许是作 
为推论某种更有力和更有趣得多的结果）��虽然也许不是以直觉主义者能接受的 
方式！ 
  
　　这一个特殊问题并不具有实际的数学趣味。它只是由于容易叙述才作为例子提出。 
以伯鲁尔的直觉主义的极端形式，他会宣称：现在断言“在π的小数展开中的某处存在 
二十位连续的7的序列”既不是真的亦不是伪的。如果在将来用计算或（直觉主义的）数 
学证明得到适当的这种或那种结果，那么断言就变成“真”的或“伪”的，视当时情况 
而定。“费马最后定理”是一类似的例子。根据伯鲁尔的极端直觉主义，现在这一道命 
题既不是真的亦不是伪的，但将来也许会变成其中的一种。对我来讲，数学真理的这种 
主观性和时间依赖性是不可理喻的。数学结果是否或何时被接受为正式“证明了”的确 
是一个主观的事体。但是数学真理不应取决于这些依赖社会的判据。对于人们希望能可 
靠地用来描述物理世界的数学，具有随时间而变的真理概念至少可以说是尴尬的和不令 
人满意的。并非所有的直觉主义者都采用伯鲁尔那样强烈的观点。尽管这样，甚至对于 
那些同情构造主义的目的的人也是这么认为，直觉主义观点显然是粗劣的。就仅仅因为 
人们可允许使用的数学推理的类型过于局限的原因，很少当代数学家愿意全心全意地追 
随直觉主义。 
  
　　我已经简介了当代数学哲学的三个主流：形式主义、柏拉图主义和直觉主义。我并 
不掩饰自己强烈同情柏拉图主义的观点，也就是数学真理是绝对的、外在的、永恒的， 
并不基于人造的判据之上；数学对象具有超越时间的自身的存在，既不依赖于人类社会 
，也不依赖于特定的物体。我把这种观点贯穿于本节、上一节以及第三章的结尾处。我 
希望读者准备在这一点上和我大致同心同德。它对于后面要遇到的大量内容都很重要。 
  
　 
  
从图灵结果到类哥德尔定理 
  
　 
  
　　我在阐明哥德尔定理时忽略了许多细节，并且也忽略它的论证中或许在历史上的最 
重要的部分；这就是被叫做公理一致性的“不可决定性”。我在这里的目的不在于强调 
这“公理一致性的可证明性的问题”。这个问题对于希尔伯特及其同代人是如此之重要 
。我只是表明，利用所考虑的形式系统公理和法则某个特殊的哥德尔命题既不是可证明 
的也不是可证伪的。但是利用我们对该问题中运算意义的直觉可以清楚地看到，它是一 
个真的命题！ 
  
　　我提到过，图灵在研究了哥德尔的著作后发展了自己后来的论证，以确立停机问题 
的不可解性。这两个论证有许多共同的地方，事实上，哥德尔结果的关键方面可利用图 
灵步骤直接推出。让我们看看这是如何进行的，并因此对哥德尔定理的背后的东西有某 
种不同的洞察。 
  
　　一个形式数学系统的主要性质是，决定某一给定的符号串是否构成该系统中给定的 
数学断言的证明应是可计算的事体。表达数学证明的全部要点毕竟在于对于什么是有效 
推理、什么是无效推理不必作进一步的裁决。以完全机械的和原先预定的办法来检查一 
个想象的证明是否确实是一个证明应是可能的；也就是说必须有检查证明的算法。另一 
方面，为提出的数学陈述去找证明（或证伪），我们并不要求它必须是算法的事。 
  
　　事实上，在任何形式系统中只要某种证明存在，就总有找到证明的算法。由于我们 
必须假定该系统是以某种符号语言来表达的，这种语言是按照符号的某些有限“字母” 
来表达的。正如以前一样，让我们把符号串以字典的方式编序。我们记得这表示对于固 
定的串的长度按字母编序，先取所有串长为1的，然后串长为2的，串长为3的等等（见12 
2页）。这样，我们就把所有正确建立起来的证明按照这个字典方案进行编序。我们有了 
证明的列表，也就有了该形式系统的所有定理的列表。这是因为定理刚好是出现在正确 
构造的证明的最后一行的命题。这种列表完全是可计算的：由于不管系统的符号串是否 
有作为证明的意义，可以先考虑所有的串的字典列表，然后用我们的证明检查算法去检 
验其是否为一个证明，若不是则抛弃之；然后以同一方法检验第二个，若不是证明则抛 
弃之；然后第三、第四等等。如果有一个证明，我们则可用这种办法最终在这一列表的 
某一处找到它。 
  
　　这样，如果希尔伯特已经成功地找到它的公理和步骤法则的数学系统，该系统足够 
有力到能使人们用形式证明决定任何在该系统中正确表达的数学命题的真伪--则就会有 
一般的算法方法去决定任何这种命题的真理性。为什么这样呢？因为用上述的步骤，如 
果最终在某个证明的最后一行遇到了我们所寻求的命题，则我们就证明了该命题。反之 
，如果我们最终遇到的一行是我们命题的否定，则我们就证伪了它。如果希尔伯特方案 
是完备的，这种或那种的终局就总会发生（并且，如果是协调的，两者永远不会同时发 
生）。这样，我们的机械步骤总会在某一阶段结束，而我们就应有一种决定系统所有命 
题真伪的普通算法。这就和第二章阐述的图灵结果相冲突，也就是说不存在决定数学命 
题的一般算法。因而我们实际上证明了哥德尔定理，就是说希尔伯特期望的方案在刚刚 
讨论的意义上不可能是完备的。 
  
　　由于哥德尔所关心的形式系统的类型只对算术命题而不是对一般的数学命题足够， 
所以事实上哥德尔定理比上述的更特定。我们是否能安排只用算术的运算去实现图灵机 
的所有必须的运算呢？换句话说，是否所有自然数的可计算功能（也就是图灵机动作的 
结果，递推的或算法的功能）可按通常的算术表达呢？我们几乎真的可以，但还不是。 
我们需要在算术和 
  
　　选择为 
  
　　“使得K（x）成立的最小自然数x”， 
  
　　这儿K（）是任何给出的算术地可计算的命题函数��并假定存在这样的 
  
我们的运算在试图寻求所需的不存在的x时就会“无限地算下去”①。）无论如何，在图 
灵结果的基础上前面的论证确认了，把数学的一切分支归结为某个形式系统中的计算的 
希尔伯特规划的确是不成立的。 
  
　　就此而言，这一步骤并没有这么清楚地显示，在这系统中我们具有真的、但不能证 
明的一个哥德尔命题（例如Pk（k））。然而，如果我们回忆在第二章给出的关于“如何 
超过算法”（参阅72页）的论证，我们就看到了可以做非常类似的事情。我们在那个论 
证中指出，如果有决定图灵机动作是否停止的任何算法，我们便能制造图灵机的一个动 
作，我们看到该动作不停止，但是该算法看不到这一点。（记得我们坚持过，当一台图 
灵机将要停止时，该算法必须正确地通知我们，虽然在图灵机动作不停止��它会 
永远运行下去的情形，有时它不能告诉我们。）鉴于上述的哥德尔定理的情形，我们具 
有利用洞察可以看到实际上必须为真的命题（图灵机的不停运行），但是给定的算法动 
作不能告诉我们这些。 
  
　 
  
递归可列集 
  
　 
  
　　存在一种按照集论的语言形象地描述图灵和哥德尔基本结果的方法。这就使得我们 
可以避免按照特别的符号主义或形式系统的任意描述，而使本质问题呈现出来。我们将 
只考虑（有限或无限的）自然数的集合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个”符号串，譬如讲Qn。则每一自然数代表一个命题。形式系统 
的所有命题的集合是由整个集合N来代表，例如，形式系统的定理可被认为自然数的某一 
个更小的集合，例如集合P。然而，命题的任何特殊编号系统细节不是重要的。为了在自 
然数和命题之间建立一种对应，我们需要的是能从任一个自然数n得到它对应的（在一种 
适当的符号记法中写出的）命题Qn的已知算法，以及从Qn得到n的另一个已知算法。假定 
已知这两种算法，我们就能随心所欲地把一个特定形式系统的命题集合和自然数集合N相 
等同。 
  
　　让我们选择一个形式系统，它是协调的，并广泛得足以包括所有图灵机的所有动作& 
#0;�并且在以下的意义上是“有意义的”，即它的公理和步骤法则可认为是“自明地 
真的”。现在，这形式系统的命题Q0，Q1，Q2，Q3，…中的一些实际上在该系统中有证 
明。这些“可证明的”命题有一些属于N的某一个子集的数字，这事实上就是上面考虑的 
定理的集P。我们事实上已经看到了在某一个给定形式系统中存在一种一个接一个产生具 
有 
  
  
  
算法地得到的。所有我们要做的是去看第n个证明的最后一行，以发现在系统中可证明的 
第n个命题，也就是第n个“定理”。）这样，我们就有了一个接一个（也许会有重复� 
;�但这无所谓）产生P的元素的算法。 
  
　　一个可用某种算法以这种方式产生的集合，譬如P，叫做递归可列的。注意，在系统 
中可被证伪��也就是其否定的命题可被证明的命题的集合也类似地为递归可列的 
，因为我们可简单地列举这可证明的命题。在此过程中取它们的否定。存在许多N的其他 
递归可列的集，我们不想介绍把它们定义出来的形式系统。递归可列集的简单例子是偶 
数。 
  
 　。�0，2，4，6，8，…｝， 
　　和平方的集合 
 　。�0，1，4，9，16，…｝， 
　以及质数的集合 
 　。�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的情况如何呢？它是一个递归集吗？我们已知它是递归可列的，所以我们必 
须决定其补集是否也为递归可列的。事实上它不是！我们何以知道呢？我们知道图灵机 
的动作被假定为在我们形式系统中允许的运算。我们用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）停止 
”的命题。类似地，不能由一个算法产生所有真的命题（由于可轻易地修改任何这种算 
法以得到所有错误的命题，只要简单地把它产生的每一命题都取一个负命题即可）。由 
于真的命题因此不是递归可列的（错的也不能），它们构成了比系统中可证明的命题更 
复杂和深广得多的陈列。这再一次阐明了哥德尔定理的结论：形式论证只是得到数学真 
理的部分手段。 
  
　　存在一定的真的算术命题的简单的族，却的的确确能形成递归可列集。例如，不难 
看出，具有如下形式的真的命题 
  
  
  
　　组成递归可列集（我把它记作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.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代表的点就涂成黑色；否则涂成白色。机 
器如何告知我们说这样的序列维持有界呢？这个问题原则上牵涉到知道在序列的无限项 
后会发生什么，这本身不是电脑的事体。幸运的是，若序列是无界的，总存在有限项后 
就使人们得 
　 
  
能肯定该序列是无界的。） 
  
　　这样，在一定的意义上讲，孟德勒伯洛特集的补集（也就是白的区域）是递归可列 
的。如果复数C在白的区域中，就有确定此事实的算法。孟德勒伯洛特集本身也就是黑的 
区域的情况又如何呢？是否有确切告知一个被怀疑处于黑区域的点果真是在黑区域的算 
法呢？迄今看来这一问题的答案仍是未知的9。我询问了许多同事和专家，似乎没有人知 
道存在这样的算法。他们也从未表明过不存在这样的算法。对于黑区域至少还没有已知 
的算法。孟德勒伯洛特集的补集也许真正是一个递归可列但不是递归的集合！ 
  
　　在进一步探索这个设想之前，必须先讨论我掩饰的某些问题。这些问题对于以后讨 
论物理的可计算性具有某种重要性。我前面的讨论实际上有些不精确。我把诸如“递归 
可列的”和“递归的”这样的术语应用于阿伽德平面也就是复数的集合上。严格地讲， 
这些术语只能适用于自然数或其他可列的集合。我们已经在第三章（98页）看到实数是 
不可列的，所以复数也不是可列的--由于实数可考虑作特殊种类的复数，也就是虚部为 
零的复数。事实上，刚好存在和实数“一样多”数目的复数，也就是C那么多。（粗略地 
讲，为了建立复数和实数之间的一一对应，我们可以把每一复数的实虚部各作小数展开 
，然后将其交叉地塞到相应实数的奇数和偶数位上去：例如复数3.6781…+i512.975…对 
应于实数50132.6977851…。） 
  
　　逃避这个问题的一种办法是只管可计算的复数。我们在第三章看到，可计算的实数& 
#0;�并因此可计算的复数--的确是可列的。然而，这里有严重的困难：事实上不存在 
决定两个按照它们相应的算法给出的可计算数是否相等的一般算法！（我们可以算法地 
形成它们的差，但我们不能算法地决定这个差是否为0。想象两个分别产生0.99999…和1 
.00000…的算法，我们也许永远不会知道这些9和0是否无限地继续下去，因此这两个数 
相等，或最终某些其他的数会出现，因此这两个数不等。）这样，我们也许永远不能知 
道这些数是否相等。其中的一个含义是，甚至对诸如阿伽德平面上的单位圆盘这么简单 
的集合（所有到原点的距离不大于一个单位的点的集合，也就是图4.4中的黑的区域）都 
没有决定复数是否实际上处于圆上的算法。当点在内部（或在外部）时不会引起这个问 
题，但点处于圆盘的边缘时，也就是在单位圆本身上时就有了问题。单位圆被认为是圆 
盘的部分。假定我们简单地给出产生某复数的实部和虚部的位数的算法。如果我们怀疑 
该复数实际上处于单位圆上，我们并不能肯定这个事实。不存在去决定可计算数 
  
　　x2+y2 
  
　　是否实际上等于或不等于1的算法，也就是决定该可计算复数x+iy是否在单位圆上的 
判据。 
  
  
  
　　这肯定不是我们所需要的。单位圆盘当然必须被当作递归的！没有很多集合比单位 
圆盘更简单！一种躲避这一问题的办法是不理睬边界。对实际上处于内部或外部的点肯 
定存在确认这些事实的算法。（简单地一个接一个地产生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。代数数对于 
这种情形下的边界的算法性质的研究毫无用处！不难去寻找其他的可计算数的子集以对 
付这特殊情形，但人们会强烈地感到，我们还没得到正确的观点。 
  
  
  
　 
  
一些非递归数学的例子 
  
　 
  
　　在许多数学分枝中产生了非递归的问题。也就是说，我们会遇到一系列的问题，它 
们答案或者为“是”或者为“非”，但是不存在决定究竟是什么答案的一般算法。在这 
类问题中有一些显得非常简单。 
  
　　首先考虑求整系数代数方程组的整数解的问题。这种方程称为丢番都方程（以希腊 
数学家丢番都来命名，他的生活年代为公元前三世纪，他研究了这一类方程）。这样的 
一组方程可为 
  
　　z3－y－1=0，yz2－2x－2=0，y2－2xz+1=0， 
  
　　问题在于决定它们是否有x，y，z的整数值的解。在给定的特殊情况下，事实上存在 
  
　　X＝13，y＝7，z＝2 
  
　　的解。然而，不存在决定任意丢番都方程集合①的这一问题的算法：尽管丢番都算 
术是这么初等，它却是非算法数学的一部分！ 
  
　　（另一个稍微高等的例子是流形的拓朴等价。这里我仅仅简略地提及，因为它和第 
八章要讨论的问题有某种可以预料到的相关性。为了理解何为“流形”，先考虑一个线 
圈，它是仅仅为一维的流形。然后考虑一个闭合面，这是二维的流形。再摹想具有三维 
或更高维的“表面”。两个流形的“拓朴等价”表明其中一个可以连续运动地变形成另 
一个��不能撕裂，也不能粘住。这样，一个球面和一个立方体的表面就是拓朴等 
价的，同时它们和一个环或茶杯的表面不是拓朴等价的��后两者实际上是相互拓 
朴等价的。现在，对于二维流形，存在一种决定其是否拓朴等价的算法��事实上 
可归结为计算每一曲面所具有“把柄”的数目。在写此书时，对于三维这问题的答案还 
没有得到，但是对于四维或更高维的情况，已经知道不存在决定等价类的算法。四维情 
形和物理有些相关是可以理解的。这是由于按照爱因斯坦的广义相对论，空间和时间一 
起组成了一个四流形（见第五章238页）。格罗许和哈特尔在1987年提出，这个非算法性 
质可能和“量子引力”有关；还可参阅第八章。） 
  
　　现在我们考虑一个被称作词语问题11的不同种类的问题。假定我们有某些符号字母 
，考虑把这些符号连成各种称作词的串。词本身可以不具有意义，但是我们有一张（有 
限的）在它们之间“等价”的表，可用此表来推导出更多这样的“等价”。这可以用如 
下办法做到，在较长的词中找出和表中某个词相同的部分，这一部分可用表中认为是相 
等的另一个词来取代。现在问题就归结为，对某一对给定的词，按照这些规则决定它们 
是否“相等”。 
  
　　例如，我们原始的表为 
　　EAT=AT 
　　ATE=A 
　　LATER=LOW 
　　PAN=PILLOW 
　　CARP=ME。 
　 
  
　　例如，从这些我们可以推出 
　　LAP=LEAP 
　　这可由连续地利用原表中的第二、第一以及再次第二个关系而得到： 
　 
  
　　LAP=LATEP=LEATEP=LEAP。 
  
　　现在的问题在于，给定某一对词，我们能简单地用这种叠代法从一个词得到另一个 
词吗？例如，我们能从CATERPILLAR得到MAN，或从CARPET得到MEAT吗？在第一种情形下 
的答案恰好为“是”，而在第二种情况下则为“非”。当答案为“是”时，通常显示这 
一点的方法是简单地写出一串等式，每一个词都是用允许的关系从前面的词得出。这样 
（要改变的字母用粗体印出，刚被置换的用斜体印出）：　　CATERPILLAR=CARPILLAR=C 
ARPILLATER=CARPILLOW=CARPAN=EAN=MEATEN=MATEN=MAN按照允许的法则，我们何以得知 
不能从CARPET得到MEAT呢？对此问题，我们要稍微多想片刻，但是用各种不同的方法不 
难看到。最简单的方法如下：在我们原始表上的每个“等式”中，A加上W再加M出现的总 
次数在两边是相等的。这样，在所有允许替代的系列中A，W和M的总数目不应改变。然而 
，对于CARPET这个数为1，而 NEAT为 2。所以靠允许的替换不可能从CARPET得到MEAT。 
  
　　请注意，当两个词“相等”时，我们可简单地使用所给定的规则，写出一串允许的 
形式符号串来显示这一点；而在“不相等”的情形，我们必须求助于关于给定规则的论 
证。只要两个词事实上是“相等”的时候，我们就有清楚的算法可用来在它们之间建立 
起“相等”。我们所要做的是，把所有可能的词的序列作字典式的列表。如果序列中含 
有接连的两个词，其中第二个词不能按允许的规则从第一个词得出的，就从这表中删去 
这样的序列。余下的序列就提供了所有要寻找的词之间的“等价类”。然而，一般地不 
存在这样明显的算法，它能决定两个词不“相等”。为了建立这个事实，我们必须求助 
于“智慧”。（我的确花了好一阵时间才注意到上面的“技巧”，它可用来建立CARPET 
和MEAT的不“相等”。对于其他例子，也许需要完全不同的“技巧”。顺便提及，对于 
建立“等式”的存在，智慧虽然不是必要的，却是有助的。） 
  
　　事实上，在上述情况中对于包含五个“等式”的特殊的表，当两个词的确“不等” 
时，提供一种去确定其“不等”的算法并不特别困难。但是，为了找到对这种情况起作 
用的算法，我们必须使用一些的智慧！人们发现，并不存在任何单独算法可普遍地应用 
于所有原始表的选择。在这个意义上讲，词语问题不存在算法解。一般词语问题是属于 
非递归数学的范畴！ 
  
　　甚至对于某种特别选取的初始表，不存在决定两个词语何时不相等的算法。其中一 
例便是 
　　AH=HA 
　　OH=HO 
　　AT=TA 
　　OT=TO 
　　TAI=IT 
　　HOI=IH 
　　THAT=ITHT。 
  
　（这表采用自G．S．蔡亭和丹娜·斯各特(1955)；参阅伽特纳1958，第144页。）这样 
，这个特殊的词语问题本身就是一个非递归数学的例子。也就是说，利用这张特殊的初 
始表，我们不能算法地决定两个给定的词是否“相等”。 
  
　　从形式化数学逻辑的考虑（正如我们早先考虑过的“形式系统”等等）中产生了一 
般的词语问题。初始表起着公理系统的作用，词的替代规则起着步骤的形式法则的作用 
。从这种考虑引起了词语问题的非递归性的证明。 
  
　　作为非递归数学问题的最后一个例子，现在我们考虑一个用多边形来覆盖欧几里德 
平面的问题。这里我们只允许用有限种不同形状的花砖，看看是否能将整个平面既没有 
裂缝又没有重叠地覆盖住。这种用多边形来铺满平面的方法称为平面的镶嵌。我们都对 
如下事实很熟悉，可以只用正方形或正三角形或正六边形来镶嵌（正如第十章图10.2所 
示的），但是不能只用正五边形。还有许多其他的单独形状可以用来镶嵌平面，正如画 
在图4.6中的两种不规则五边形。用两个形状来镶嵌，结果就更精巧。图4.7画出了两个 
简单的例子。迄今为止所有的例子都具有称为周期性的性质。这表明它们在两个独立的 
方向上完全重复。按照数学语言，我们说存在一个周期的平行四边形--一个平行四边形 
，如果我们用某种方法将其标出，并在平行于它的边的两个方向上不断地重复，则能重 
新产生给定的镶嵌花样。图4.8即为一个例子，在左面画出了用刺状的花砖进行的周期镶 
嵌，而在右面则画出与此周期性镶嵌相关的周期平行四边形。 
  
　　存在许多不是周期性的平面镶嵌。图4.9画出了三种，这是用图4.8所示的同一种刺 
状花砖组成的非周期性的“螺旋”状镶嵌。这一种特别的花砖形状（由于明显的原因） 
被叫做“万能的”，它是由B·格吕堡和G.C.谢发德设计的(1981，1987)，这明显地是基 
于H·冯德堡的更早的形状。值得注意的是，用这种花砖既可以构成周期性的也可以构成 
非周期性的镶嵌。许多其他单独花砖形状和花砖集合也具有这种性质。现在我们要问， 
是否存在一种花砖或一组花砖，只能非周期性地镶嵌平面呢？答案是肯定的。在图4.10 
中我画出了一族由美国数学家拉飞逸·罗宾逊(1971)建造的六个花砖，它们只能够非周 
期性地镶嵌整个平面。 
  
  
  
　 
  
  
  
　　值得稍微了解一下这种非周期性的花砖族由来的历史。（参阅格吕堡和谢发德1987 
）。1961年美籍华人逻辑学家王浩提出了对于镶嵌问题是否存在一个决定步骤的问题， 
也就是说，是否存在一种算法，它可以决定给定的不同多边形的有限集合能否将整个平 
面  嵌①！他指出，如果每一个以某种方氏 馇镀矫娴牟煌ㄗ┑募希鼓馨颜馄矫� 
周期性地镶嵌的话，则的确存在这样的决定步骤。我想，可能那时人们感到，不太会有 
违反这种条件的集合--亦即会存在“非周期性”的花砖集合。然而，1966年在王浩的建 
议指导下，罗伯特·伯格能够指出，镶嵌问题的决定步骤实际上不存在：镶嵌问题也是 
非递归数学的一部分12！ 
  
　 
  
　　这样，我们从王浩的早期结果得知。必然存在非周期性的花砖集合，而且伯格也确 
实找到了第一族非周期性花砖。但是，由于这些论证脉络之复杂性，他的集合涉及到了 
非同小可的大数目的不同花砖��最初有20426个。伯特又用了许多技巧才将其数目 
减少到104个。然后到1971年，拉飞逸·罗宾逊将此数目减少到图4.10所示的六个。 
  
  
  
　　 
  
　 
  
　　图4.11中还画出了另外一种非周期性的六种花砖的集合。这是大约在1973年我自己 
沿着完全不同的思路得到的。（在第十章中我还将提及，图10.3画出了用这些形状铺就 
的排列。）我注意到罗宾逊的非周期性的六集合后，开始设法减少此数目；试着拼拼凑 
凑，能够将其减少到两个。图4.12中画出了另个两种方案。这些完整的镶嵌显示出的必 
须为非周期性的花样，具有许多显著的性质，包括了似乎在结晶学上不可能的五重对称 
的准周期结构。以后我还会提及。 
  
　　令人吃惊的是，数学中这么明显地“无聊的”领域--也就是用全等的形状去覆盖平 
面��初看起来像是“小孩游戏”，实际上应该是非递归数学的一部分。实际上， 
在这领域中还有许多未解决的困难问题。例如，我们还不知道，是否存在只包括单非周 
期性集合。 
  
　　王浩、伯格和罗宾逊处理镶嵌问题时，所用的花砖是以方块为基础的。我这里允许 
用一般形状的多边形，而且为了展现单独的花砖，人们需要某种可胜任的计算方法。一 
种方法是将其顶点当成复平面上的点，也许这些点只要是代数数就完全足够了。 
  
　 
  
孟德勒伯洛特集像非递归数学吗？ 
  
　 
  
　　让我们回到早先的关于孟德勒伯洛特集的讨论。为了阐释的目的，我们假定，在某 
一适当的意义上，孟德勒伯洛特集是非递归的。由于它的补集是递归可列的，这就表明 
集合本身不是递归可列的。我认为，关于非递归集合和非递归数学方面，孟德勒伯洛特 
集的形式似乎对我们有许多教益。 
  
　　回到第三章遇到的图3.2。我们注意到，集合的大部分似乎都由一个大的心状的区域 
所充满，在图4.13中用A来表示该区域。这个形状称为心脏线，它的内部区域可以定义为 
阿伽德平面的点C的集合。该集合是由 
  
　　c=z-z2 
  
　　的形式产生的，z是离原点距离小于1/2的复数。这一集合在早先提出的意义上肯定 
是递归可列的：即存在一个算法，把它应用于区域的内部的一点时，将会断定这一点的 
确是在区域的内部。很容易从上述的公式得到实际的算法。 
  
　　现在考虑刚好处于心脏线左边的圆盘状的区域（图4.13中的区域B）。它的内部区域 
为点 
  
　　c=z-1 
  
　　的集合，这儿z离开原点距离小于1/4。这一区域的确是圆盘的内部--在一个准确圆 
的内部的点集合。这一区域又是在上面意义下递归可列的。关于心脏线上其他“瘤”的 
情况又如何呢？考虑余下的两个最大的瘤。这是大致圆形的斑点，近似地处于图3.2心脏 
线的上顶和底下图4.13中用C1，C2表示。它们可按 
  
　　c3+2c2+(1-z)c+(1-z)2=0 
  
　　的集合给出，这儿z的范围是离开原点距离小于1/8的区域。这个方程事实上不仅为 
我们提供了两个斑点（在一起的），而且还提供一个“婴儿”心脏线形状，后者出现在 
图3.2的左边的地方--也就是图3.1的主要区域--在图4.13中标作C3的区域。这些（一起 
或分开的）区域由于上述公式的存在又组成了递归可列集。 
  
　 
  
　　尽管我已经做过假设，即孟德勒伯洛特集可能是非递归的，我们运用某些定义完好 
的以及不过于复杂的算法，可以清理出该集合的最大面积。这个步骤似乎应该继续下去 
。集合中所有最明显的、肯定占满了它面积的绝大部分（如果不是所有的话）的区域， 
可以被算法地处理。如果正如我所设想的那样，这集合全体不是递归的，则我们的算法 
不能达到的区域必须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一 
个区域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而（如果我关 
于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙的、复杂的、模糊的深 
处，甚至于用我们改善了的算法都达不到。我们再次可能利用直觉、天才和勤奋的巨大 
努力，将这样的一个区域定位，但是还会有其他的会逃脱掉，等等。 
  
　　我想这就像用数学方式处理困难的问题，且假定为非递归性的。人们在某些特别的 
领域遇到的最普遍问题可由简单的算法步骤��甚至是已经知道了几世纪的步骤来 
解决。但是其中仍有漏网之鱼，要掌握它们就需要更复杂的步骤。漏网之鱼当然特别刺 
激数学家们，并促使他们去发展更为有力的方法。这些必须是基于对涉及的数学性质的 
越来越深刻的洞察之上。在我们对物理世界的理解中也许存在某些这种东西。 
  
　　在上面考虑的词语及镶嵌问题中，人们可以对这一类事稍有了解（虽然在这些领域 
中数学工具还未发展得非常远）。我们在一个非常特殊的情形下能用非常简单的论证去 
显示，某一词不能用允许的规则从另一词得到。不难想象，更复杂得多的推理可在处理 
更古怪的情形时起作用。很可能这些新的推理可发展成算法步骤。我们知道，不存在一 
个可以足够应付词语问题的所有情况的步骤，但是逃脱的例子需要非常仔细和精巧地去 
构造。的确，只要我们肯定知道躲开我们算法的例子，只要我们知道如何构造这些例子 
，则我们可以改善我们的算法以包括这种情形。只有不“相等”的配对词会逃脱，故一 
旦我们知道它们逃脱，我们就知道它们不“相等”，这一事实可添加到我们算法上去。 
我们改善了的洞察就导致一个改善了的算法！ 
  
　 
  
复杂性理论 
  
　 
  
　　我在前面以及上一章关于算法的性质、存在和局限的论证是处于非常“原则的”水 
平上。我根本就没有讨论到出现的算法是否在任何方面像是可行的。即使对于算法存在 
并且该算法如何构造都很清楚的问题，也还需要许多才干和勤勉，才能将此算法发展成 
有用的东西。有时小小的洞察和才干就能可观地降低算法的复杂性，以及有时极大地加 
快其速度。这些问题经常是非常细节和技术性的。近年人们在构造、理解和改善算法方 
面，在不同的情况下做了大量的工作。这是一个快速扩大和发展的研究领域。我不想对 
这些问题进行细致的讨论。然而，有关算法的速度可被增加的某一绝对的极限有各种普 
遍知道或猜测的东西。人们发现，甚至在具有算法性质的数学问题中，也存在种种内在 
地比其他问题更难于算法地解决的问题。困难的问题只能用非常慢的算法（或许，需要 
非同寻常地大量的存储空间等）来解。有关这类问题的理论称为复杂性理论。 
  
　　复杂性理论并不这么关心算法地解决单独问题的困难，而是关心无限个问题的族， 
找到解决一个单独族的所有问题的一般算法。族中的不同问题会有不同的“尺度”。问 
题的尺度是由某一自然数n来测量。（关于这一个数n实际上如何表征问题的尺度，我一 
会儿还要再说。）算法对于每类中的每一特别问题所需的时间长度��或更正确地 
说，基本步骤的数目--是依赖于n的某一自然数N。稍微精确一点讲，我们讲在所有具有 
某一特别尺度n的问题中算法采用的最大的步骤数目为N。现在，当n变得越来越大，N也 
似乎变得越来越大。事实上，N似乎增加得比n快速得多。例如，N可以近似地和n2，n3或 
许2n成比例（对于大的n，它比n，n2，n3，n4以及n5中的每一个都大多了，甚至比带有 
任何固定指数r的nr都大），或者譬如讲N甚至近似地和22n（这又更大得多）成比例。 
  
　　当然，这些“步骤”的数目可依赖于实现该算法的电脑的类型。如果电脑为第二章 
描述的图灵机，那儿只有一盘磁带--这是相当低效率的--那数目N就会比允许两盘或三盘 
磁带的增加得更快速（也就是说机器会运行得更慢）。为了避免这类不定性，按照N作为 
n的函数增加的可能方式进行了宽广的分类，使得不管使用何种类型的图灵机，N的增加 
率的度量总是归到同一分类中去。一种称为P（说明“多项式时间”的分类包括了所有最 
多为n，n2，n3，n4，n5，…中的一个的固定倍数①的速率。也就是说，对P分类中的任 
何问题（这里我的“问题”的真正含义是具有解决它们的一个一般算法的一族问题）， 
我们有 
  
　　N≤K×nr， 
  
　　这儿K和r为常数（与n无关）。这表明N不比n的某一固定方次的某一倍数更大。 
  
　　两个数相乘肯定是属于P问题的简单类型。为了解释这一点，我必须首先描述数目n 
如何表征一对特殊乘数的尺度。我们可以想象每一个数都以二进位写出，而每一个数的 
二进位位数简单地为n/2，总共给出了n二进位数--也就是总共n比特。（如果一个数比另 
一个短，可以简单地从短的开始连续地在前头加上零使之和长的具有一样的长度。）例 
如，如果n=14，我们可以考虑 
  
　　1011010×0011011 
  
　　（就是1011010×11011，但是在短的数上添了一些零）。最直接进行乘法的方式是 
只要写出： 
  
　 
  
　　记住，在二进位系统中，0×0=0，0×1=0，1×0=0，1×1=1，0+0=0，0+1=1，1+0=1 
，1+1=10。单独二进位乘法的次数为(n/2)×(n/2）=n2/4，并且可具有(n2/4-(n/2)次的 
单独的二进位加法（包括移位）。这样，总共有(n2/2)-(n/2)次的单独算术运算�� 
;我们必须包括一些涉及到移位的额外的逻辑步骤。总的步骤数为N=n2/2（忽略低阶项） 
，这肯定是多项式的13。 
  
　　一般来说，对于一族问题，我们取这问题的“尺度”的测度n为需要指明该特别尺度 
的问题的自由数据所需要的二进位位数（或比特）的总数。这意味着，对于给定的n，在 
给定的尺度下问题会有多到2n种不同的情形（因为每一位可有两种可能性中的任一个，0 
或1，而总共有n位数），而这些都必须由算法在不多于N步骤下被一致地处理好。 
  
　　存在许多不属于P问题（的族）的例子。例如，为了进行从自然数r行 
  
　　在多项式时间内可以写下答案并甚至能检查正确与否的问题更为有趣。由此性质表 
征的（可算法地解出的）问题（的族）是一个重要的范畴。它们被称为NP问题（的族） 
。更精确地讲，如果在NP中的问题的族的个别问题有一解，那么该算法将给出这个解， 
并且它必须能在多项式时间内检验所设想的解确实是一个解。在问题没有解的情形下， 
算法会告诉我们这个，人们不必在多项式或别的时间内去检验的确没有解14。 
  
　　NP问题既在数学本身，也在实在世界的许多范围内出现。我只给出一个简单的数学 
例子：在一个图中寻找所谓的“哈密顿线路”的问题（一个极简单思想的吓唬人的名字 
）。用“图”来表示点或“顶点”的有限集合，一定数目的点对由称为图的“边缘”的 
线连接起来。（我们在这儿并不对几何或“距离”性质感兴趣，只对由哪一顶点连接到 
哪一顶点感兴趣。这样，所有顶点是否在一个平面上表出是无关紧要的，我们的边缘是 
否互相穿越还是处于三维空间中都是无所谓的。）哈密顿线路简单地就是一个只包括图 
的边缘的闭合圈，其中每一顶点只刚好通过一次。图4.14中画出了一个在上面标出哈密 
顿线路的图。哈密顿线路问题是去决定，对于任何给定的图是否存在哈密顿线路，只要 
存在就把它明了地画出来。 
  
　 
  
　　可以按二进位用不同方式来表述一个图。用何种方法关系不大。一个步骤是给顶点 
编上号1，2，3，4，5，…，然后以某种适当的固定顺序列出成对的顶点来： 
  
　　(1，2)，(1，3)，(2，3)，(1，4)，(2，4)，(3，4)，(1，5)，(2，5)，(3，5)，( 
4，5)，(1，6)，… 
  
　　然后我们做一个准确的0和1的搭配的表，当一对顶点对应于图的一个边缘时写上1， 
否则写0。这样二进位序列 
  
　　10010110110… 
  
　　表明顶点1接到顶点2、顶点4以及顶点5，…顶点3接到顶点4和顶点5，…，顶点4接 
到顶点5，…等等（见图4.14）。如果需要的话，哈密顿线路可由这些边缘的子集给出， 
它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿 
线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是 
边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各 
一次。这一检验过程是某种可以在多项式时间内完成的事。 
  
　　事实上，这个问题不仅是NP的，而且被认为是NP完备的。这表明其他任何NP问题都 
可在多项式时间内转变成它。这样，如果某个足够聪明的人能在多项式时间内找到解决 
哈密顿线路的算法，也就是能显示哈密顿线路问题实际上是在P中！则其推论是任何NP问 
题都在P中！这样的事情会具有重大的含义。一般地讲，对于合情理大的nP中的问题被认 
为可以用一台快速的现代电脑“处理”的（也就是“在一可接受的”时间长度里是可解 
的）。而在NP中又不在P中的问题，对于合情理大的n被认为是“不可处理的”（也就是 
虽然在原则上可解，“在实际上是不可解的”），而不管我们将面临着何种可以预见的 
种类的电脑速度的增加。（对于大的n的不在P中的NP问题，需要的时间会急速地变得比 
宇宙的年龄还要长，这对于实际的问题没有什么用处！）任何在多项式时间内解决哈密 
顿线路问题的聪明算法都能转换成在多项式时间内解决任何其他NP问题的算法！ 
  
　　另一个NP完备的15问题是“旅行推销员的问题”。这个问题和哈密顿线路问题很相 
像，除了在不同的边缘附上数字，人们寻求数（推销员走的“距离”）的和为极小的哈 
密顿线路。旅行推销员问题的多项式时间解会又一次导致所有其他NP问题的多项式时间 
解。（如果真的找到这样的一个解，将会变成头条新闻！尤其是好几年来提出了密码系 
统，该问题有赖于大整数的因子化问题，这是另一种NP问题。如果可在多项式时间内解 
决这一问题，那么这样的码就可能被强大的现代电脑所破。但是如果不能，这码就是安 
全的。参见伽特纳1989。） 
  
　　专家们普遍相信，不管用任何类图灵机的仪器，实际上都不可能在多项式时间内解 
决一个NP完备的问题。所以结论是，P和NP不是同样的这个信念很可能是正确的，虽然还 

　　12．汉弗(1974)和迈尔斯(1974)还指出，存在一个单独的（一个巨大数目的花砖） 
集合，它只能以不可计算的方式来镶嵌平面。 
  
　　13．事实上对于大的n，这一步骤的数目可用一些技巧减少到nlogloglogn�� 
这当然还在P中。参见克奴斯(1981)有关的更多资料。 
  
　　14．更正确地讲，只对是/非类型问题（例如，给定a，b和c，a×b=c为真的吗？）P 
、NP和NP完备的族（参见165页）才被定义，但在正文中的描述对我们的目的已经足够。 
  
　　15．严格地讲，我们需要是/非的模式，诸如：推销员是否有一条距离小于若干的路 
径呢？（见上面的注释14）。 
--