藍色情懷

心、哥德爾與複雜度

心

我們所討論的「心」是「理知的心」，是因大腦活動而產生的現象，特別是腦的思維、推理、想像、知覺、記憶、學習、意向等相關功能。

中國古代雖然對人體解剖有相當深入的觀察，但是卻把這些高等的智能活動主要歸功於心臟。以現存最早而理論比較完整的醫書《黃帝內經》來說，〈靈樞‧邪客〉有謂：「心者，五藏六府之大主也，精神之所舍也。」又例如《孟子》〈告子〉說：「心之官則思」；《荀子》〈解蔽篇〉說：「心者形之君也，而神明之主也，出令而無所受令。」

晚到清朝王清任（1768∼1831年）的名著《醫林改錯》（註一）還需批判這種混淆。他在〈醫林改錯臟腑記敘〉中說：「其論心為君主之官，神明出焉，意藏於心，意是心之機，意之所專曰志，志之動變曰思，以思謀遠曰慮，用慮處物曰智，五者皆藏於心。既藏於心，何得又云脾藏意智、腎主伎巧、肝主謀慮、膽主決斷。據所論，處處皆有靈機，究竟未說明生靈機者何物，藏靈機者何所，若用靈機，外有何神情，其論心如此含混。」

王清任在〈腦髓說〉中確切地指出「氣之出入，由心所過，心乃出入氣之道路，何能生靈機、貯記性？靈機記性在腦者，因飲食生氣血，長肌肉，精汁之清者化而為髓，由脊骨上行入腦，名曰腦髓。」他也提到「李時珍曰：腦為元神之府。金正希曰：人之記性皆在腦中。」為什麼知覺上很顯然是發生在鼻樑後的活動，中國古人偏偏要到處尋來路，真是一項歷史悠久而又令現代人費解的胡塗公案。在中國的哲學傳統裡，就是連主宰客觀知識的心也不太愛談論。「心」成了形上化的「道德的心」，同時內涵不斷擴大，終致很難搞得清「心」到底是什麼了。

我們所謂的「心」，英文中最恰當的翻譯是「mind」。這種理知之心作為指導物理世界的形上原則，在西方思想史上最早提出的人是安那薩哥拉斯（Anaxagoras,499∼428B.C.）。他認為心是所有東西中最細最純的，心控制有生之物，也是宇宙能動的起源（註二）。西元前五世紀號稱希臘醫學之父的阿克彌翁（AlCmaeon），已經辨識出腦是感官中樞（註三）。柏拉圖（Plato, 427∼347B.C.）在他的對話錄《泰彌阿斯》（Timaeus）中，也把靈魂的理性部分，擺進了頭顱裡（註四）。有趣的是亞里斯多德（Aristotle, 384∼322B.C.）卻以為腦的作用是在替血液散熱，而心臟才是感官的中心（註五）。不過古代西方世界的醫學，最受希臘人蓋倫（C. Galen, 129∼199年）的影響，他倒是認為理知所在之處是腦（註六）。1575年，西班牙醫生德聖璜（J. H. de San Juan）出版了現代第一本腦功能的科學著作，開始在生理學與心理學間建立起橋樑（註七）。

理知的心與肉體的身是如何存在、如何互動，從希臘時代之後，就日漸成為西方哲學史上的一個核心問題。而當現代科學伴隨著文藝復興的腳步在歐洲傳播與茁壯後，機械觀的眼光便成為透視各種事物奧祕的不二法門。

現代哲學之父笛卡兒（R. Descartes, 15961650年）嘗試把有機世界加以機械化，就是連人的肉體也看作是一套精緻的機器。心臟比喻為茶壺，從血管來的血經過茶壺燒開，再像蒸汽一樣壓回血管（註八）。而他把腦設計成巧妙的水力機，管子裡流動著極細緻的屬於精神的液體。這種液體在腦及神經各部位的質與量，決定了種種的心理狀況與感覺，例如痛楚、癢、反射動作、友善、勤勉、自信、勇敢、甚至心情安寧。他說：「活人的身體狀況，如同鍾錶或其他自動機上好了發條，並且補實了原來設計它能動的物質條件；而死人的身體就像摔壞的鍾錶，或者缺乏動因的自動機。」（註九）

在這種觀點下，一般的動物只不過是會動的物質、精密的自動機罷了。笛卡兒認為倘若自動機「內部機關與外貌都雷同一隻沒有理性的猴子或其他禽獸，人就不可能有辦法區分它與那些動物在本質上的差別」。（註十）人之異於禽獸、異於自動機，並不在於人有精神的變化，而是在人有理性、有思想、有語言，也就是有理知的心。

笛卡兒最著名的話「我思故我在」（cogito, ergo sum），比較貼切的意義是「心在而後思想在」。他說：「當我考量我自己的心，也就是一個會思想的我時，我沒有辦法在我自己中區別出部分來，必然只能以一個整體來感知到自己。⋯⋯意願、感受、理解等功能不能說是心的部分，因為是那個惟一且同一的心在意願、在感受、在理解。但是肉體的或有廣延的東西就相當不同了，我想不出一件這類東西我的心無法把它分成部分。因為心是無法再劃分的，即此一樁也足可讓我知道，人的心或說靈魂是迥異於肉體的。」（註十一）笛卡兒更說：「我們的靈魂因其本質特異而獨立於肉體之外，所以也無由隨形體俱殞。」（註十二）

