演算法、圖靈機、哥德爾定理與知識的不確定性

文史 08-22

實用實用還是實用

《人文社科項目申報300問》

演算法、圖靈機、哥德爾定理

與知識的不確定性

王榮江

作者簡介：王榮江(1963-)，江蘇宿遷人，哲學博士，淮陰師範學院經法系副教授，主要研究方向是科學思想史和科學認識論。淮陰師範學院經法系，江蘇淮安223001

人大複印：《科學技術哲學》2002 年 07 期

原發期刊：《自然辯證法研究》2002 年第 03 期第 48-51 頁

關鍵詞：演算法/ 圖靈機/ 哥德爾定理/ 知識/ 不確定性/ algorithm/ turing machine/ Godel s theorems/ knowledge/ uncertai-nty/

摘要：知識論一直在尋求對知識的確定性作一般演算法式的邏輯證明的辯護。然而，即使在處理抽象的數量概念的數學基礎研究中，也不能達到最終邏輯證明的確定性。圖靈對停機問題的演算法步驟的否定回答、哥德爾定理對真理的「不可證明性」的確立，使我們不得不面對知識中邏輯證明背後不確定性的東西。

知識論中，一般地把知識定義為「被證明為合理的真信念」[1](justified true belief)，知識被描述為同時滿足三個條件的陳述：S知道P當且僅當：P為真；S相信P；S有充分的理由相信P。這裡知識的定義指的是命題知識(knowledge that P)，它不是定義像「我知道柏拉圖」句式中通過熟知而得到的知識，也不是定義「如何的知識」(knowledge-how)，而是強調它必須有充分的理由讓人相信。即信念不僅僅由它是真的這一事實證明為合理的，它還必須有充分的理由，才能稱之為「知識」；它要求的不僅僅是被結果證明為正確的，還必須是事前的正當理由。

知識論從古希臘將「知識」與「意見」嚴格區分開始，一直在尋求那確定無疑的絕對真理的證明主義道路上發展。知識論家的工作就是要思考真正的知識應該符合的標準，通過什麼樣的方法能達到真正知識的標準，如何能將知識與真正的信念相區別，驅除或然性而達到確定性。這樣的研究在現當代，以研究科學理論知識的科學哲學的形式表現出來。科學哲學家感興趣的是，對特定發現方法所獲得的科學知識在多大程度上是確定的，即科學哲學家想知道科學知識是否有那麼一部分是確定無疑的，不會在任何可設想的條件下被修正，以及它是如何達到這樣的確定性的。今天，這樣的知識論努力似乎已不可能，科學知識不但沒有我們人類想要達到的確定性，彷彿又走向了它的反面——不確定性。科學哲學走過了從基礎論到整體論再到相對主義的發展過程，直至後現代主義，實踐著認識論的不可能主義——「一種無處不在的、極端的、無法克服的不確定性，一種認識論上的虛無主義。」[2]我們如何來理解這一點？

當然，知識論者並不關心我們是否認識某個特定的可靠的真理性知識，而是關心我們是否有理由能要求認識整個某一類的真理性知識。在知識論中，我們似乎不能直接回答上述問題，有關演算法、圖靈機和哥德爾定理卻能為我們提供一種有效的理解途徑。

演算法是一個古老的數學概念。它由9世紀波斯的一位數學家提出。當然，在古希臘就有演算法的實例，比如，現在被稱為歐幾里德演算法的，找兩個數的最大公約數的步驟就是一例。演算法事實上是解題的系統步驟。一般演算法概念的準確表達只是從本世紀起才有記載，特別是30年代給出了這一概念的不同描述。阿倫·圖靈在1936年提出的「圖靈機」概念，是一般演算法的典型代表。其目的是為了解決「希爾伯特第十問題」——數學問題的一般演算法步驟問題，也就是在原則上是否存在一般數學問題的解題步驟的判決問題。希爾伯特的規劃是要把數學置於無懈可擊的牢固的基礎上，其中的公理和步驟法則一旦確立就不再改變。他想一勞永逸地解決數學的可靠性問題。1931年，庫爾特·哥德爾提出的定理證明了希爾伯特規劃的不可能。圖靈關心的判決問題超出任何按公理系統的特殊的數學形式，他的問題是：是否存在能在原則上一個接一個地解決所有數學問題的某種一般的機械步驟。圖靈發現，他可以把這個問題重述成他的形式，即決定把第n台圖靈機作用於數m時事實上是否停機的問題。因而被稱為停機問題。於是，圖靈機的問題是這樣的問題：存在某種完全自動地回答一般問題，即停機問題的演算法步驟嗎？圖靈的回答是：這根本不存在。圖靈是通過證明不存在決定圖靈機停機問題的演算法來證明不存在判定所有數學問題是否可解的問題。

