哥德尔定理及其哲学义蕴

1、哥德尔定理及其哲学义蕴1.哥德尔其人假设让人们列举出20世纪影响人类思想的十大伟人，恐怕爱因斯坦alberteinstein、图灵alantturing、哥德尔kurtgdel和凯恩斯jhnkeynes应榜上有名，事实上，这四位也恰是2002年美国?时代周刊?上列出的“20世纪震撼人类思想界的四大伟人，足见这四位大家思想之重要而深远。然而，对于物理学家爱因斯坦、理论计算机之父图灵，以及经济学家凯恩斯的工作，一般人总还略知一二，但大多数人对作为数学家和逻辑学家的哥德尔的思想就知之不祥，更知之不确了。库尔特哥德尔1906年出生在摩拉维亚的布尔诺城，是一个生活条件属中产阶级的奥地利日尔曼裔家庭的第二

2、个儿子，父亲是一家纺织厂的合伙经营人，母亲是受过良好教育的家庭妇女。1924年哥德尔入维也纳大学学习，最初主修物理和数学，后来在维也纳小组的鼓励下开始学习逻辑。1930年获哲学博士学位，1933年获维也纳大学执教资格。1940年迁居美国任普林斯顿研究院研究员，1948年参加美国国籍，1976年退休，1978年由于精神紊乱死于回绝进食造成的营养枯竭。哥德尔的一生可以说是倾力献身根底理论研究的一生，他的学术奉献根本上是在数学、逻辑和哲学领域。1929-1938年间哥德尔作出数理逻辑领域三大奉献：证明一阶谓词演算的完全性；证明算术形式系统的不完全性；证明连续统假设和集合论公理的相对一致性，这些结果不

3、仅使逻辑学发生了革命，而且对数学、哲学、计算机和认知科学都有非常重大的影响。特别是电子计算机诞生之后，哥德尔的不完全性定理的深化性更加受到学界的关注。只是稍稍出乎人们意料的是，作出这几个划时代结果后，自1940年以后，哥德尔除了继续考虑一些集合论问题，有5年时间热中相对论并得到一个受爱因斯坦赞赏的结果外，大部分时间倾注了哲学问题的研究。他一生著述很少，极少公开演讲，只出版过一部著作，发表文字不及300页，从未构造过任何完好的理论体系，甚至没有一个真正意义上自己的学生，他的大部分思想记录在手稿、私人通信和谈话记录中。哥德尔曾被许多人看作带有神秘色彩的人物，一方面是因为他的不完全性定理的逻辑外衣使

4、大多数人难觅其思想的内在义蕴，另一方面也因为对于他的个性和精神状况流传着一些坊间神话。但是可以肯定的，哥德尔不仅以精湛优雅的工作作出了令世人瞩目的科学奉献，还以卓然深化的思想为世人留下一笔丰厚的哲学遗产。哥德尔一生特立独行，始终如一地将一流的人格品质、高远的科学鉴赏力、超凡的创造性和至为严谨的学风融为一体，倾其全力献身根底理论研究工作，在这个充满竞争的世界上，他完全采取了一种“超然于竞争之上的生活态度。王浩曾将哥德尔与爱因斯坦相提并论，称他们是哲人科学家中的“稀有品种。到目前为止，由一流数学家和逻辑学家组成的编委会负责编辑出版的?哥德尔文集?已经于1986、1990、1995年出版了前三卷，其

5、他各卷还将陆续出版，借助?哥德尔文集?，我们必将逐步走进哥德尔的精神世界，进一步理解其思想的博大精深。2.哥德尔的不完全性定理哥德尔思想最深化地表达在为世人称道的不完全性定理之中。为了理解这一定理的深化内涵，我们首先理解一下一阶谓词逻辑的完全性问题。我们知道，自然语言中包含着各种隐喻的成分和模糊之处，在使用中常常需要依赖于使用语言的语境，用自然语言进展推理往往会产生歧义，带来意义的不确定性，因此在莱布尼兹时代，逻辑学家们就希望引进一套意义单一明确的人工符号，构造一套形式语言来严格、明晰地整理日常推理和数学推理。为此目的，1879年弗雷格g.frege提出第一个初等逻辑的形式系统未完全形式化，1