笛卡兒這樣嚴格的在身心之間劃界，開了西方哲學二元論的先河，但是也即刻遭遇二元論的困難，身心又如何來互動呢？笛卡兒的天真答案是說身心經過腦下的松果體交會。蓋倫曾經認為松果體是控制思想流動的管道與活門，笛卡兒以為除了人其他動物並沒有松果體，因此松果體是區分有心與無心的表徵。如果笛卡兒能像現代人一樣，知道有一類非常原始的爬蟲，牠的松果體都比人發達的話，又不知會作何感想了？（註十三）

笛卡兒的二元論其實是一樁拓展科學王國疆域的策略，一旦心靈與物質劃分開來，整個物質世界便成為一個機械的系統，用以探索它的學問就是物理學，而物理學的原理終將化約到幾何學或其他抽象的數學。不管是終極的理由也好、巫道的活靈也好，都屬於神學概念的天下，全與物理科學發生不了關係。用以解釋無生物的原理原則，也同樣可用以解釋除人心之外的有生世界。在這樣一種機械世界觀強勢瀰漫的時代裡，笛卡兒的心實在也很難倖免於成為機械鍾的命運。機械論哲學的死硬派霍布斯（T. Hobbes,1588∼1679年）想把心的運作都化歸到加法與減法，因此當他得知帕斯卡（B. Pascal,1623∼1662年）發明了加法計算器後，更以為證實了他自己的哲學。霍布斯在《巨靈》（Leviathan）書中說：「不論何處只要有加減就有推理，倘若是沒有加減的地方，推理也無由存在，因為推理就是算計（就是後果的加減）。⋯⋯當人推理時，他所考慮的無非是把各部分加起的總和。（註十四）這種簡單的化約論（reductionism）想法在德拉麥特利（J. O. de la Mettrie,1709∼1751年）處達到高峰，他的名著《人是機器》（L'homme machine）的題目已充分表明了他的立場。他也認為只要零件組織足夠複雜，就有可能造出會說話的機器。在德拉麥特利的機械世界裡，人的心理過程正如同他的物理過程一樣，都可以用機械的、唯物的理由找到說明（註十五）。

圖靈算機

不論心到底是不是機器，替心的運作尋找機械的說明，確實有它正面的意義與價值。凡是這種說明可以奏效的地方，都使人對心的功能產生較明確的認識與掌握。霍布斯要把推理化約到加法與減法雖然是想得太簡單，但是當多數人算複雜加法還頗費心思的時代，帕斯卡的計算器豈不是把心的一種功能解密了？

現代人當然知道再怎麼精巧組合槓桿與齒輪，轉動起來也比心的機制粗糙得多。在不忽視物質構造因素的前提下，應該先在功能的層次上尋求心的機械說明，只有當這種理解非常深入後，才適合去挑選恰當的物質把它具體實現出來。要達到鍾錶報時的功能，用黃銅鋼鐵固然很好，用木頭細索亦未嘗不可，這是人早就充分明瞭的。但是只有從二十世紀三十年代以降，人才真正認識出功能層次描述的重要性、可能性與廣泛性。

時至今日，電腦軟、硬體於數十年間快速演化的歷史經驗，更讓人清晰地了悟到，計算的可能性是在功能層面已經完全決定好了。1936年圖靈（A. M. Turing, 1912∼1954年，註十六）發表了抽象計算機模式的論文，從此人對心的研究因擁有新而有力的工具，便進入一個截然不同的局面。

圖靈仔細分析了人作計算時，最基本最不可少的要素有那些，就發現很多平日用來計算的方式與行為，只是使過程與步驟比較方便，其實都可以用更簡單樸素的辦法達成。當一切都簡化到不能再簡單的階段，就會察覺人在計算時所需的，只是一條要多長就有多長的橫向紙帶，上面打好一條條直線，區劃成水平方向的一個個方格子。計算開始時方格子裡都寫好了0（代表空格子）或1，但是寫1的方格子只能有有限多個。計算者從某個起首的方格開始，所需要執行的步驟不出下列幾樁事：

依據現在注視的方格里是1還是0，決定下一步驟作什麼

如果把以上的動作交給一個機器去作，人人都應該會同意是在機器能力範圍內的事。而且我們可以用一套種簡單的程式語言來設定機器如何操作，這套語言的基本指令只有七種：

利用這七種指令寫一個有限長度的程式，就定義好了一個圖靈算機（Turing machine，註十七），也就是說我們是用軟體而非硬體來決定一個抽象的計算機。如果回到人作計算的情況來看，則程式中每一條指令相當於計算者一個心的狀態。為什麼只能允許有限個不同的狀態呢？圖靈回答說：「假如我們允許無限多個心的狀態，則它們中間有些會『任意的接近』以致混淆不清。」（註十八）現在舉一個簡單圖靈算機的例子如下：

若計算開始時紙帶上有連續n個1，而且機器看著最左邊的那個1，我們順序執行完各步驟，當機器進入第10步停止後，紙帶上正好留下連續2n個1，所以這個圖靈算機是一個用來加倍的機器。下面我們把計算n＝2的全部過程表列出來，符號↑指出機器正在注視的方格。

因為自然數可以只用0和1兩個符號的二進制來表示，所以圖靈算機正好拿來計算自然數上的函數。圖靈算機的程式雖然長度有限，但當輸入值給定並且機器運算開始後，是不是在有限時間中算得出結果，卻要看情況而定了。有時候終究無法在有限步驟裡停下來，輸出最後的答案。例如下三行程式：

這部機器只有向右移到看見一個1時，才會停下來。因此如果一開始紙帶上的1都在關照的方格的左邊，機器就永遠也停不下來了。所以圖靈算機計算的函數，自然應包括在某些值上有可能沒有定義的函數。