當然，這不是說，在任何個別的情形下，我們不可能決定某些特殊數學問題的真理或非真理，或者決定某一台給定的圖靈機是否會停止。我們可以利用一些技巧或者僅僅是常識，就能在一定情況下決定這種問題。但是，不存在一個對所有的數學問題，也不存在對所有圖靈機以及所有它們可能作用的數都有效的一個演算法。也就是說，這不是一個單獨問題的不可解性，而是關於問題的族的演算法的不可解性。在任何單獨的情形下，答案或者為「是」或者為「非」它肯定存在一個決定那個特定情形的演算法。當然，困難在於我們可能不知道用這些演算法中的哪一個。這就是決定一個單獨陳述而不是決定一族陳述的數學真理的問題。正如羅傑·彭羅斯所說：「重要的是要意識到，演算法本身不能決定數學真理。一個演算法的成立總是必須由外界的手段來建立起來。」[3]希爾伯特的希望，是對於任何一串代表一個數學命題的符號，譬如P，人們應能證明或者P或者非P，依P是真的還是偽的而定。如果這一希望能被實現，這甚至使我們不必為這些命題的意義憂慮。P僅僅為一語法正確的符號串。如果P為一定理（也就是可在系統內證明P），則符號串P的真值就可被賦予真；另一方面，如果能證明非P為定理的話，則可被賦予偽。為了使這些有意義，我們除了完備性外還需要一致性。也就是說，不應有P和非P都為定理的符號串P，否則P會同時是真的和偽的。

哥德爾定理指出，不管任何精確（形式化）數學公理和不同法則系統，如果它足夠寬廣於包容簡單算術命題的描述並且其中沒有矛盾，則必然包含某些用在該系統內所允許的手段既不能證實也不能證偽的陳述。也就是說，公理系統本身的協調性的陳述被編碼成適當的算術問題後，必然成為一道「不能決定的」命題。

哥德爾定理所要說明的問題，在羅素髮現的集合悖論中已經存在。在開始的時候，羅素並沒有認識到集合悖論的根本性，他還是和他的合作者懷特海著手發展一種高度形式化的公理和步驟法則的數學系統，試圖要把所有正確的數學推理翻譯到他們的規劃中去。當然，他們非常仔細地選擇法則以防止導致羅素悖論那樣的推理類型，但是他們的計劃也必然在哥德爾定理面前破產。

哥德爾定理說，甚至在良定義（沒有悖論）的數學公理系統中，存在著根據這些公理所無法證明的一些問題。即在這個系統中存在著既不能證明也不能否證的明確命題。即使我們求助於可能解決這一問題的更大的公理系統，在這個新的系統中也同樣存在不可判定的命題。用波蘭尼的話說，「這就表明我們從來沒有完全知道我們的公理意味著什麼，因為如果我們知道的話，我們就可以避免在一個公理中斷言另一個公理所否定的東西的可能性。對於任何特定的演繹體系來說，這種不確定性是可以通過把它轉換成一個較廣泛的公理體系而消除的，這樣，我們就可以證明原來的體系的一致性。但是，任何這樣的證明也還是不確定的，也就是說，較廣泛的體系的一致性將總是不可判定的。」[4]這樣，用什麼方法能確定數學真理或邏輯真理就變得有些茫然了。最為根本的一點是，那種原有的從古希臘哲學開始就已形成的，並在近代科學中得到充分應用的科學知識觀——設計一組公理並通過邏輯論證的方式從中推出自然界的一切現象——確定性信念必須拋棄。

事實上，哥德爾確立的「不可證明性」的真理和羅素悖論的論證之間的相似性，與圖靈解決停機問題的圖靈機不存在的論證有相似性。這些相似性不是偶然的，它們之間存在有內在的歷史連接的脈絡：圖靈是在研習哥德爾工作之後才找到它的論證的；哥德爾本人非常熟悉羅素的悖論，並能把這一類將邏輯延伸得這麼遠的悖論的推理轉化成有效的數學論證。