6、910年罗素b.russell在?数学原理?中给出了一阶谓词逻辑的形式系统p，1928年希尔伯特d.hilbert和阿克曼.akeran又引进了形式系统ha，根本特征都是引进了一套人工语言代替自然语言。一般来讲，在一个形式系统中，各种陈述都表示成有穷长度的符号串，系统的形成规那么指明什么样的符号串是合法的公式，一些符号串被当作公理。系统中还包括一系列推理规那么，指明什么是系统中定理的证明。一个证明就是从公理出发对公式变形而形成的有穷长的公式序列，序列中的每一个公式，或者是公理，或者是由在前的公式按照推理规那么形成的公式，而且系统中每一个定理都是这样经过有穷步骤得到的结果。到了20世纪20年代，

7、这三个系统已经为逻辑学家们所普遍承受。问题是，这样的形式系统是否能囊括所有的逻辑真理？于是，希尔伯特1928年明确提出问题，证明一阶谓词逻辑系统具有完全性。一年以后，哥德尔在他1929年完成的博士论文中证明，包括弗雷格、罗素和希尔伯特-阿克曼的一阶谓词逻辑的形式系统，都具有一种语义完全性，即所有普遍有效式都可在一阶谓词逻辑系统中作为定理得到证明，所谓普遍有效式，就是在一切论域中都真的公式。这一结果说明，一阶谓词逻辑系统在刻画那些逻辑真理方面是足够充分的。既然一阶谓词逻辑具有如此强大的才能，逻辑学家们期望借助它构造整个数学的形式系统，从而用形式化手段证明所有的数学真理。事实上，1900年巴黎数学

8、家会议上，希尔伯特遵从“世界上没有不可知，“人类理性提出的问题人类理性一定可以答复的哲学信念，提出23个问题数学问题，其中的第二个问题就是建立整个数学的一致性即无矛盾性或称协调性，20年代希尔伯特本人曾提出了一个使用有穷方法建立实数和分析的一致性的方案，称为希尔伯特元数学方案。所谓有穷方法，粗略地说就是一套可操作的形式化程序，按照这样的程序可以一步一步地在有穷步骤内得到确切结果。1930年获得博士学位之后，为了获得大学授课资格，哥德尔开始沿着希尔伯特方案的道路着手解决希尔伯特第二问题。而不完全性定理正是解决第二问题所得的结果。哥德尔最初是想寻此方案首先建立算术理论的一致性，然后再建立相对于算术

9、而言实数理论的一致性，但出乎意外的是，他得到了与希尔伯特预期完全相反的结果，最终证明了形式算术系统的一致性不能用有穷手段证明。哥德尔首先用一阶谓词逻辑的形式语言陈述皮亚诺算术的五条公理，同时将所形成的算术形式系统记为pa，在发表于1931年的论文?论?数学原理?及有关系统中的形式不可断定命题中，证明了如下两个重要结果：哥德尔第一不完全性定理：假设pa是一致的，那么存在pa命题p，p在pa中不可证；假设pa是一致的，那么p的否认p在pa中不可证1936年罗塞尔j.b.rsser证明可以将条件“一致改为“一致，即系统pa是不完全的，这样的p称为不可断定命题即命题和命题的否认都不是系统的定理。哥德尔

10、第二不完全性定理：假设算术形式系统pa是一致的，那么不可能在系统pa内部证明其一致性。哥德尔的两个不完全性定理可以更一般地表述为：哥德尔第一不完全性定理：任何足以展开初等数论的数学形式系统，假设是一致的，就是不完全的，即其中必定存在不可断定命题；哥德尔第二不完全性定理：任何足以展开初等数论的数学形式系统，假设是一致的，其一致性在系统内不可证。第二不完全性定理的另一种形式：任何足够丰富的数学形式系统，假设是一致的，那么它不能证明表达它自身一致性的命题是定理。哥德尔证明第一不完全性定理的思路是，先在形式系统中构造一个命题p，这个命题形如“p在系统中不可证，进而指出，这个命题p和它的否认p都不是系统