我們先從最基本的加法函數、乘法函數開始，再逐漸累積組合成愈來愈複雜的函數。而當有關自然數間的關係用它們的代表函數表示以後，圖靈算機也可用來判定許許多多這類關係是否成立。不要看圖靈算機這麼簡單，凡是人能想出是靠機械方式算出的函數，無不可以在圖靈算機上算出來，當然通常會需要很多的步驟。因此圖靈第一項重要的貢獻，便是讓人充分體認出如此簡樸的東西，卻能有極其廣大的潛能。又因為很多抽象的結構都可以用適當的自然數代表出來，於是圖靈算機的威力甚至涵蓋了一切能用機械方式處理的問題。著名的丘池論點（Church thesis）， 也叫做丘池-圖靈論點就是斷言：

凡是機械可算的，都是圖靈算機可算的。

從1935年丘池論點公諸於世後，迄今未曾發現任何反面的證據，因此它已成為普遍接受的學理。也就是這種強而有力的普遍性，使得人很自然地想用圖靈算機來刻劃心的功能。

圖靈第二項驚人的發現是，我們可以造一個萬能的（universal）圖靈算機。首先我們要把七種指令加以編碼：

其次要把一套程式編碼，我們先寫一個1，再相繼把各個指令以它們的數碼串連起來，最後寫上111作為終結的記號。例如前面用來加倍的圖靈算機，它的數碼便是：

這種數碼可以當作是一個以二進製表示的自然數。它的特性是我們能唯一又直接從一組數碼研判出它是不是圖靈算機的數碼，並且當答案為肯定時，讀出它的指令來。這個過程是完全機械化的，所以我們可以設計一個特殊的圖靈算機U，當任何一個圖靈算機M的數碼m連上一組輸入值v，當成是 U的輸入時，U的計算過程就是先解碼，然後再模擬M在v上的計算過程。因此任何能利用一個圖靈算機計算的東西，都可以用U來計算，所以說U是一個萬能算機。萬能算機的存在正是今日所有一般用途的電腦，快慢雖有差別但可計算範圍均一致的理論基礎。

假如萬能算機U的輸入是mv時（其中m是某個圖靈算機的數碼），而在有限步驟裡計算得以完成，則輸出的值稱為中ψ_m(v)，不難看出ψ_m(v)是m與v的可算函數。現在定義一個新的函數Ψ(m)：

如果U在輸入mm時會停得下來，則定

圖靈算機雖然本領廣大，但是這個函數Ψ(m)卻無法計算。為什麼呢？我們拿任何一個圖靈算機T來看，假設它的數碼是p。我們要證明T在算Ψ(m)的過程中，當碰到m＝p時一定算不出正確的值。首先T在輸入P時可能停不下來，但是根據定義的方法，Ψ(p)一定有個值，因此這個T不合於計算Ψ(p)。假設T在輸入p時會停下來，則根據萬能算機的性質，停下時的輸出值應該是ψ_p(p)。但是若根據Ψ(p)的定義，則應輸出ψ_p(p)+1。我們由此得到一個矛盾，所以沒有一個圖靈算機能處處算對Ψ(m)的值。

前面我們看過一個三行程式的圖靈算機，它是否會停的問題很容易就解決了。但萬能圖靈算機會不會停止的問題，卻不可能用任何機械方式判定。否則我們便可用那種方式來判定輸入mm到U裡，計算會不會停止，從而得到一個計算Ψ(m)的機械方法，這就與剛剛得的結論矛盾了。這個所謂停止問題（halting problem）的不可解性（unsolvability，即不可由機械來判定）的事實，是圖靈的第三項重大的創見。在電腦尚未問世之前，圖靈已經不容置疑地證明了電腦會遭遇的內在侷限。

形式系統

心的本領除了在計算方面可以用圖靈算機這種模式（model）「捕捉」住外，它執行推理的邏輯能力也是相當明確的，應該有辦法作精準的描述，而「形式系統」正是達成此項任務的最佳工具。形式系統初步可以看作是一種符號遊戲，首先要規定好那些符號串是遊戲的對象，那些符號串是遊戲開始時的出發點。然後講好如何從一串符號變化到另一串符號的規則，遊戲的目的就是要按規則儘量變化出符號串。我們現在舉一個簡單的形式系統的例子：

我們的形式系統叫做「○■□系統」（註十九），因為只用○、■、□三個符號來排出合法的符號串。○□是唯一作為起始的符號串，稱為「公設」（axiom）。有四條變化符號串的規則，稱為「推論律」（rules of inference）。凡是能用推論律從公設推出的符號串，就是我們所要的符號串，稱為「定理」（theorem）。因為公設本身不需要任何推論律已經有了，所以也算作定理之一。以下四條推論律裡的w表示任何一串合法的符號串。

因為暫時定理並不代表什麼實質的意思，所以叫做形式系統。現在我們在「○■□系統」中作一個推出定理○□■□的示範：



這樣的形式系統裡的推論遊戲豈不太簡單了，有什麼好玩呢？然而倘使我們嘗試在「○■□系統」內去推論出○■，就會發現什麼定理推得出、什麼定理推不出，實在不是一個唾手可解的簡單問題。針對一個形式系統，來判定任何給出來的合法符號串是不是定理，就叫做「判定性問題」（decidability problem）。如果這個問題可以用機械性的方式解決，也就是能交給一個圖靈算機來代勞的話，便說此一形式系統是「可判定的」（decidable），否則便說是「不可判定的」（undecidable）。