為什麼我們應該接受哥德爾和圖靈的論證，而必須排斥導致羅素悖論的推理呢？事實上，前者更直接明了得多，並且作為數學論證更為有力而出人意料，羅素悖論則依靠牽涉到「巨大」集合的更為模糊的推理。但是必須承認，其差別並不真像人們以為的那麼清楚。弄清這些差別的企圖是整個形式主義觀念的強大動機。哥德爾的論斷表明，嚴格的形式主義者的觀點是不能成立的，但他沒有向我們指出另外完整的可信賴的觀點。這問題仍未得到解決。當代數學中為了避免導致羅素悖論的「巨大的」集合的推理的類型所實際採用的步驟是不能完全令人滿意的。而且，它仍然試圖以明晰的形式主義的術語來表達，換句話說，按照我們並不完全相信不會出現矛盾的術語來描述。

彭羅斯認為，無論情況如何，哥德爾論證的清楚推論是，「數學真理的概念不能包容於任何形式主義的框架之中。數學真理是某種超越純粹形式主義的東西。甚至即使沒有哥德爾定理，這一點也是清楚的。」[5]在我們試圖去建立任何一個形式系統時，我們在決定採取什麼公理和法則的指導，總是在給定系統的符號的「意義」下對何為「自明正確」的直覺理解。並且，根據關於「自明」和「意義」的直觀理解，我們如何決定採用哪個形式系統是有意義的，哪個是沒意義的，以自身具有一貫性的概念來決定也是不夠的。「人們可以有許多自身具有一貫性但在含義上沒有『意義』的系統，它們的公理和步驟法則具有錯誤的意義，或者根本沒有意義。甚至在沒有哥德爾定理時，『自明』和『意義』的概念仍然是需要的。」[6]

對科學知識而言，其真理性不能完全容納在純粹邏輯證明的形式主義之中，它是超越邏輯證明和規範性的運作的。只有在科學世界觀信念的意義確定了的情況下，才有對科學假說的自明性的理解及其邏輯的真理證明。

如果沒有哥德爾定理，人們可能想像：「自明」和「意義」的直覺概念只要在開始建立形式系統時用一次就好了，而此後就與決定真理的清楚的數學論證不相干。這樣，按照形式主義者的觀點，這些直覺概念在發現適當形式的論證時，作為數學的初步思維或導引而起作用，而在實際展示數學真理時不起作用。彭羅斯指出，哥德爾定理表明，上述觀點在數學基本哲學中不能真正站住腳。他說：「數學真理的觀念遠遠超越形式主義的整個概念。關於數學真理存在某些絕對的『上帝賦予』的東西。」「任何特定的形式系統都具有臨時和『人為』的品格，在數學的討論中，這類系統的確起著非常有價值的作用。但是它只能為真理提供部分（或近似）的導引。真正的數學真理超越於人為的構造之外。」[7]這一關於數學真理的觀點，完全適應於科學知識真理。

按照哥德爾定理，無論我們構造出多麼複雜的理論，它都有一個表述的形式系統，但在這個系統內都有一個不可證的公式，這個公式不能作為定理在該系統內被推導出來。但是這種形式化（人類不可避免的認識形式）的不能證明性，是否就意味著認識本身的不可能和不正確呢？

彭羅斯持一種「人心超過計算機」的觀念。認為從哥德爾定理可以得出，人類判定數學真理的過程是超越任何演算法的。因為，意識是我們賴以理解數學真理的關鍵，這種意識是我們能夠借直覺的洞察力「看出」某些在數學形式系統中不能證明的數學命題的真理性，而意識是不能被形式化的，它必定是非演算法的。計算機只能處理有演算法的東西，因而計算機不過是強人工智慧專家所鍾愛的「皇帝新腦」而已。

在哥德爾本人看來，他的不完全定理並未給出人類理性的極限，只揭示了數學中形式主義的內在局限性[8]。這是任何形式主義的內在局限性，知識論中的主流學派的證明主義也不能例外，它並不能完成其自身提出的為知識真理作辯護的任務，甚至這樣的努力還會掩蓋和扼殺科學知識中的智慧和創造性的特徵。

