1. 哥德爾其人

假如讓人們列舉出20世紀(jì)影響人類思想的十大偉人，恐怕愛因斯坦（Albert Einstein）、圖靈（Alant Turing）、哥德爾（Kurt G?del）和凱恩斯（John Keynes）應(yīng)榜上有名，事實(shí)上，這四位也恰是2002年美國(guó)《時(shí)代周刊》上列出的“20世紀(jì)震撼人類思想界的四大偉人”，足見這四位大家思想之重要而深遠(yuǎn)。然而，對(duì)于物理學(xué)家愛因斯坦、理論計(jì)算機(jī)之父圖靈，以及經(jīng)濟(jì)學(xué)家凱恩斯的工作，一般人總還略知一二，但大多數(shù)人對(duì)作為數(shù)學(xué)家和邏輯學(xué)家的哥德爾的思想就知之不祥，更知之不確了。
庫(kù)爾特?哥德爾1906年出生在摩拉維亞的布爾諾城，是一個(gè)生活條件屬中產(chǎn)階級(jí)的奧地利日爾曼裔家庭的第二個(gè)兒子，父親是一家紡織廠的合伙經(jīng)營(yíng)人，母親是受過良好教育的家庭婦女。1924年哥德爾入維也納大學(xué)學(xué)習(xí)，最初主修物理和數(shù)學(xué)，后來在維也納小組的激勵(lì)下開始學(xué)習(xí)邏輯。1930年獲哲學(xué)博士學(xué)位，1933年獲維也納大學(xué)執(zhí)教資格。1940年遷居美國(guó)任普林斯頓研究院研究員，1948年加入美國(guó)國(guó)籍，1976年退休，1978年由于精神紊亂死于拒絕進(jìn)食造成的營(yíng)養(yǎng)枯竭。
哥德爾的一生可以說是傾力獻(xiàn)身基礎(chǔ)理論研究的一生，他的學(xué)術(shù)貢獻(xiàn)基本上是在數(shù)學(xué)、邏輯和哲學(xué)領(lǐng)域。1929-1938年間哥德爾作出數(shù)理邏輯領(lǐng)域三大貢獻(xiàn)：證明一階謂詞演算的完全性；證明算術(shù)形式系統(tǒng)的不完全性；證明連續(xù)統(tǒng)假設(shè)和集合論公理的相對(duì)一致性，這些結(jié)果不僅使邏輯學(xué)發(fā)生了革命，而且對(duì)數(shù)學(xué)、哲學(xué)、計(jì)算機(jī)和認(rèn)知科學(xué)都有非常重大的影響。特別是電子計(jì)算機(jī)誕生之后，哥德爾的不完全性定理的深刻性更加受到學(xué)界的關(guān)注。只是稍稍出乎人們意料的是，作出這幾個(gè)劃時(shí)代結(jié)果后，自1940年以后，哥德爾除了繼續(xù)思考一些集合論問題，有5年時(shí)間熱中相對(duì)論并得到一個(gè)受愛因斯坦贊賞的結(jié)果外，大部分時(shí)間傾注了哲學(xué)問題的研究。他一生著述很少，極少公開演講，只出版過一部著作，發(fā)表文字不及300頁(yè)，從未構(gòu)造過任何完整的理論體系，甚至沒有一個(gè)真正意義上自己的學(xué)生，他的大部分思想記錄在手稿、私人通信和談話記錄中。
哥德爾曾被許多人看作帶有神秘色彩的人物，一方面是因?yàn)樗牟煌耆远ɡ淼倪壿嬐庖率勾蠖鄶?shù)人難覓其思想的內(nèi)在義蘊(yùn)，另一方面也因?yàn)閷?duì)于他的個(gè)性和精神狀況流傳著一些坊間神話。但是可以肯定的，哥德爾不僅以精湛?jī)?yōu)雅的工作作出了令世人矚目的科學(xué)貢獻(xiàn)，還以卓然深刻的思想為世人留下一筆豐厚的哲學(xué)遺產(chǎn)。哥德爾一生特立獨(dú)行，始終如一地將一流的人格品質(zhì)、高遠(yuǎn)的科學(xué)鑒賞力、超凡的創(chuàng)造性和至為嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)融為一體，傾其全力獻(xiàn)身基礎(chǔ)理論研究工作，在這個(gè)充滿競(jìng)爭(zhēng)的世界上，他完全采取了一種“超然于競(jìng)爭(zhēng)之上”的生活態(tài)度。王浩曾將哥德爾與愛因斯坦相提并論，稱他們是哲人科學(xué)家中的“稀有品種”。到目前為止，由一流數(shù)學(xué)家和邏輯學(xué)家組成的編委會(huì)負(fù)責(zé)編輯出版的《哥德爾文集》已經(jīng)于1986、1990、1995年出版了前三卷，其他各卷還將陸續(xù)出版，借助《哥德爾文集》，我們必將逐步走進(jìn)哥德爾的精神世界，進(jìn)一步理解其思想的博大精深。