如果一個形式系統裡，所有合法符號串都是定理，就實在太沒有鑑別力，也就太無趣了。我們感興趣的是那種會有些合法符號串並不是定理的系統，也就是稱為「相容的」（consistent）形式系統。但是想從公設與推論律來研判一個系統是不是相容的，只要系統稍微複雜點，也同樣變成十分困難的問題，當然我們希望這類「相容性問題」（consistency problem）最好能有機械方式的解決辦法。以上面的「○■□系統」而言，我們確實能花一番氣力去證明如下的判定原則（註二十）：

一組用○、■、□排成的符號串，是「○■□系統」定理的充分而且必要的條件是，該符號串以○起首，後面跟著的符號串只用到■、□兩個符號，同時□出現的次數不會是3的倍數。

原則中的充要條件很容易用一個圖靈算機來檢查，譬如○■就不可能是「○■□系統」裡的定理了。由此我們便知「○■□系統」是相容的，而且它是可判定的系統。

哥德爾不完備性定理

如果形式系統的符號串不能賦與實質的解釋而產生意義，那麼這個系統就只能永遠是場遊戲，而且經常還會是挺無趣的遊戲，人又何必要研究它呢？所幸當人反省一下做邏輯或數學推理的經驗，不也是需要用很多符號，從已知的推導出未知的時候，就會想到形式系統說不定可用來模寫人心解決邏輯或數學問題的過程。平日數學研究裡所謂的「證明」，其實是一種說服的過程。從一些已經知道的事實，依照正常思維的邏輯步驟，來說服別人另外一些命題也是真的、對的。現在把這些事實所涉及的概念，以及推理時的步驟，都儘可能的用符號表示出來，如此建構起的形式系統，它的符號串就有自然的解釋，而其實質的意義便有真假區別了。對這種能賦與實質解釋的形式系統而言，當然可研究其判定性、相容性的問題。此外，因為解釋的關係，還會增加一種新類型的問題。

在形式系統裡推論出定理的過程也叫做「證明」（proof），是形式的證明。一個合法的符號串能成為定理，就說它是「可證明的」（provable）。現在「證明」一詞有了兩種意義，一種是我們直覺的、斷定真假的證明，一種是在形式系統裡去推導定理的證明。假如想用一套系統模寫人的自然思維過程，至少應該達到證明出的定理，在解釋後都為真。否則這套系統便會帶來混亂，不要也罷。凡是定理均為真的形式系統，就稱為「可靠的」（sound）系統。從另外一個方向看，凡是為真的命題，也就是能有一般直覺證明的命題，最好在形式系統中也是可證明的。滿足真命題均為可證的形式系統，就稱為「完備的」（complete）系統。數學家如果能碰到一個既可靠又完備的形式系統，必然會高興得不得了。

數學最基本的研究對象，無非是數與形。就拿0,1,2,3,……這無窮多個自然數來說，它們的性質便極其豐富，並且還有許多問題迄今仍然無法解決，甚至有懸疑上千年的難題例子。皮亞諾（G. Peano, 1858〜1932年）在1889年已建構了描述自然數的形式系統，我們現在稱為PA，PA使用的符號包括下列各類：

從式子裡面挑出一些作為涉及邏輯性質的公設，以及一些作為涉及算術性質的公設。其實公設是有無限多條，不過給出任何式子，都可以機械性的判定它是不是公設。最後再規定好證明定理的推論律，PA這個形式數論（formal number theory）系統於焉完成，它也稱為形式算術（formal arithmetic）或初等數論（elementary number theory）。PA裡涉及算術性質的公設，既然是用來模寫自然數的性質，顯然均為真。形式證明的過程當然也設計得會從真的式子推出真的式子，因此PA毫無疑問是一個可靠的系統。至於PA是不是完備的系統，卻是極端艱深困難的問題。

有關完備性的問題我們甚至可以放到較寬的系統中考慮，令S是一個包括PA的形式系統，譬如說在S中還可以形式化實數的性質等等。現在我們再回頭去檢查一些萬能圖靈算機U的停止問題，給定任何一個自然數m，「U在mm上會停」這句話其實能用普通自然數的性質給予證明。因此我們就能從自然數m經過一番機械過程，找到S中的句子C_m來表示這件事，也就是說在自然的解釋下，C_m的意思便是說「U在mm上會停」。並且因為S已經充分地模寫了自然數的性質，所以「U在mm上會停」的證明也能在S中完成形式的推導，所以我們對任何m有了下面這個條件句：

（a）若「U在mm上會停」，則「C_m是S裡的定理」。

前面我們已經說過，只有可靠的形式系統才是有用的系統，所以我們應該對所有m假設：

（b）若「C_m是S裡的定理」，則「U在mm上會停」。

現在先考慮一下S是不是一個可決定系統的問題。假設有一個機械程序能判定任一式子是不是S的定理，則給出任何自然數m，我們就能機械地判斷萬能圖靈算機U在mm上會不會停。因為我們可以先機械地找出句子C_m，再機械地判定它是不是S的定理。根據（b）與（a），可知是定理就會停，不是定理就不會停。如此便與前面證明的停止問題的不可解性矛盾了。所以我們首先知道S不是一個可決定的形式系統。

既然S應該是可靠的系統，我們也可假設下面這個條件句對所有m成立：

（c）若「﹁ C_m 是S裡的定理」，則「U在mm上不會停」。

但是反過來，

（d）若「U在pp上不會停」，則「﹁C_m是S裡的定理」。

會不會對所有的m成立呢？假使（d）會成立，我們就有辦法找到萬能圖靈算機停止問題的機械解。方法如下：