人類能否超越自身——或者，計算機程序能否跳出自身，這可能是一切認識的根本性的問題。哥德爾定理是說，數論形式系統能談論自身，但不能超越自身。一個計算機可以修改自身的程序，但不能違背自身的指令——充其量只能通過服從自身的指令來改變自身的某些部分。在科學認識與其認識成果——知識——之間也存在這樣的關係，科學認識是一個極為複雜的過程，它的結果不能因其結果的形式表達系統的不完全性而得以否定。

科學知識的基礎無疑是數學，從近代科學對自然的數學化努力以來，可以說正是數學為我們有效地描述現實世界提供了可能，也正是數學的確定性確保了科學理論的確定性。愛因斯坦說過，令他幼年時代難忘的兩件事情中的一件事是他看了一本歐幾里德幾何學的啟蒙教科書。書中都是些確定的論斷，並且都達到了非常精確的證明而讓人無法懷疑。正是這種明澈和確定性給他留下了不可泯滅的印象。羅素也有同樣的經歷並在晚年說過：「渴望確定性就像大多數人需要宗教信仰一樣的重要。」事實上，兩千多年來，歐幾里德幾何學代表了認識追求確定性的不可抗拒的尊嚴。畢達哥拉斯說「數是萬物的本原」，數是完美和諧的，因而由數所組成的世界也是完美和諧的；柏拉圖相信上帝就是用幾何學來創造世界，因而研究世界就不能不懂幾何學；伽利略乾脆就說，宇宙這本書就是用數學語言寫成的，認為如果沒有數學語言，人們只能在黑暗的迷宮中徒勞地徘徊；牛頓就是這種數學主義的堅決執行者。自牛頓以來，這種觀點幾乎變成一種教條，為知識確定性辯護的哲學知識論，總是把不確定性排除在知識之外。

但是數學理論自身是確定的嗎？由數學定律建立起來的科學理論是對世界的客觀描述嗎？或者它還是像康德所說的，思維可能把歐幾里德式的東西強加給外部世界，甚至於人類的「思維法則」就是按照歐幾里德的模式構作的。非歐幾何和相對論的出現使這一問題顯得突出，數學中的基礎主義各派的爭論使問題更加尖銳化。

哥德爾不完全定理說明，不確定性是人類認識的形式邏輯思維本身固有的，即使在純粹數學裡我們也無法徹底達到確定性。進一步，如果把這些數學的概念和理論與人們的實際經驗和科學觀察接觸，就會產生更大的不確定性。原因在於在純粹的邏輯觀念與現實之間並不是一一對應關係。哥德爾在與王浩的談話中說，「由於涉及『概念』、『命題』和『證明』等一般概念在它們最一般的意義上的不可解內涵悖論的存在，不存在使用這些概念的自指性的論證在邏輯發展的現階段能被看成是具有確定性的」。「關於『證明』這個一般概念的境況是與『概念』這個一般概念的境況相類似的，這是由於我們不能消除圍繞著這些概念的那些矛盾。否則，一旦我們理解了證明這個一般概念，我們也就憑藉心智有一個關於它自身一致性的證明。假定容易些，我們也就能夠真正從證明的這個一般概念導出矛盾，包括證明的自我應用。我們對證明概念的理解是不完全的，……某些事情與我們的邏輯觀念是不符合的，這一點是極端明顯的。」[9]因而，在任何認識中絕對的確定性是沒有的。

愛因斯坦說：「就涉及現實的一些數學命題而言，它們是不確定的……；就它們是確定的來說，它們卻又不涉及到現實。」[10]黑洞理論學家S.霍金認為，上帝不僅擲色子，而且有時還把它們扔到看不見它們的地方去。數學中，非歐幾何導致了對公理性的研究，其結果使人震驚。在許多數學分支里發現公理具有一種任意性，而且由它導出的證明往往是有缺陷的。更糟糕的是，數學家們試圖按順序整理自己的理論並沒有產生如此做法的、普遍贊成的程序。今天，我們有許多數學「學派」，例如構造主義學派、邏輯主義學派、形式主義學派和直覺主義學派，它們在基本原則上往往存在激烈的爭執。

王浩認為，哥德爾定理使那些進行數學形式化努力的人，「從此深深感到了形式處理與直覺處理相互制約的中心意義，儘管這個部門是研究形式側面的。」[11]哥德爾定理還以不同方式施加影響於數學哲學的三大學派：形式主義、邏輯主義和直覺主義。王浩指出，它「毀掉了形式主義者找出完全形式系統及有窮主義一致性證明的期望，也毀掉了邏輯主義者找出一套清澈而廣博的『大邏輯』形式系統的期望。這些定理對直覺主義者來說不那麼令人吃驚，但它們和它們的證明是構造性的。所以是直覺主義者能接受的；此外，這項工作向他們證明適當運用形式方法會產生用他們的眼光看不全也看不準的大型準確結論。」[12]