2. 哥德爾的不完全性定理

哥德爾思想最深刻地體現(xiàn)在為世人稱道的不完全性定理之中。為了理解這一定理的深刻內(nèi)涵，我們首先了解一下一階謂詞邏輯的完全性問題。
我們知道，自然語言中包含著各種隱喻的成分和模糊之處，在使用中常常需要依賴于使用語言的語境，用自然語言進(jìn)行推理往往會(huì)產(chǎn)生歧義，帶來意義的不確定性，因此在萊布尼茲時(shí)代，邏輯學(xué)家們就希望引進(jìn)一套意義單一明確的人工符號(hào)，構(gòu)造一套形式語言來嚴(yán)格、清晰地整理日常推理和數(shù)學(xué)推理。為此目的，1879年弗雷格（G.Frege）提出第一個(gè)初等邏輯的形式系統(tǒng)（未完全形式化），1910 年羅素（B.Russell）在《數(shù)學(xué)原理》中給出了一階謂詞邏輯的形式系統(tǒng)PM，1928年希爾伯特（D.Hilbert）和阿克曼（W.Ackerman）又引進(jìn)了形式系統(tǒng)HA，基本特征都是引進(jìn)了一套人工語言代替自然語言。一般來講，在一個(gè)形式系統(tǒng)中，各種陳述都表示成有窮長(zhǎng)度的符號(hào)串，系統(tǒng)的形成規(guī)則指明什么樣的符號(hào)串是合法的公式，一些符號(hào)串被當(dāng)作公理。系統(tǒng)中還包括一系列推理規(guī)則，指明什么是系統(tǒng)中定理的證明。一個(gè)證明就是從公理出發(fā)對(duì)公式變形而形成的有窮長(zhǎng)的公式序列，序列中的每一個(gè)公式，或者是公理，或者是由在前的公式依照推理規(guī)則形成的公式，而且系統(tǒng)中每一個(gè)定理都是這樣經(jīng)過有窮步驟得到的結(jié)果。到了20世紀(jì)20年代，這三個(gè)系統(tǒng)已經(jīng)為邏輯學(xué)家們所普遍接受。問題是，這樣的形式系統(tǒng)是否能囊括所有的邏輯真理？于是，希爾伯特1928年明確提出問題，證明一階謂詞邏輯系統(tǒng)具有完全性。
一年以后，哥德爾在他1929 年完成的博士論文中證明，包括弗雷格、羅素和希爾伯特-阿克曼的一階謂詞邏輯的形式系統(tǒng)，都具有一種語義完全性，即所有普遍有效式都可在一階謂詞邏輯系統(tǒng)中作為定理得到證明，所謂普遍有效式，就是在一切論域中都真的公式。這一結(jié)果表明，一階謂詞邏輯系統(tǒng)在刻畫那些邏輯真理方面是足夠充分的。
既然一階謂詞邏輯具有如此強(qiáng)大的能力，邏輯學(xué)家們期望借助它構(gòu)造整個(gè)數(shù)學(xué)的形式系統(tǒng)，從而用形式化手段證明所有的數(shù)學(xué)真理。事實(shí)上，1900年巴黎數(shù)學(xué)家會(huì)議上，希爾伯特遵從“世界上沒有不可知”，“人類理性提出的問題人類理性一定能夠回答”的哲學(xué)信念，提出23個(gè)問題數(shù)學(xué)問題，其中的第二個(gè)問題就是建立整個(gè)數(shù)學(xué)的一致性（即無矛盾性或稱協(xié)調(diào)性），20年代希爾伯特本人曾提出了一個(gè)使用有窮方法建立實(shí)數(shù)和分析的一致性的方案，稱為希爾伯特元數(shù)學(xué)方案。所謂有窮方法，粗略地說就是一套可操作的形式化程序，依照這樣的程序可以一步一步地在有窮步驟內(nèi)得到確切結(jié)果。1930年獲得博士學(xué)位之后，為了獲得大學(xué)授課資格，哥德爾開始沿著希爾伯特方案的路線著手解決希爾伯特第二問題。而不完全性定理正是解決第二問題所得的結(jié)果。哥德爾最初是想尋此方案首先建立算術(shù)理論的一致性，然后再建立相對(duì)于算術(shù)而言實(shí)數(shù)理論的一致性，但出乎意外的是，他得到了與希爾伯特預(yù)期完全相反的結(jié)果，最終證明了形式算術(shù)系統(tǒng)的一致性不能用有窮手段證明。
哥德爾首先用一階謂詞邏輯的形式語言陳述皮亞諾算術(shù)的五條公理，同時(shí)將所形成的算術(shù)形式系統(tǒng)記為PA，在發(fā)表于1931年的論文《論《數(shù)學(xué)原理》及有關(guān)系統(tǒng)中的形式不可判定命題Ⅰ》中，證明了如下兩個(gè)重要結(jié)果：
哥德爾第一不完全性定理：如果PA是一致的，則存在PA命題P， P在PA中不可證；如果PA是ω一致的，則P的否定﹁P在PA中不可證（1936年羅塞爾（J.B.Rosser）證明可以將條件“ω一致”改為“一致”），即系統(tǒng)PA是不完全的，這樣的P稱為不可判定命題（即命題和命題的否定都不是系統(tǒng)的定理）。
哥德爾第二不完全性定理：如果算術(shù)形式系統(tǒng)PA是一致的，則不可能在系統(tǒng)PA內(nèi)部證明其一致性。
哥德爾的兩個(gè)不完全性定理可以更一般地表述為：
哥德爾第一不完全性定理：任何足以展開初等數(shù)論的數(shù)學(xué)形式系統(tǒng)，如果是一致的，就是不完全的，即其中必定存在不可判定命題；
哥德爾第二不完全性定理：任何足以展開初等數(shù)論的數(shù)學(xué)形式系統(tǒng)，如果是一致的，其一致性在系統(tǒng)內(nèi)不可證。
第二不完全性定理的另一種形式：任何足夠豐富的數(shù)學(xué)形式系統(tǒng)，如果是一致的，那么它不能證明表達(dá)它自身一致性的命題是定理。
哥德爾證明第一不完全性定理的思路是，先在形式系統(tǒng)中構(gòu)造一個(gè)命題P，這個(gè)命題形如“P在系統(tǒng)中不可證”， 進(jìn)而指出，這個(gè)命題P和它的否定﹁ P都不是系統(tǒng)的定理，即這個(gè)命題在系統(tǒng)中是不可判定的。依照經(jīng)典邏輯，任何一個(gè)命題，或者為真，或者為假，二者必居其一，二者只居其一，即命題和命題的否定必有一真，因此，系統(tǒng)中存在不可判定命題，就意味著系統(tǒng)中存在真的但不可證的命題。事實(shí)上，哥德爾構(gòu)造的命題P身就是一個(gè)真的但在系統(tǒng)中不可證的命題。
哥德爾證明第二不完全性定理的思路是，既然有事實(shí)，如果系統(tǒng)PA是一致的，則P在系統(tǒng)PA中不可證，那么表達(dá)這個(gè)事實(shí)的論證可以在系統(tǒng)PA中形式化。例如，“系統(tǒng)PA是一致的”可以表示為Con（PA），同時(shí)把“P在系統(tǒng)PA中不可證”就用P表示，相應(yīng)論證就表示成：
├ Con（PA）→ P
根據(jù)前述，如果 Con（PA）可證，則有
├ P
即P在系統(tǒng)PA中可證。這顯然與第一不完全性定律相矛盾。
哥德爾定理第一次向世人澄清了“真”與“可證”概念的本質(zhì)區(qū)別。由于一個(gè)命題在一個(gè)形式系統(tǒng)中可證，就意味著遵循推理規(guī)則，能夠一步接著一步地在有窮步驟內(nèi)完成證明過程。但哥德爾指出，即使限制在皮亞諾算術(shù)這樣狹小的數(shù)學(xué)范圍內(nèi)，要想用形式化的有窮手段證明它的無矛盾性這一真理都是不可能的。換句話說，任何豐富到足以展開初等數(shù)論的形式系統(tǒng)，至少會(huì)遺漏一個(gè)數(shù)學(xué)真理，數(shù)學(xué)形式系統(tǒng)不能囊括所有的數(shù)學(xué)真理。那么，能不能添加更強(qiáng)的公理擴(kuò)充原有的系統(tǒng)窮盡所有的數(shù)學(xué)真理呢？哥德爾說，不行！因?yàn)?，?duì)于新擴(kuò)充的系統(tǒng)還會(huì)有新的數(shù)學(xué)真命題在其中不可證，…… 繼續(xù)擴(kuò)充，情形依然如此。實(shí)際上，除非你把這種擴(kuò)張過程持續(xù)到超窮，否則這種系統(tǒng)連最簡(jiǎn)單的算術(shù)真理都不能窮盡。哥德爾本人談及定理證明過程時(shí)曾說過，“我在數(shù)論形式系統(tǒng)中構(gòu)造不可判定命題的啟發(fā)性原則是將可證性和相對(duì)應(yīng)的高度超窮的客觀數(shù)學(xué)真理概念相區(qū)分”?？磥恚勺C數(shù)學(xué)命題和數(shù)學(xué)真理之間永遠(yuǎn)隔著一個(gè)超窮距離，僅僅使用有窮方法甚至沒有希望逼近它。正如哥德爾所說，“數(shù)學(xué)不僅是不完全的，還是不可完全的”，這一點(diǎn)也恰是哥德爾定理最深刻的哲學(xué)義蘊(yùn)。