每一個形式系統裡的證明，都可以列成一個長度有限的式子序列，式子與式子之間都用逗號隔開，而且每一個式子若非公設，則是由在前面已出現過的式子，經推論律推出的。假如形式系統的符號可用有限個基本符號寫出，例如在PA中只需17個，則這些形式證明都可以用有限個基本符號寫出來。因此當長度一定時，只可能存在有限個相異的證明。又因為我們能機械地判斷一列式子有沒有構成形式證明，所以我們有辦法把S裡的證明，機械性地按長度順序排列成一個（可能無窮長的）序列。當m給定後，我們順著這個序列找C_m或﹁C_m。因為「U在mm上會停」和「U在mm上不會停」兩句話中，必有唯一的一句為真，所以根據（a）和（d）我們必定會尋找到C_m與﹁C_m二者中之一，再因（b）和（c）便知U在mm上到底停不停了。

這樣一套判定U能否停止的機械程序，便告訴我們（d）不可能對所有m成立，也就是說存在某個數p，U在pp上不會停，但﹁Cp不是S裡的定理。形式句﹁Cp 解釋後的意思是說「U在mm上不會停」，現在U在pp上真的不會停，所以﹁Cp是一個為真的句子。最後我們發現Cp也不能是S裡的定理，否則根據（b）U 在pp上就會停了。

綜合上面所說，如果在任何形式系統S中，我們有一套機械方法從任一自然數 m得到句子C_m，且滿足（a）,（b）,（c）三條，則必然存在一個句子Cp，使得Cp為真，但Cp與﹁Cp都不是S裡的定理，也就是說S不可能是一個完備的系統。可靠性與完備性成了無法兼得的魚與熊掌，這就是著名的哥德爾（K. F. Gödel,1906〜1978年，註二十一）第一不完備定理（First Incompleteness Theorem），不過我們此處採取了克林（S. C. Kleene）的改良方式來解說，而與哥德爾1931年的原始證明略有不同（註二十二）。

拉塞（J. B. Rosser, 1907〜1989年）於1936年採取較萬能算機停止問題更複雜的命題，還可以用S的簡單相容性來代替（a）,（b）,（c）三條件（註二十三）。所謂簡單相容性（simple consistency）就是說，在S裡不可能證明兩個互相矛盾的句子C與﹁C。如果C與﹁C都不是S裡的定理，則稱C是不可判定的句子（undecidable sentence）。那麼哥德爾第一不完備定理另一種表達方式就是說：任何一個有能力討論數論的形式系統，如果它是簡單相容的，就會產生一個為真但是不可判定的句子。進一步我們在S中能找出一個句子來表達S的簡單相容性，用Consis稱呼這個句子。哥德爾第二不完備定理就是說，即使S是簡單相容的， Consis也不會是S中的定理。所以人想要證明S的簡單相容性，就必須走到S之外，使用新的公設或比S裡更強的推論方法。

複雜度

在我們討論圖靈算機的過程中，似乎只對機器在輸入值上停不停感興趣，至於停下來輸出什麼結果好像無關緊要。其實不然，我們現在準備從輸出的角度來看一看。我們只考慮計算停止後，紙帶上至少有兩個1的情形。在最左與最右的兩個1之間的0與1的符號串就是輸出值，作為前後標兵的兩個1不算在輸出值內。

假如我們現在想輸出1024個1來（包括前後標兵在內），最無趣的辦法是在紙帶上寫好1024個1，什麼程式也不要。這樣我們用了1024個比特（bit，就是一個0或1的數字，用以縮寫binary digit）。如果我們使用前面第二節裡的加倍機器，在512個1上運算一番，也得到1024個1。可是那個程式的數碼用了45個比特，再加上輸入的 512個比特，一共是557比特，比1024個比特大有改善。因為1024是2的10次方，我們可以從一個1開始，把加倍機器開動10次得到所需。例如下面程式的頭9步，與前述加倍機器完全相同。如果開始的輸入是

這個方法要輸出1024個1，所需要的比特數能降到166。為什麼我們能用相對較少的比特，產出比特較大的數串呢？主要是因為大數串裡的0與1出現的相當規律，我們可以用較精簡的程式造出它來。對於一個由0與1構成的數串w，我們可以定義它的複雜度（complexity）K （w）＝n，如下：

1.存在一個圖靈算機以及某個輸入值，機器的數碼加上輸入值的長度是n，而計算的輸出值是w。

2.不會有小於n的數滿足上述情況。目前在數學、物理，計算機科學裡有好多不同的複雜度的概念，上面這種概念是1965年左右分別由柴廷（G. Chaitin）與柯莫郭洛夫（A. N. Kolmogorov, 1903〜1987年）提出，別名還包括信息理論的複雜度（information-theoretic complexity）、信息內容（informaiton content）、算則複雜度（algorithmic complexity），或柯莫郭洛夫複雜度（註二十四）。愈規則的數串其複雜度與其長度之比愈小，反之比值愈大的數串表示0與1出現的方式愈亂（random）。其實如果數串w的長度是n，則K(w)≦n+9。因為我們最壞也可用如下一個挺無聊的機器輸出w：指令只有一個「停」，起始紙帶上是1w1。因為機器碼是1100111，所以K（w）不會大於數串11001111w1的長度n＋9。從這個上限可看出，當數串相當長後，複雜度與長度之比愈接近1的數串愈亂。此外我們並不難估算出絕大多數的數串都相當亂。譬如我們來看看長度是n的數串中，有多少的複雜度不大於n−10。決定這種數串複雜度的最短程式與輸入，是長度不大於n−10的0與1數串。長度是i的數串一共是2i個，所以長度不大於n−10的數串共有2＋4＋…＋2n-10=2n-9-2個。因此長度是n的數串中，其複雜度不大於n−10的就不會多過2n-9個。這種數串與長度是n的數串總數相比，就有

