計算機科學之父:艾倫.麥席森.圖靈Alan Mathison Turing.

謎樣的計算機科學之父

從二十世紀後半開始，電子計算機對人類文明產生驚天動地的變革，一個「資訊時代」的文明階段已經正式展開。把作為計算機理論創始者的涂林稱為「計算機科學之父」，應該是恰當的。我認為艾倫‧麥昔森‧圖靈（Alan Mathison Turing）是二十世紀對人類文明最有影響的科學家之一，不過我也要聲明，這樣的評價也許還沒有得到普遍的認同。但是我確信隨著時代的推進，涂林在科學史上的地位會日漸崇隆。   在電子計算機還沒有製造出來的時候，圖靈把計算機的原理與能力極限，都已經界定分析清楚。他的思想深深影響了計算機科學的發展軌跡，也成為人工智能研究的動力。從二十世紀後半開始，電子計算機對人類文明產生驚天動地的變革，一個「資訊時代」的文明新階段已經正式展開，雖然前景充滿了難以預料的因素，但是人類有信心期待一個樂觀的未來。把作為計算機理論創始者的圖靈稱為「計算機科學之父」，應該算是恰當的。 蒼白少年 圖靈在一九一二年六月二十三日誕生於倫敦，他的父親當時在英屬印度任公務員，而母親也出身於居住在印度的英國中上層家庭。因此涂林在十四歲他父親從印度退休返鄉前，就一直和哥哥寄養在一些英國本土家庭。成長在這種比較缺乏親情的環境裡，對圖靈的性格造成某些負面的影響。他有輕微的口吃，又難和別人打成一片，而且凡事自己料理，機乎有些離群索居的傾向。 涂林在學校裡的表現平平，他只喜歡課外做一些簡單的化學實驗。後來勉強擠進一所培養社會中堅份子的所謂「公學校」(Public School)，在十六歲時認識了學長克里斯多福‧牟康 (Christopher Morcom)。他深受牟康的吸引，也刺激他發展溝通與競爭的技能。但是在一九三○年二月牟康突然不幸過世，涂林非常受打擊，有三年時間他寫信給牟康的母親，說他常常思考人的心靈，特別像牟康的心靈，如何能嵌入肉身？死後是不是能從物質中脫離開來？ 一九三一年涂林進入劍橋大學國王學院就讀，次年他學習了馮諾曼 (J. von Neumann) 研究量子力學邏輯基礎的新著，使他逐漸學會嚴格思維的求知方式。然而也就是在國王學院的環境裡，他的同性戀傾向日漸明顯，這對他日後的人生造成重大的影響。 判定可算 一九三三年涂林自習羅素 (B. Russell) 與懷特海 (A.N. Whitehead) 的鉅作《數學原理》(Principia Mathematica)，開始進軍數理邏輯的領域。羅素與懷特海準備為數學的真理尋求一個嚴謹的基礎，而邏輯正是他們想用來達成目標的利器。雖然他們作出開創性的貢獻，但是邏輯的形式體系如何承載數學的真理，並沒有得到滿意的解決。出乎當時許多專家的預料，一九三一年剛出道的哥德爾 (K.Gödel) 徹底粉碎了羅素等人的美夢。他著名的「不完備定理」證明在任何無矛盾的形式數論系統裡，一定找得到真命題，它自已以及它的否定命題，都無法依據系統裡的推理法則，得到形式的證明。簡單來說，就是任何無矛盾的邏輯系統，從本質上沒有能力捕捉人類所能理解的全部數學真理。 一九三五年涂林由劍橋拓樸學家紐曼 (M.H.A. Newman) 的講課中知道，雖然有哥德爾的出人意表結果，但是希爾伯特 (D. Hilbert) 所提的另一個相關問題卻仍然沒有解決。所謂「判定性 (decidability) 問題」（德文原名是 Entscheidungsproblem）是要問有沒有明確的方法，至少在原則上能判定任何給定的命題，可否在初階邏輯系統裡得到證明。 要回答這個問題，必須先清楚而具說服性地界定什麼是「明確的方法」。捨棄圖靈一般邏輯學家用各種推理系統規範方法的思路，採用了一種截然不同的途徑，最終得以用否定的答案解決「判定性問題」。他在一九三六年四月告訴紐曼自己的結果，但得知美國著名邏輯學家丘池 (A. Church) 已經宣布解決了「判定性問題」，涂林不幸喪失了發現的優先權。涂林把他得到的結果寫成〈論可計算數及其在判定性問題上之應用〉("On Computable Numbers, with an Application to the Entscheidungsproblem", 以下簡稱〈可計算數〉）一文，在該年五月送交《符號邏輯學報》(Journal of Symnbolic Logic)，而在十一月號（其實是次年一月）正式刊登發表。 涂林雖然沒有得到第一名，但〈可計算數〉是一篇畫時代的巨著，其內容的深刻以及對後世的影響，都超越與覆蓋了丘池的成果。涂林在這篇論文中至少有三項極重要的創見： (一)發明與定義一種抽象的計算機； (二)證明萬用計算機 (universal machine) 的存在性； (三)證明存在有任何計算機都不能解決的問題。 涂林機器 涂林面對的首要問題是，有哪些可能的程序可用來計算一個數？他採取的途徑是： (一)仔細分析我們的直觀，從而定義出合適的計算機； (二)證明別人嘗試過的方法和他的方法等價，但是他的方法更接近直觀； (三)給出大量各式各樣的數，證明它們在新的意義下是可以計算的。 在分析直觀方面，涂林解析一位計算者的狀態，（他稱為 computer 那時電子計算機尚未問世。）從中抽離出最本質的要素，然後模擬定義一個理論的計算機。這個機器能變換的狀態是有限的，因為涂林認為計算者的心靈不應該有無窮多狀態，否則有些狀態會任意接近，以致無法區分其間的差異。機器具備一條要多長就有多長的紙帶，紙帶畫分成一個個小方格。另外有有限個符號，用以寫在小方格上來記錄計算過程。機器在每一刻的動作，取決於當時機器的狀態與所掃瞄的小方格上的符號。機器的基本動作包括： (一) 在小方格上寫一個符號，如果原來已經有符號，就把那個符號遮掉； (二) 擦掉原來寫在小方格上的符號； (三) 把紙帶向左或向右移動一格。 涂林定義理論計算機的方法有相當大的彈性，如果採取一些變化並不會影響可以計算的範圍，因此現在把這一類的理論計算機都稱為涂林機器（Turing machine，下文簡稱涂林機，圖二）。乍看起來令人懷疑這麼簡單的計算工具能算多少東西？當然從如此原始的基礎出發，要想計算日常使用的數學物件，必然會經過冗長的步驟。但涂林的重點不在要花多少精力，而在可不可能做到。最終涂林以極具說服力的論證讓人相信，所有可計算的數都能用涂林機計算。 圖二：涂林機器 (Turing machine)。 在瞭解其計算機功能的過程中，涂林體會到定義一個計算機的方法也是機械性的，因此可以用符號記錄下來。如此便能定義一個所謂的萬用計算機，它可以模擬任何其他涂林機的計算過程。萬用計算機把想模擬的涂林機的定義符號當作輸入吃進來，然後在想要計算的輸入值上，一方面解讀被模擬機器的指令，一方面依樣畫葫蘆執行，最後得出同樣的結果。萬用涂林機賦予當代內儲程式 (stored program) 電子計算機的理論基礎，使得人類在機械發明史上，首次有可能利用軟體的變化，大量擴充硬體的使用效率。 當我們深刻體認出涂林機的威力時，我們會產生一個跟剛開始時態度相反的問題：還有什麼是涂林機不可能計算的呢？當我們啟動涂林機開始計算某個輸入值時，最怕的是它一直運作不停，老是給不出答案而抵達停機的最終狀態。涂林機的定義方法，並不保證每次計算都會在有限時間內完成。於是我們很自然便想知道，有沒有可能造一個特殊的涂林機，來判斷任何涂林機一旦在任何輸入值上開動，是否計算最後會停止。這就是所謂的「停機問題」 (halting problem)。因為所有的涂林機可以有效地、機械化地逐一列隊，涂林便得以使用對角線論證法 (diagonal argument) 證明不可能存在這種特殊的涂林機，也就是說「停機問題」是無解的，再從這裡就可以繼續推論出「判定性問題」也是無解的。 涂林機的正面應用絕不侷限在可計算數的範圍，事實上，通過各種編碼的程序，可以想像的任何機械化演算過程，似乎原則上都可以在涂林機上執行。因此有人主張一切可計算的均是涂林機可計算的，這也就是一般所謂的「丘池－涂林論點」(Church-Turing Thesis)。不過隨著人類對高速及大量計算的經驗累積，這個論點也有重新檢討的需求了。 涂林機的定義，從「認識」的心理圖像上來說，最接近直觀的機械性運算特性。經過後人的繼續開拓，引入計算複雜度的考量，終於發現計算機理論內最核心也最困難的「P=NP?」問題。因此涂林的貢獻超越其他的邏輯學家，成為計算機科學的始祖。 破解密碼 一九三六年九月涂林渡海到美國普林斯敦大學讀研究所，他在十二月時公開演講他的計算理論，但是幾乎沒什麼人來聽講。 當〈可計算數〉刊出時，也沒有引起大家的重視，只有兩個人向他索取抽印本。到一九三八年六月涂林在丘池指導下獲得了博士學位。因為涂林懷念劍橋大學的環境，他辭謝了馮諾曼邀請他擔任助理的機會，也拒絕了他父親的建議，要他留在美國迴避希特勒渡海攻擊英倫的危險，他毅然決然地返回國王學院。涂林除了從理論上研究計算機外，他也喜歡動手操作機具。他在普林斯頓時，就曾嘗試製作用續電器乘二進位數字的密碼機。回到英國後，涂林更秘密參加了政府破解密碼部門的工作。 一九三九年九月三日英國正式對納粹德國宣戰，破解德國軍事密碼的任務愈發重要與迫切。特別是德國潛艦在大西洋上橫行，而德國海軍使用代號「謎語」(Enigma) 的密碼系統號稱不可破解，造成盟軍非常大的威脅。最終涂林因為他在計算理論的經驗，以及統計方法的巧妙運用，成功地破解了「謎語」系統。德國人在不知情的狀況下，軍事通訊徹底曝光，很快失去了大西洋的制海權。因為快速破解密碼的需求，英國情報部門加強研製電子的計算機具。涂林不僅開始學習電子方面的技術，並且暗地裡計畫製造一台電子的萬用涂林機，也就是真正的現在所謂的電子計算機。 二次世界大戰後，美國方面由於馮諾曼的積極推動，開始電子計算機的研製。英國受到這種發展的刺激。也在一九四六年以涂林的設計為基礎，成立了「自動計算引擎」（Automatic Computing Engine，簡稱 ACE）計畫。雖然涂林在計畫裡擔任首席科學家，也開創了一些包括程式語言設計的新想法，但是他對工程方面毫無影響力，結果 ACE 計畫完全泡湯。此時涂林當年的老師紐曼在曼徹斯特大學建立基地，並且從皇家學會謀得一筆鉅款製造計算機。紐曼請了一位雷達工程師威廉斯 (F.C. Williams)，幫他實現涂林式的內儲程式計算機，而在一九四八年六月成功地讓涂林的構想變成實物。 人工智能 涂林擔任計算機實驗室的副主任，但是涂林沒有實權。因為當時英國政府急於發展計算機，用在製造原子彈的任務上，所以威廉斯趁勢打造自己的王國，把紐曼原來的方案涼在一邊。而涂林大才小用，只能做些雜七雜八的事。不過在這一片混亂中，涂林於一九五○年發表了一篇思慮清晰的哲學論文：〈計算機械與智能〉 (Computing Machinery and Intelligence)，是人工智能研究上，一篇具歷史性的文獻。 涂林討論的問題是如何研判機器會不會思想，他採取的方法不是思辯性的分析，而是建議一種可操作的評判標準。他提出所謂的模仿遊戲 (Imitation Game) 來研判計算機的思考水準，這個遊戲的布局如下：在一個房間裡安置一台計算機和一位助理，在另一個房間裡有一位詢問者。詢問者分別與計算機及助理以通訊管道連接起來，並且利用鍵盤敲擊出螢光幕上的文字交談。 詢問者事先並不知道哪一個通話的對象是計算機，他用各種各樣的問題查探二者的真實，遊戲終結時詢問者要決定哪一個是計算機。在遊戲過程中，計算機盡量要讓詢問者猜不出自己的真實身份，而助理的作用在協助詢問者做出正確的判斷。現在一般稱呼這種類型的遊戲為涂林測驗 (Turing test)，如果計算機能以高成功率瞞騙過詢問者，我們就可以說計算機已有人腦思維的功能。 涂林自己很樂觀地認為在二十世紀末，計算機的功能已經強大到多數人不能否認它有思考能力。但是目前電子計算機的功能，雖然已經發揮到連涂林也不見得想像得出的地步，然而定期在世界各地舉行的涂林測驗比賽，至今仍然無法讓計算機展現接近人的思考能力。不過涂林的想法與信心不僅刺激了人工智能的研究，也使心理學產生變革，更間接催生了當代的認知科學。人腦到底是不是電腦，也成為研究人類心靈與意識上爭論不休的問題。 天妒英才 涂林在曼徹斯特安居下來，他開始對生物成長時形態的變化感覺興趣。他認為化學反應與擴散的非線性方程式，會導致對稱的起始形態，逐漸成長出不對稱的複雜面貌。他似乎也是最先把電腦引入數學研究的人，他使用電腦的數值模擬，觀察他所假設的化學反應。一九五一年他因為涂林機的貢獻當選皇家學會院士，他同時發表了另一項高度原創性的論文〈形態發生的化學基礎〉(The Chemical Basis of Morphogenesis)。這又是一篇超前時代太多的傑作，雖然當時並未引起什麼注意，但是現在看來，它卻是當今炙手可熱的非線性動力學的開山工作之一。 一九五二年三月涂林因為他的男伴偷了東西潛逃，報警後反而被警方送上法庭審判，因為那個年代同性戀在英國還算是犯罪的。涂林不願做任何辯護，也不認為自己的行為有錯。他面對法庭給他的兩種選擇，坐牢或是接受賀爾蒙矯正時，他寧願挑後者。但是這種粗暴的處理方法，不僅使涂林戲說自己快長出了乳房，其實更嚴重的是已經攪亂了他的心靈。 涂林本來還繼續秘密地幫英國情報機構工作，但是冷戰時期的嚴峻環境，使得同性戀者無法通過安全檢查，涂林也因而被判出局。他那種不太符合一般社會規矩的行為模式，更是讓安全單位放心不下。一九五四年六月八日，去他家裡打掃的清潔工發現涂林已經長眠不醒，他的床邊還留有咬了一半的蘋果。雖然驗屍結果說是服氰化物自殺，他母親堅信涂林又在搞化學實驗，不小心把殘留手上的藥物沾在蘋果上吃進了肚子，現在更有人懷疑涂林說不定是冷戰時期保密防諜的犧牲品。 涂林一生的際遇並未與他的貢獻成正比，哥德爾比他更孤僻，但是生前就獲得顯赫的名聲，也不像他英年早逝。除了有皇家學會院士的頭銜外，涂林沒有在學術的權力核心逗留過，更沒有交往多少學術權貴。雖然在邏輯與計算機科學的領域裡，他死後較快獲得肯定，美國計算機協會 (Association for Computing Machinery) 從一九六六年起設立涂林獎，做為對計算科學有貢獻人士的最高獎項。但是直到一九八三年另一位同性戀的牛津數學家安德魯．哈吉斯 (Andrew Hodges)，替他寫了一本膾炙人口的傳記《謎樣的涂林》(Alan Turing: The Enigma)，英美大眾才對他有較全貌的認識。以這本書為藍圖的舞台劇「破解密碼」(Breaking the Code)，於一九八六至八八年在英美兩地上演，也相當轟動，深受人們喜愛。此外，英國 BBC 更於一九九六年把它拍成電影。 一九九八年六月二十二日，英國下議院通過修改法條，使得十六歲以上同性或異性間的自願性行為均屬合法。第二天，涂林誕生的房子正式被指定為英國的歷史遺產，哈吉斯在揭開紀念碑儀式的獻詞裡，替涂林的人生作了一句最好的結語：「法律會殺人，但是精神賦予生命。」 (the law kills but the spirit gives life.) 資料資料 1. 涂林傳記裡最權威的當然屬哈吉斯的作品，最新版本如下（2000年預計還會出美國新版）：Andrew Hodges (1992), 《Alan Turing: The Enigma》, Vintage. 2. 最近哈吉斯對涂林工作的哲學面又出了一本小冊子：Andrew Hodges (1999), 《Alan Turing: A Natural Philosopher》, Routledge. 3. 哈吉斯也建立一個涂林專屬網站：www.turing.org.uk，內容非常豐富，絕對值得優先推薦。 4. 〈計算機械與智能〉這篇著名論文現在也可在網路上閱讀：www.abelard.org/turpap/turpap.htm。 5. 有關涂林機的介紹可參閱：John E. Hopcroft, Turing Machines, 《Scientific American》, May 1984, pp.70-80. 6. 有關「丘池－涂林論點」的檢討，請參閱網路上《史丹佛哲學百科全書》的條目：www.plato.stanford.edu/entries/church-turing。 7. 以涂林為主要角色的一本科學小說頗值得一讀：John L. Casti (1998), 《The Cambridge Quintet: A Work of Scientific Speculation》, Perseus Press. 中文譯本由新新聞文化公司出版，書名是《劍橋五重奏》。