2008年10月6日 星期一

計算機科學之父:艾倫.麥席森.圖靈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. 中文譯本由新新聞文化公司出版,書名是《劍橋五重奏》。



沒有留言:

張貼留言