也就是小於0.2％。所以在長度是n的數串中，超過99.8％的複雜度大於n−10。但是隨便便拿出一個數串，然後叫我們證明它是一個亂數串，卻不是件簡單的事。

譬如說我們現在有一套很好的形式系統，在裡面足夠證明K（w）＞n這種命題。當然我們要假定這套系統是可靠的，也就是說若在其中證得出K（w）＞n，則w的複雜度確實大過n。現在我們要設計一個新的程序。類似前面證明不完備性的思考方式，我們能機械地把系統裡的證明排成一個順序P1,P2,P3……。對於每一個Pi，先檢查它是不是一個K（w）＞n命題的證明？如果是的話，對某個事先選好的常數H而言，n＞H成不成立？如果成立的話，就輸出w；否則繼續檢查下一個證明Pi+1。這整個程序也可寫成一個圖靈算機的程式M，而常數H必須選得比M的數碼的長度還大。一旦M運轉起來，它會不會停呢？假如它會停下來輸出w，則根據系統的可靠性，w的複雜度大於H。但是算出它的程式M長度小於H，所以它的複雜度應該小於H。我們因此得到一個矛盾，所以M停不下來。

以上便是柴廷推導出的哥德爾風格的不完備定理：

對於任何可靠的形式系統，都存有一個由系統決定的常數H，只要n＞H,就沒有辦法在系統裡證明任何給定的0與1數串的複雜度大於n。這個結果讓人驚訝的理由是：如果我們的形式系統是一個極強的系統，幾乎包括了所有日常數學推理的方式（例如所謂Zermelo Fraenkel的公設化集合論），則存有某個特別的常數，使得我們永遠無法證明任何給定的數，它的複雜度大於那個常數，雖然我們明明知道絕大部分的數複雜度均極高。這似乎是說不僅形式系統的能力有侷限性，連我們直覺的數學本領也有跨不過的鴻溝。

心與機器

從二十世紀末的今天看十七、十八世紀的霍布斯與德拉麥特利，他們把心的理知功能化約到算術以及機械性運作的想法，似乎在圖靈算機上得到了基本的實現。尤其最近半個世紀間，電腦工藝的驚人發展，更使得「心等不等同於機器？」這個問題，愈加有咀嚼的材料了。所謂「人工智慧」（artificial intelligence）的研究，往往強烈暗示或導引人趨向肯定的答案。

心如果真的是一套機器，機器得先會思想。機器會不會思想呢？圖靈在1950年建議用下面這套「模仿遊戲」來檢驗機器。我們先讓一個男人A，一個女人B，一個發問題的人C來玩「模仿遊戲」。C與A,B在不同的房間內通過電腦交談，C知道有兩個人在跟他交談，但不知道誰是A、誰是 B。遊戲的目的就是由C發問題，A,B來回答，而要C判斷誰是A、誰是B。B的角色是想儘量幫C達到目標，而A可以用各種方法（包括說謊）去誘導C作錯誤的判斷。如果現在用一個電腦取代A，C的答對比率會較剛才顯著的不同嗎？以上就是有名的判斷電腦像不像人腦的「圖靈測試」（註二十五）。

圖靈自己對電腦的本領是非常有信心，他以為到二十世紀末再作這種測試，經過五分鍾的詢問後，能正確辨認出電腦的機會不會超出 70％。1991年尾，波士頓電腦博物館與劍橋行為研究中心，主辦了一次有六個程式參加的「圖靈測試」比賽，有十位評審，每次在一個限定的話題下，與一個人或一個電腦交談十四分鍾，然後評斷對方是人還是機器。得第一名的是一個電腦治療師的程式，有五位評審相信是在跟人交談。這已經是十分令人滿意的成就了，至於話題無限制的情況，連主持的單位也認為不可能在世紀尾以前圓滿達成。

也有相當多人認為心不是機器，不可能用任何圖靈算機來模擬心的功能。一種具代表性的論證方式如下：假設圖靈算機T可以模擬人（譬如是我）的心，那麼利用哥德爾的技巧，造一個特別的不可判定句子，T沒有辦法證明它，而我卻有辦法，因此T不可能完全代表我，所以我的心不是機器。這個論證其實誤用了哥德爾不完備定理，我真正能作的是，從任何給定的圖靈算機T找出句子C且證明：

（*）若T是簡單相容的，則C為真。

而如果T真的是簡單相容的，則C為不可判定的句子。其實T也有能力證明（*）這個條件句。T無法判定的句子（即使是假設了簡單相容性），我也無法證明，除非我能先證明T的簡單相容性，不幸的是只要T夠複雜，這個問題通常我也解決不了。因此很粗心的運用哥德爾不完備定理，是無法否證「心即機器」的論斷（註二十六）。

哥德爾自己比較傾向於認為心是無法以機械方式來刻劃。根據王浩的記載，哥德爾曾寫過：「圖靈在Proc. Lond. Math. Soc. 42（1936）, p.250給過一個論證，意在指明心的程序無法比機械的程序作得更多。然而這個論證並不足以得到定論，因為它倚賴一項預設，就是認為有限的心只可能承擔有限個可分辨的狀態。圖靈完全忽視了一件事實：使用中的心不是靜態的，而是不斷地在發展。……在心發展的每一個階段，雖然可能的狀態數有限，但是沒有理由說在整個發展過程中，這個數不會趨向無窮。也許會有系統的方法來加速、特定、與唯一決定這種發展，例如以機械程序為基礎來問正確的問題。不過必須承認這種程序的精確定義，有待對心的基本運作更加深刻瞭解才能完成。」（註二十七）當然哥德爾的說法也只是一種信念的宣告，並不是什麼嚴格的證明。克林在評論哥德爾這裡所冀望的新程序時，認為多半仍然是跳不出圖靈算機的範圍，否則便成為「天空中的派餅」（pie in the sky）──空想而已（註二十八）。