3. 哥德爾定理在不同語境下的版本

顯然，哥德爾定理與數(shù)學(xué)家的最初期望相去甚遠(yuǎn)，因?yàn)?，一方面人們期望?shù)學(xué)形式系統(tǒng)囊括所有數(shù)學(xué)真理，一方面又分明知道總有數(shù)學(xué)真理不可證；一方面經(jīng)驗(yàn)和直覺告訴人們數(shù)學(xué)是一致的不含矛盾的，理性又教導(dǎo)人們數(shù)學(xué)不能證明它自身的一致性。因此，定理發(fā)現(xiàn)之后，人們不得不重新調(diào)整自己的思維方式。著名數(shù)學(xué)家外爾（H.Weyl）當(dāng)時(shí)曾就此感慨到，“上帝是存在的，因?yàn)閿?shù)學(xué)無疑是一致的；魔鬼也是存在的，因?yàn)槲覀儾荒茏C明這種一致性?！边@段話形象地道出了當(dāng)時(shí)處于兩難境遇的數(shù)學(xué)家的困惑。甚至有人把哥德爾定理的意義進(jìn)一步引申：宇宙給了我們一種選擇，就人類認(rèn)知而言，我們要么擁有一本正確的但卻是極不完整的小書，要么擁有一本完整的但缺乏內(nèi)在和諧的大書，我們可以選擇完整也可以選擇和諧，但魚和熊掌不可得兼。在我們看來，這些說法不過是哥德爾定理帶給人們的某些啟示，事實(shí)上，哥德爾定理自圖靈機(jī)概念誕生之后更加凸現(xiàn)其深刻和意義深遠(yuǎn)。
1930年代，哥德爾、丘奇（A.Church）、克林尼（G.J.Kleene）、圖靈等一批數(shù)學(xué)家開始對(duì)直觀的“算法可計(jì)算”概念的數(shù)學(xué)刻畫進(jìn)行探索，相繼提出了λ-可定義、遞歸函數(shù)和圖靈機(jī)概念，并給出了影響廣遠(yuǎn)的丘奇-圖靈論題：一切算法可計(jì)算函數(shù)都是遞歸函數(shù)，一切算法可計(jì)算函數(shù)都是通用圖靈機(jī)可計(jì)算的函數(shù)，或者說，每個(gè)算法都可在一臺(tái)通用圖靈機(jī)上程序化。雖然幾種數(shù)學(xué)刻畫是等價(jià)的，但是哥德爾最為贊賞圖靈機(jī)概念，這其中最為重要的是，圖靈機(jī)概念第一次澄清了形式系統(tǒng)的真正內(nèi)涵——形式系統(tǒng)不過是一種產(chǎn)生定理的機(jī)械程序，或者說圖靈機(jī)的工作程序就是數(shù)學(xué)家在形式系統(tǒng)中進(jìn)行工作的程序。有了圖靈機(jī)概念以后人們開始期望造出能證明所有數(shù)學(xué)定理的機(jī)器，但是，既然圖靈機(jī)就等價(jià)于形式系統(tǒng)，那么形式系統(tǒng)的局限就是圖靈機(jī)的局限。于是，哥德爾的第一不完全性定理在給出圖靈機(jī)概念之后就有了如下幾種等價(jià)說法：
（1）沒有數(shù)學(xué)形式系統(tǒng)既是一致的又是完全的。
（2）沒有定理證明機(jī)器（或機(jī)器程序）能夠證明所有的數(shù)學(xué)真理。
（3）數(shù)學(xué)是算法不可完全的。
（4）數(shù)學(xué)是機(jī)器程序不可窮盡的。
（5）停機(jī)定理——沒有任何圖靈機(jī)程序能判定，任給一個(gè)程序P和一套輸入I，依照這套輸入I運(yùn)行程序P時(shí)，機(jī)器是否能停機(jī)。即停機(jī)問題是圖靈機(jī)算法不可解的。由于任何數(shù)字計(jì)算機(jī)都是通用圖靈機(jī)的特例，因此，停機(jī)定理表明，本質(zhì)上，計(jì)算機(jī)的能力是有限的。
1985年，切廷（G.J.Chaitin）在《算法信息論》一書中，給出了算法信息論中的哥德爾式不可判定命題，并且給出哥德爾定理的算法信息論版本：
（6）對(duì)形式算術(shù)系統(tǒng)T而言，可以找到一個(gè)數(shù)CT，它是公理系統(tǒng)T的信息熵，即描述或處理這些公理所需要的最小信息量，如果K（w）是字為w的科爾莫葛洛夫（A.N.Kolmogorov）復(fù)雜性，則T中一切滿足K（w）> CT 的命題在T中不可證。
施瓦茨（Schwarz）曾就這些結(jié)果總結(jié)過頗具啟發(fā)的三句話：“希爾伯特認(rèn)為，一切事物都是 [算法]可知的；哥德爾認(rèn)為有些事物不是[算法]可知的；切廷認(rèn)為只有少部分事物是[算法]可知的”?？梢?，哥德爾定理確實(shí)深刻地變革了我們對(duì)于一致性、完全性、真理、可證性和可計(jì)算性之間關(guān)系的傳統(tǒng)認(rèn)識(shí)。
曾有人問哥德爾，能否把他的定理推廣到數(shù)學(xué)以外。哥德爾嘗試給出了一個(gè)自己認(rèn)為合理的表述：“一個(gè)完全不自由的社會(huì)（即處處按統(tǒng)一法則行事的社會(huì)），就其行為而言，或者是不一致的，或者是不完全的，即無力解決某些可能是極端重要的問題，而當(dāng)社會(huì)面臨困境時(shí)，這種不一致或者不完全都會(huì)危機(jī)整個(gè)社會(huì)的生存?！?/div>