11、的定理，即这个命题在系统中是不可断定的。按照经典逻辑，任何一个命题，或者为真，或者为假，二者必居其一，二者只居其一，即命题和命题的否认必有一真，因此，系统中存在不可断定命题，就意味着系统中存在真的但不可证的命题。事实上，哥德尔构造的命题p身就是一个真的但在系统中不可证的命题。哥德尔证明第二不完全性定理的思路是，既然有事实，假设系统pa是一致的，那么p在系统pa中不可证，那么表达这个事实的论证可以在系统pa中形式化。例如，“系统pa是一致的可以表示为npa，同时把“p在系统pa中不可证就用p表示，相应论证就表示成：npap根据前述，假设npa可证，那么有p即p在系统pa中可证。这显然与第一不完全

12、性定律相矛盾。哥德尔定理第一次向世人澄清了“真与“可证概念的本质区别。由于一个命题在一个形式系统中可证，就意味着遵循推理规那么，可以一步接着一步地在有穷步骤内完成证明过程。但哥德尔指出，即使限制在皮亚诺算术这样狭小的数学范围内，要想用形式化的有穷手段证明它的无矛盾性这一真理都是不可能的。换句话说，任何丰富到足以展开初等数论的形式系统，至少会遗漏一个数学真理，数学形式系统不能囊括所有的数学真理。那么，能不能添加更强的公理扩大原有的系统穷尽所有的数学真理呢？哥德尔说，不行！因为，对于新扩大的系统还会有新的数学真命题在其中不可证，继续扩大，情形仍然如此。实际上，除非你把这种扩张过程持续到超穷，否那么

13、这种系统连最简单的算术真理都不能穷荆哥德尔本人谈及定理证明过程时曾说过，“我在数论形式系统中构造不可断定命题的启发性原那么是将可证性和相对应的高度超穷的客观数学真理概念相区分。看来，可证数学命题和数学真理之间永远隔着一个超穷间隔 ，仅仅使用有穷方法甚至没有希望逼近它。正如哥德尔所说，“数学不仅是不完全的，还是不可完全的，这一点也恰是哥德尔定理最深化的哲学义蕴。3.哥德尔定理在不同语境下的版本显然，哥德尔定理与数学家的最初期望相去甚远，因为，一方面人们期望数学形式系统囊括所有数学真理，一方面又清楚知道总有数学真理不可证；一方面经历和直觉告诉人们数学是一致的不含矛盾的，理性又教导人们数学不能证明它

14、自身的一致性。因此，定理发现之后，人们不得不重新调整自己的思维方式。著名数学家外尔h.eyl当时曾就此感慨到，“上帝是存在的，因为数学无疑是一致的；魔鬼也是存在的，因为我们不能证明这种一致性。这段话形象地道出了当时处于两难境遇的数学家的困惑。甚至有人把哥德尔定理的意义进一步引申：宇宙给了我们一种选择，就人类认知而言，我们要么拥有一本正确的但却是极不完好的小书，要么拥有一本完好的但缺乏内在和谐的大书，我们可以选择完好也可以选择和谐，但鱼和熊掌不可得兼。在我们看来，这些说法不过是哥德尔定理带给人们的某些启示，事实上，哥德尔定理自图灵机概念诞生之后更加凸现其深化和意义深远。1930年代，哥德尔、丘奇

15、a.hurh、克林尼g.j.kleene、图灵等一批数学家开始对直观的“算法可计算概念的数学刻画进展探究，相继提出了-可定义、递归函数和图灵机概念，并给出了影响广远的丘奇-图灵论题：一切算法可计算函数都是递归函数，一切算法可计算函数都是通用图灵机可计算的函数，或者说，每个算法都可在一台通用图灵机上程序化。虽然几种数学刻画是等价的，但是哥德尔最为赞赏图灵机概念，这其中最为重要的是，图灵机概念第一次澄清了形式系统的真正内涵形式系统不过是一种产生定理的机械程序，或者说图灵机的工作程序就是数学家在形式系统中进展工作的程序。有了图灵机概念以后人们开始期望造出能证明所有数学定理的机器，但是，既然图灵机就等