哥德爾是一位思想非常不輕易隨俗的人，因此他在一些深刻的基本問題上，有些看法頗令人費解，最終的對錯有待時間來證明。譬如在他與王浩的討論中，他認為圖靈的論證在加入以下兩個額外的假設就可成立：一、離開物則不可能有心；二、腦的功能基本上像個數位電腦。這兩個假設今日一般人多能接受，哥德爾雖然相信二、頗可能成立，但是他以為一、只是我們這個時代的一種偏見，將會被科學的方法所推翻。譬如說腦神經細胞的數目，並沒有多到足以承擔所有可見的心的運作（註二十九）。哥德爾這種傾向物外有心的看法，其實說服力並不充足。

值得注意的可能發展方向

「心即機器」實在不是容易清楚論斷的事，等同的兩端各自都很難界定，即使把機器侷限在圖靈算機的範疇，可是心的這邊好像仍然捉摸不住。機器的行為雖然能通過形式系統加以描述，但形式系統如果表現力量不夠強，要想形式化心的認識還力有未逮。譬如以形式的算術系統PA而言，哥德爾第一不完備定理導出的不可判定句子，似乎距離日常一般數學家討論的問題太遠。PA會不會在處理「正常的」整數問題上，足夠捕捉心的能力？1977年帕瑞斯（J. Paris）與哈林頓（L. Harrington）證明了在PA裡無法決定下面這個Ramsey理論的定理：對於所有k,r都存有n，使得集合S＝｛k＋1,k＋2,………,n｝的所有k元素子集合，無論以何種方法分成r類，都會存在一個足夠大的S的子集合B，它所有的元素都來自同一類。此處所謂的「足夠大」，是指B的元素個數大於 B裡最小元素的值（註三十）。這個定理在非形式的數學裡，是不難加以證明的，也就是說它是一個「正常的」數學定理。帕瑞斯與哈林頓的這項結果充分說明PA 能力的侷限性。

當形式系統的表達能力太強時，它與心的區分並不是一項已確認的事實。我們可以把哥德爾第一不完備定理理解成：

不會存有一個機械程序，它的輸出包含了所有算術的真命題，而不會包含任何假命題。

但是人腦自以為證明了算術的定理，但結果卻是錯的，這種事情也非罕見。因此在經驗上與機器比起來，也沒有絕對的優勢。而柴廷式的不完備定理，更暴露了人與形式系統同時面對的，相當終極性的限制。

從以上的理解過程中吸取教訓，有幾種可能發展方向似乎是應該注意的：

一、心與機器的分別很難冀望於一個裁判性的數學定理來達成。從人的知識發展歷史來看，對複雜客觀實體的瞭解，也必定會通過多個面向前進，經常不可能也不必要定於唯一的進路（approach）。用形式系統與圖靈算機模擬心的功能，完全偏重在心的語言性摹寫，以及機器的符號操作面向。事實上心會不斷學習，好像應該會因此改善自己的構形（configuration）。而機器在所謂機器人（robot）的意義下，必須不斷接受物理性的能量訊息，也給出物理的反應。有關結合學習與行動的理論模式，目前仍在積極發展中，它們會不會受不完備性定理影響？或者它們是不是有自己類型的不完備性？都有待深入的研究。另外，神經系統的運作也可用動力系統的眼光來探討，但是動力系統才漸漸揭開面貌的混沌現象，對心的認識有什麼關係，應該也是引人入勝的課題。

二、從經驗與直覺上可以體會出，心的許多運作頗有機械的取向。但是圖靈算機的輸入方式有相當的限制，能否充分捕捉住心的機械取向，也有商榷的餘地。圖靈算機的輸入建基在有限個符號的有限長度序列，因此只可能分辨可數的（countable）無窮多對象。倘若要討論不可數的無窮，譬如實數的運算，就只能處理利用遞迴方式建造的可數個的實數，許多古典數學的漂亮結果便無法在這樣小的論域裡存身。最近發展出的Blum-Shub- Smale的實數上計算理論中（註三十一），每一個實數都可以當作輸入值，因此能把古典數學的機械性部分明白抽出討論，不致在輸入的編碼一關，就把會下金蛋的雞給宰了。這個例子給我們一個啟示，即使心的機制基本上是圖靈算機式的，它所處理訊息的「表徵」（representation）可能很有發揮的餘地。因此由輸入類型決定的相對性算機模式，既可保持圖靈算機的計算普遍性，又可以因需要調整適用範圍，似乎是更恰當的選擇。這方面的研究在數學上雖然已有相當結果，但是在認知科學的應用研究上，大家好像還是太拘泥在原始的圖靈算機模式。