王浩說：「哥德爾直言不諱地說過，我們沒有任何絕對確定的知識。言外之意，哪怕極其簡單的事情，我們也無絕對把握說自己完全捕獲了堪稱終審法庭的客觀實在。他提出他所謂『基於成功的論證』作為有利於實在主義的證據。」[13]

這樣，試圖建立一個絕對可靠的數學根基的企圖必然是不能成功的，數學的基礎從根本上看來是有問題的。克萊因把這一點總結在《數學——確定性的喪失》一書中，他認為，哥德爾關於相容性的結論表明：「我們使用任何數學方法都不可能藉助於安全的邏輯原理證實相容性，已提出的各種方法概莫能外。這可能是本世紀某些人聲稱的數學的一大特徵，即其結果的絕對確定性和有效性已喪失。」[14]

數學家S.李柯克幽默地說，科學、哲學和神學現今都湊到一塊了，在某種意義上表明，它們就像一起參加葬禮的三個人那樣湊到了一塊，這個葬禮就是確定性的死亡。

當然，追求絕對確定性知識的不可能，也並不意味著我們在知識的可靠性上，一定要採取一種徹底懷疑主義的態度。確定和懷疑只構成我們對我們所獲得知識的兩種極端態度（一種是始終堅持我們能獲得具有確定性的知識並努力追求不動搖，一種是因對追求具有確定性的知識的懷疑而走向相對主義和不可知論。）。雖然懷疑主義給我們提供了更深更廣的思想空間（確定論者只是在預先假定有確定性知識的前提下，在尋求確定性知識的根基中兜圈子），但它的假設性要求（除非我們對任何事物的認識有絕對的把握，除非我們絕無犯錯誤的可能性，否則我們就不應該要求對任何事物有知識。）也是不現實的。因為，雖然我們對任何事物的認識沒有絕對的把握，我們隨時都會犯錯誤，但是我們的認識畢竟在這樣的易謬論中真的前進了。知識論的歷史，是哲學家不懈追求知識的絕對確定性而逐步顯現知識的不確定性的歷史。知識論的歷史說明，沒有那種不容置疑的絕對確定性知識，知識也不是非要有這種不容置疑的絕對確定性不可。如果我們把認識看作我們對客體世界的反映，那麼，客體世界經過主體上升為理論知識的過程，是主體在理想性目標指導下，人為建構合理性的過程，其間存在著非理性的、不合理和不合法的因素。在過去，認識總是在思維中捨棄對象世界和自身的不確定性的因素，通過思維中的確定性來建構對象世界的確定性從而達到對對象世界的確定性認識。現在，原有簡單的是與非的線性思維方式，已不能滿足我們深化認識的需要，我們不得不面對對象世界和主觀思維中的、不可人為排除的不確定性，它構成我們知識論甚至是我們新的認識方式和思維方式的核心。絕對確定性知識的不可能與知識不確定性的凸現，不是知識論的「死亡」，而是知識論的「新生」。在這樣的知識論中，我們真正觸及到對象世界和我們思想思維的深處。

參考文獻：

[1]Robert Audi.Epistemology:A contemporary introduction to the theory of knowledge[M].Routledge,London,1998.214.J.丹西當代認識論導論[M].中國人民大學出版社，1990.25.

[2]波特·羅斯諾.後現代主義與社會科學[M].上海譯文出版社，1998.161.

[3][5][6][7]羅傑·彭羅斯.皇帝新腦——有關電腦、人腦及物理定律[M].湖南科學技術出版社，1995.72,128,129,129.

[4]波蘭尼.個人知識[M].貴州人民出版社，2000.396.

[8][9]轉引自劉曉力.哥德爾對心—腦—計算機問題的解[J].自然辯證法研究，1999(1).

[10]轉引自J利特爾.數學的不確定性[J].New Scientist,4,Dec.,1980.

[11][12]][13]王浩.哥德爾[M].上海譯文出版社，1997.390,391,402.

[14]M克萊因.數學：確定性的喪失[M].湖南科學技術出版社，1997.269.