16、价于形式系统，那么形式系统的局限就是图灵机的局限。于是，哥德尔的第一不完全性定理在给出图灵机概念之后就有了如下几种等价说法：1没有数学形式系统既是一致的又是完全的。2没有定理证明机器或机器程序可以证明所有的数学真理。3数学是算法不可完全的。4数学是机器程序不可穷尽的。5停机定理没有任何图灵机程序能断定，任给一个程序p和一套输入i，按照这套输入i运行程序p时，机器是否能停机。即停机问题是图灵机算法不可解的。由于任何数字计算机都是通用图灵机的特例，因此，停机定理说明，本质上，计算机的才能是有限的。1985年，切廷g.j.haitin在?算法信息论?一书中，给出了算法信息论中的哥德尔式不可断定命题，

17、并且给出哥德尔定理的算法信息论版本：6对形式算术系统t而言，可以找到一个数t，它是公理系统t的信息熵，即描绘或处理这些公理所需要的最小信息量，假设k是字为的科尔莫葛洛夫a.n.klgrv复杂性，那么t中一切满足kt的命题在t中不可证。施瓦茨sharz曾就这些结果总结过颇具启发的三句话：“希尔伯特认为，一切事物都是算法可知的；哥德尔认为有些事物不是算法可知的；切廷认为只有少部分事物是算法可知的。可见，哥德尔定理确实深化地变革了我们对于一致性、完全性、真理、可证性和可计算性之间关系的传统认识。曾有人问哥德尔，能否把他的定理推广到数学以外。哥德尔尝试给出了一个自己认为合理的表述：“一个完全不自由的社

18、会即处处按统一法那么行事的社会，就其行为而言，或者是不一致的，或者是不完全的，即无力解决某些可能是极端重要的问题，而当社会面临困境时，这种不一致或者不完全都会危机整个社会的生存。4.哥德尔本人谈不完全性定理的哲学义蕴既然任何一致的形式系统和图灵机程序不能囊括所有的数学真理，而我们人心可以看出它们的真理性，那么哥德尔定理似乎说明，在机器模拟人的智能方面必定存在着某种不能超越的逻辑极限，或者说计算机永远不能做人所能做的一切。于是，一批具有数理背景的科学家和哲学家很难抵御一种诱惑，用哥德尔不完全性定理论证“人心将永远胜过计算机的结论。果真可以作如此论证吗？我们可以考察一下哥德尔本人对他的定理的哲学义

19、蕴的阐释。从哥德尔的一部分手稿和1970年代与数学家王浩的谈话记录中，我们得知，他在不同场合曾屡次谈及不完全性定理的哲学义蕴，甚至1951年的“第25届吉布斯演讲的题目就是“有关数学根底的根本定理及其哲学义蕴，特别是集中于心-脑-计算机-哥德尔定理的关系问题他曾有过许多阐述。哥德尔首先严格区分了心ind、脑brain、计算机的功能后明确断言，人类大脑的功能不过像一台计算机，心与脑同一的观点却是我们时代的偏见，但不完全性定理不能作为“人心胜过计算机论断的直接证据，要推出如此强硬论断还需要其他假定。事实上，在严格区分了心、脑、计算机的功能后，“人心是否胜过计算机的问题可以转换为几个子问题：1是否大

20、脑和心的功能等同？2是否大脑的运作等同于计算机的运作？3是否心的本质是可计算的？这三个问题实际上就是“心脑功能同一论、“大脑的可计算主义和“心的可计算主义是否成立的问题。心脑同一论是20世纪50年代末以来西方占据主流的一种哲学理论，也是人工智能的理论基矗但哥德尔认为，心脑同一论是人们普遍承受的时代偏见，而心的可计算主义是应当得到批判的。首先，哥德尔曾在屡次申明，他本人并不反对用不完全性定理作为证明“人心胜过计算机这一结论的部分证据，因为在他看来，不完全性定理并未给出人类理性的极限，而只提醒了数学形式主义的内在局限，但是，仅仅使用他的定理缺乏以作出如此强硬论断。哥德尔指出，图灵曾给出的“心的过程