三、我們所討論的心是Homo sapiens種的獨有現象，但是比較初級的心理活動，特別是感官訊息的處理上，別的種系也有出色的表現。生命既然是隨演化而生、隨演化而變，在生命最高層出現的心，不可能沒有演化的說明。目前數學的理論還未能著力到這個課題，也可能現有的數學工具不足以掌握與剖析心的演化，但這必然是一個有高度挑戰性且值得開拓的領域。心的功能其最核心問題，是訊息表徵、儲存、整理、運用、製出的問題，而訊息是因物的相互關係而產生，因物的相互動作而變化（註三十二）。在這種極廣義的訊息下，心的源起將推至宇宙無生命的歷史階段，也可以說在大霹靂（the big bang）產生宇宙的開始，心與物就同時誕生。相對於處理物理世界的宇宙論（cosmology），似乎值得營造一個「心的宇宙論」。當然這些觀點已經太趨於遐思玄想，目前還沒有具體的科學內容。不過讓心理滿足美麗的形上原則，在科學史上不是沒有扮演過推動進步的角色，看這一次對心的探索上，形上的思辨能否協助我們走出迷宮。

註一：清‧王清任撰 李天德、張學文點校《醫林改錯》 人民衛生出版社 北京 1991

註二：有關安那薩哥拉斯的文獻見S.Sambursky ed., Physical Thought, from the presocratics to the quantum physicists, Pica Press,New York, pp. 52∼55, 1974.

註三：參見G. Sarton, A History of Science, Vol. 1, W. W. Norton, New York, p.215,1952.

註四：參見F. Copleston, A History of Philosophy, Vol. 1, Part 1, Image Books, Doubleday, Garden City, NY, p.234, 1962.

註五：註二引書p.537。

註六：參見S.F. Mason, A History of the Sciences, Collier Books, MaCmillan, New York, p.58, 1973.

註七：參見E. Marcorini, The History of Science and Technology, a narrative chronology, Facts On File, New York, pp.166∼167, 1975.

註八：參見R. S. Westfall, The Construction of Modern Science, mechanisms and mechanics, Cambridge University Press, Cambridge, p.38, 1977.

註九：轉引自F. Copleston, A History of Philosophy, Vol. 4, Image Books, Doubleday, Garden City, NY, 1962, p.145.

註十：見註七。

註十一：轉引自S. L. Jaki, Brain, Mind and Computers, Herder and Herder, New York, 1969,p.21.

註十二：註八引書p.146。

註十三：參見I. Asimov, Asimov's Biographical Encycolpedia of Science and Technology, Second Revised Edition, Doubleday, Garden City, NY, P. 117, 1982.

註十四：轉引自註十引書p.24。

註十五：有關德拉麥特利的思想參見，李石岑與郭大力合譯：《郎格唯物論史》上卷第四篇第二章 中華書局 上海 1941

註十六：有關圖靈的生平參見A.Hodges, Alan Turing, the enigma of intelligence, Unwin Hyman, London, 1987.

註十七：本文以解說為主，而非歷史性的研究。因此圖靈算機、哥德爾不完備定理等，均採取適合我們現在所需的改良形式，並非原始發表的狀態。圖靈算機基本上使用下文所用模式：M. Davis, What is a computation? in Mathematics Today: Twelve Informal Essays, L. A. Steen ed., Springer-Verlag, New York, pp.241∼267, 1978.

註十八：A. M. Turing, On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London Mathematical Society.42：250, 1936.

註十九：此系統出自D. R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, New York,第一章, 1979.

註二十：此原則的充分性首見於L. Swanson and R. J. McEliece, A simple decision procedure for Hofstadter's MIU-system, The Mathematical Intelligencer, 10：48∼49, 1988.

註二十一：有關哥德爾的生平及思想參見Hao Wang, Reflections on Kurt Gödel, The MIT Press, Cambridge, MA, 1987.

註二十二：克林的講法參見S. C. Kleene, Mathematical Logic, John Wiley and Sons, New York, 第五章，1967.

註二十三：J. B. Rosser, Extensions of some theorems of Gödel and Church, Journal of Symbolic Logic, 1（1936）, pp.87〜91.

註二十四：基本的參考書有G. J. Chaitin, Information, Randomness and Imcompletness, papers on algorithmic information theory, World Scientific, Singapore, 1987. 以及M. Li and P. M. B. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Addison-Wesley, Reading, MA, 1992.

註二十五：A. M.Turing, Computing machinery and intelligence, Mind, 59（1950）, pp.433〜460. 也節錄於D. R. Hofstadter and D. C. Dennett eds., The Mind's I, fantasies and reflections on self and soul, Basic Books, New York, pp.53〜67, 1981.

註二十六：對於這類論斷的批評參見H. Putnam, "Minds and machines", in H. Putnam, Mind, Language and Reality, Philosophical Papers, volume2, Cambridge University Press.

註二十七：引自Hao Wang, From Mathematics to Philosophy, Routledge & Kegan Paul, London, p.325, 1974.

註二十八：引自S. C. Kleene, "Turing's analysis of computability and major applications of it", in The Univeral Turing Machine: a Half-Century Survey, R. Herken ed., Oxford University Press, Oxford, p.51, 1988.

註二十九：註四引書p.326.

註三十：J. Paris and L. Harrington, "A mathematical incompleteness in Peano arithemetic," in Handbook of Mathematical Logic, J. Barwise ed., North-Holland, Amsterdam, pp.1133〜1142, 1977.

註三十一：L. Blum, M. Shub, and S. Smale, "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines," Bulletin of the American Mathematical Society（New Series）, 21（1989）, pp.1〜46.

註三十二：訊息的概念在很多不同的場合以不同的意味出現，為訊息尋找一個足夠廣義的理論基礎，是具挑戰性而待解的難題。下書是最近一項有意義的嘗試：K. Devlin, Logic and Information, Cambridge University Press, Cambridge, 1991.

李國偉任職於中央研究院數學所；本刊編輯委員