21、不能超越机械过程的论证在附加以下两个假定之后才有可能：a没有与物质相别离的心。b大脑的功能根本上像一台数字计算机。他认为b的概然性很高；但无论如何a是将要被科学所否证的时代偏见。实际上，早在1951年的吉布斯演讲稿1995年发表中，哥德尔就指出，附加了希尔伯特主张的“人类理性提出的问题人类理性一定可以解答这样一个哲学假定，有可能从不完全性定理推出“人心胜过计算机的结论，当然，哥德尔本人也倾向于这一假定成立，但同时他也意识到，这种对于“心脑同一论和“心的可计算主义的批判未必会令人信服，因为它毕竟是一种推论式的。值得注意的一点是，哥德尔第二不完全性定理的一种形式是说，任何恰当的定理证明机器，或者定

22、理证明程序，假设它是一致的，那么它不能证明表达它自身一致性的命题是定理。哥德尔认为，人心有洞察具有超穷性质的数学真理的直觉才能，特别是可以洞察数学形式系统的一致性。但是由于形式系统的局限性，一方面，人心不能将他的全部数学直觉形式化，假设人心把他的某些数学直觉形式化了，这件事本身便要产生新的直觉知识如这个形式系统的一致性知识；另一方面，不排除存在一台定理证明机器确实等价于数学直觉这种可能。但重要的在于，假定有这样的机器，由第二不完全性定理，我们不可能证明确实如此。看来，当人们应用哥德尔定理试图严格地作出“人心胜过计算机的论证时，其中包含着一个令人难以觉察的破绽：问题的核心并不在于是否存在能捕获人

23、类直觉的定理证明机器，而恰恰在于，即使存在这样一台机器，也不能证明它确实做到了这一步。恰如哥德尔所说：“不完全性定理并不排除存在事实上等价于数学直觉的定理证明机器。但是定理蕴涵着，我们或者不能确切知道这台机器的详情，或者不能确切知道它是否会准确无误地工作。在纪念现代计算机先驱冯诺意曼j.vnneuann诞辰60周年大会上，哥德尔曾问过一个问题，“一台机器知道自己程序的可能性有多大？这个问题颇似那个幽默的悖论：上帝能否造一块他自己举不起来的石头？事实上，指出这类内涵悖论的自指性的本质恰好是哥德尔定理最深化的义蕴之一。今天，许多人认为计算机不能超过人类心智，就是认为大脑是一个具有高容错机制的系统，

24、同时人的意识具有意向性、自指性和非定域性等特征，这些都是计算机所不能到达的。当然，在哥德尔看来，除了必要的哲学假定之外，答复“人心是否胜过计算机的问题还依赖于我们能否消除内涵悖论，还要取决于包括大脑科学在内的整个科学的进展。5.哥德尔定理对人工智能的启示自不完全性定理诞生之时，定理内在的哲学义蕴就一直是学界争论的话题，特别是在人工智能领域这一争论持续了近半个世纪。1961年美国哲学家鲁卡斯j.luas首先以剧烈言辞撰文?心、机器、哥德尔?，试图用哥德尔定理直接证明“人心超过计算机的结论：“依我看，哥德尔定理证明了机械论是错误的，因为，无论我们造出多么复杂的机器，只要它是机器，就将对应于一个形式

25、系统，就能找到一个在该系统内不可证的公式而使之受到哥德尔构造不可断定命题的程序的打击，机器不能把这个公式作为定理推导出来，但是人心却能看出它是真的。因此这台机器不是心的一个恰当模型。这就是著名的鲁卡斯论证。随后，另一位美国哲学家怀特利.h.hitely发表了强有力的批驳文章?心灵、机器、哥德尔回应鲁卡斯?，遂引起许多人卷入并长达几十年的争论。1979年获普利策文学大奖的美国畅销书?哥德尔、艾舍、巴赫一条永久的金带?将艾舍尔义蕴深化的版画、巴赫脍炙人口的?音乐的奉献?乐章与哥德尔定理戏剧性地连接在一起，试图从多个视角说明如何用哥德尔定理否证强人工智能方案，谱写了一首心-脑-计算机的“隐喻赋格曲。

26、1963年，美国哲学家、认知科学家德莱弗斯h.dreyfus出版了?计算机不能做什么？人工理性批判?，1982年和1986年又相继出版了?胡塞尔、意向性和认知科学?与?心灵优于机器：人的直觉在计算机时代的力量?等，批判了强人工智能的观点，反对把人仅仅看成一种抽象的推理机器。他认为，与机器不同，人具有识别、综合以及直觉洞察的才能，这些才能植根于一些与计算机程序的计算理性截然不同的过程中，直觉智能的力量使人可以理解、言说以及巧妙地调整我们与外部环境的关系。1989年，英国数学家、物理学家罗杰彭罗斯r.penrs在风行全球的?皇帝新脑计算机、心智和物理定律?一书中，对鲁卡斯论证又作了进一步扩展,指出

27、数学真理的概念不能包容于任何形式主义的框架之中，人心，特别是人的意识完全是非算法的，计算机不过是强人工智能专家所钟爱的一副“皇帝新脑而已，被称为“哥德尔定理惊人的强应用，并由此引发了1990年?行为和大脑科学?杂志上许多人介入的一场争论。1997年和1998年当代语言哲学家，强人工智能的反对者塞尔j.r.searle相继出版?意识之迷?与?心灵、语言和社会?等著作，断言仅仅依靠单纯的输入输出，计算机不可能完全模拟人的意识活动。塞尔通过他的所谓“中文屋概念批驳了强人工智能专家所持有观点。在塞尔看来，计算机与人类的心智相比，其理解力不仅是不完全的，而且可以说完全是空白。他认为，假设我们所说的机器是

28、指一个具有某种功能的物理系统，或者只从计算的角度讲，大脑就是一台计算机，然而在他看来，心的本质并非如此。因为计算机程序纯粹是按照语法规那么来定义的，而语法本身缺乏以担保心的意向性和语义的呈现，程序的运行只具有在机器运行时产生下一步形式化的才能，只有那些使用计算机并给计算机一定输入同时还能解释输出的人才具有意向性。意向性是人心特有的功能，心的本质绝不能被程序化，也就是说，心的本质不是算法的。我们看到，今天的计算机在数值计算、蛮力搜索等方面已大大超过人类，但是在模糊识别、感知和在复杂境域中进展决策的才能却无法与人相比，甚至最先进的计算机不能模拟一个3岁儿童的智能，那么，这其中真正的障碍终究在哪里？

29、人们最初是从希尔伯特元数学方案开始考虑问题的，是想用有穷手段，用能行的方法建立一个没有内在矛盾的形式系统囊括所有的数学真理，哥德尔告诉我们，这样做不可能。但是，今天我们仍然在追求一种严格一致的算法来模拟人的智能，人工智能领域长期以来一直是在图灵的算法概念根底上产生的基于符号的“认知可计算主义的纲领指导下工作，但是这种纲领已经越来越显示出它的局限，这一局限本质上正是哥德尔定理早就断言的形式系统的局限。那么计算机和人的智能的本质区别终究何在？人类智能和认知的本质终究为何？是否像哥德尔断定的，存在与物质相别离的心能超越任何计算机去发现和证明某些数学定理，至少在发现具有超穷性质的数学真理、提出数学公理

30、、构造数学猜想方面是任何计算机都无法企及的？抑或像彭罗斯断言的那样，人心能超越任何计算机实现非算法的运算，而且人心具有的某种特殊才能是建立在迄今未予发现的物理学规律的根底上？这些问题至今并无定论。至少，目前我们无法确定“心不是计算机的结论为真。而且，人工智能是否存在某种不可逾越的逻辑极限？基于图灵算法概念的计算概念可否超越？这些都是源自对哥德尔定理的发人深思的问题，但问题的最终解决还需要更深化的科学的进展。1997年曾任美国数学会主席的斯梅尔s.sale效仿数学家希尔伯特向全世界数学家提出了21世纪需要解决的24个数学问题，其中的第18个问题是，“人类智能的极限和人工智能的极限是什么？并且指出，这个问题与哥德尔不完全性定理有关。值得指出的是，哥德尔曾经说过一句耐人寻味的话