自我介紹
connielee

臺北市立陽明高中
資訊科技概論教師

search
calendar
« 四月 2019 »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          
近期文章
文章分類
網站連結
文章彙整
Syndicate
Credits
LifeType IE7 XHTML CSS Firefox

« | »

【轉貼】謎樣的計算機科學之父

2007-03-08 @ 08:54 in ⓣ教材研究

【摘要】從二十世紀後半開始,電子計算機對人類文明產生驚天動地的變革,一個「資訊時代」的文明新階段已經正式展開。把作為計算機理論創始者的涂林稱為「計算機科學之父」,應該算是恰當的。

我認為艾倫.麥昔森.涂林(Alan Mathison Turing)是二十世紀對人類文明最有影響的科學家之一,不過我也要聲明,這樣的評價也許還沒有得到普遍的認同。但是我確信隨著時代的推進,涂林在科學史上的地位會日漸崇隆。

在電子計算機還沒有製造出來的時候,涂林把計算機的原理與能力極限,都已經界定分析清楚。他的思想深深影響了計算機科學的發展軌跡,也成為人工智能研究的動力。從二十世紀後半開始,電子計算機對人類文明產生驚天動地的變革,一個「資訊時代」的文明新階段已經正式展開,雖然前景充滿了難以預料的因素,但是人類有信心期望一個樂觀的未來。把作為計算機理論創始者的涂林稱為「計算機科學之父」,應該算是恰當的。

蒼白少年

涂林在一九一二年六月二十三日誕生於倫敦,他的父親當時在英屬印度任公務員,而母親也出身於居住在印度的英國中上層家庭。因此涂林在十四歲他父親從印度退休返鄉前,就一直和哥哥寄養在一些英國本土家庭。成長在這種比較缺乏親情的環境裡,對涂林的性格造成某些負面的影響。他有輕微的口吃,又難和別人打成一片,而且凡事自己料理,幾乎有些離群索居的傾向。

涂林在學校裡表現平平,他只喜歡課外做一些簡單的化學實驗。後來勉強擠進一所培養社會中堅份子的所謂「公學校」(Public School),在十六歲時認識了學長克里斯多福‧牟康(Christopher Morcom)。他深受牟康的吸引,也刺激他發展溝通與競爭的技能。但是在一九三0年二月牟康突然不幸過世,涂林非常受打擊,有三年時間他寫信給牟康的母親,說他常常思考人的心靈,特別像牟康的心靈,如何能嵌入肉身?死後是不是能從物質中脫離開來?

一九三一年涂林進入劍橋大學國王學院就讀,次年他學習了馮諾曼(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 Symbolic Logic),而在十一月號(其實是次年一月)正式刊登發表。

涂林雖然沒有得到第一名,但<可計算數>是一篇畫時代的巨著,其內容的深刻以及對後世的影響,都超越與覆蓋了丘池的成果。涂林在這篇論文中至少有三項極重要的創見:(一)發明與定義一種抽象的計算機;(二)證明萬用計算機(universal machine)的存在性;(三)證明存在有任何計算機都不能解決的問題。

涂林機器

涂林面對的首要問題是,有哪些可能的程序可用來計算一個數?他採取的途徑是:(一)仔細分析我們的直觀,從而定義出合適的計算機;(二)證明別人嘗試過的方法和他的方法等價,但是他的方法更接近直觀;(三)給出大量各式各樣的數,證明它們在新的意義下是可以計算的。

在分析直觀方面,涂林解析一位計算者的狀態,(他稱為computer,那時電子計算機尚未問世。)從中抽離出最本質的要素,然後模擬定義一個理論的計算機。這個機器能變換的狀態是有限的,因為涂林認為計算老的心靈不應該有無窮多狀態,否則有些狀態會任意接近,以致無法區分其間的差異。機器具備一條要多長就有多長的紙帶,紙帶畫分成一個個小方格。另外有有限個符號,用以寫在小方格上來記錄計算過程。機器在每一刻的動作,取決於當時機器的狀態與所掃瞄的小方格上的符號。機器的基本動作包括:(一)在小方格上寫一個符號,如果原來已經有符號,就把那個符號遮掉;(二)擦掉原來寫在小方格上的符號;(三)把紙帶向左或向右移動一格。

涂林定義理論計算機的方法有相當大的彈性,如果採取一些變化並不會影響可以計算的範圍,因此現在把這一類的理論計算機都稱為涂林機器(Turing machine,下文簡稱涂林機)。乍看起來令人懷疑這麼簡單的計算工具能算多少東西?當然從如此原始的基礎出發,要想計算日常使用的數學物件,必然會經過冗長的步驟。但涂林的重點不在要花多少精力,而在可不可能做到。最終涂林以極其說服力的論證讓人相信,所有可計算的數都能用涂林機計算。

在瞭解其計算機功能的過程中,涂林體會到定義一個計算機的方法也是機械性的,因此可以用符號記錄下來。如此便能定義一個所謂的萬用計算機,它可以模擬任何其他涂林機的計算過程。萬用計算機把想模擬的涂林機的定義符號當作輸人吃進來,然後在想要計算的輸入值上,一方面解讀被模擬機器的指令,一方面依樣畫葫蘆執行,最後得出同樣的結果。萬用涂林機賦予當代內儲程式(stored program)電子計算機的理論基礎,使得人類在機械發明史上,首次有可能利用軟體的變化,大量擴充硬體的使用效率。

當我們深刻體認出涂林機的威力時,我們會產生一個跟剛開始時態度相反的問題:還有什麼是涂林機不可能計算的呢?當我們啟動涂林機開始計算某個輸入值時,最怕的是它一直運作不停,老是給不出答案而抵達停機的最終狀態。涂林機的定義方法,並不保證每次計算都會在有限時間內完成。於是我們很自然便想知道,有沒有可能造一個特殊的涂林機,來判斷任何涂林機一旦在任何輸入值上開動,是否計算最後會停止。這就是所謂的「停機問題」(halting problem)。因為所有的涂林機可以有效地、機械化地逐一列隊,涂林便得以使用對角線論證法(diagonal argument)證明不可能存在這種特殊的涂林機,也就是說「停機問題」是無解的,再從這裡就可以繼續推論出「判定性問題」也是無解的。

涂林機的正面應用絕不侷限在可計算數的範圍,事實上,通過各種編碼的程序,可以想像的任何機械化演算過程,似乎原則上都可以在涂林機上執行。因此有人主張一切可計算的均是涂林機可計算的,這也就是一般所謂的「丘池-涂林論點」(Church-Turing Thesis)。不過隨著人類對高速及大量計算的經驗累積,這個論點也有重新檢討的需求了。

涂林機的定義,從「認識」的心理圖像上來說,最接近直觀的機械性運算特性。經過後人的繼續開拓,引入計算複雜度的考量,終於發現計算機理論內最核心也最困難的「P= NP?」問題。因此涂林的貢獻超越其他的邏輯學家,成為計算機科學的始祖。

破解密碼

一九三六年九月涂林渡海到美國普林斯敦大學讀研究所,他在十二月時公開演講他的計算理論,但是幾乎沒什麼人來聽講。

當<可計算數>刊出時,也沒有引起大家的重視,只有兩個人向他索取抽印本。到一九三八年六月涂林在丘池指導下獲得了博士學位。因為涂林懷念劍橋大學的環境,他辭謝了馮諾曼邀請他擔任助理的機會,也拒絕了他父親的建議,要他留在美國迴避希特勒渡海攻擊英倫的危險,他毅然決然地返回國王學院。涂林除了從理論上研究計算機外,他也喜歡動手操作機具。他在普林斯頓時,就曾嘗試製作用續電器乘二進位數字的密碼機。回到英國後,涂林更秘密參加了政府破解密碼部門的工作。

一九三九年九月三日英國正式對納粹德國宣戰,破解德國軍事密碼的任務愈發重要與迫切。特別是德國潛艇在大西洋上橫行,而德國海軍使用代號「謎語」(Enigma)的密碼系統號稱不可破解,造成盟軍非常大的威脅。最終涂林因為他在計算理論的經驗,以及統計方法的巧妙運用,成功地破解了「謎語」系統。德國人在不知情的狀況下,軍事通訊徹底曝光,很快失去了大西洋的制海權。因為快速破解密碼的需求,英國情報部門加強研製電子的計算機具。涂林不僅開始學習電子方面的技術,並且暗地裡計畫製造一台電子的萬用涂林機,也就是真正的現在所謂的電子計算機。

二次世界大戰後,美國方面由於馮諾曼的積極推動,開始電子計算機的研製。英國受到這種發展的刺激,也在一九四六年以涂林的設計為基礎,成立了「自動計算引擎」(Automatic Computing Engine, 簡稱ACE )計畫。雖然涂林在計畫裡擔任首席科學家,也開創了一些包括程式語言設計的新想法,但是他對工程方面毫無影響力,結果ACE計畫完全泡湯。此時涂林當年的老師紐曼在曼徹斯特大學建立基地,並且從皇家學會謀得一筆鉅款製造計算機。紐曼請了一位雷達工程師威廉斯(F. C. Willaims),幫他實現涂林式的內儲程式計算機,而在一九四八年六月成功地讓涂林的構想變成實物。

人工智能

涂林擔任計算機實驗室的副主任,但是涂林沒有實權。因為當時英國政府急於發展計算機,用在製造原子彈的任務上,所以威廉斯趁勢打造自己的王國,把紐曼原來的方案涼在一邊。而涂林大才小用,只能做些雜七雜八的事。不過在這一片混亂中,涂林於一九五0年發表了一篇思慮清晰的哲學論文:(計算機械與智能)(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.)

資料來源:科學月刊
#發行日期:1999、11
#期號:0359
#專欄:世紀科學專輯
#標題:謎樣的計算机科學之父
#作者:李國偉

李國偉任職於中央研究院數學研究所

參考資料

  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. <計算機械與智能>這篇著名論文現在也可在網路上閱讀:http://www.abelard.org/turpap/turpap.htm
  5. 有關涂林機的介紹可參閱:John E. Hopcroft, Turing
    Machines, Scientific American, May 1984, pp. 70-80.
  6. 有關「丘池-涂林論點」的檢討,請參閱網路上《史丹佛哲學百科全書》的條目:http://www.plato.stanford.edu/entries/church-turing
  7. 以涂林為主要角色的一本科學小說頗值得一讀:John L. Casti (1998), The cambridge Quintet: A Work of Scientific Speculation, Perseus Press. 中文譯本由「新新聞文化公司」出版,書名是《劍橋五重奏》。

咬文嚼字﹕nuclear

葉李華

原子核(nucleus)也簡稱「核」,指原子中心的稠密部分,由數目接近的質子與中子結合而成。核子(nucleon)則是指組成原子核的粒子,亦即質子與中子的統稱。因此「核」與「核子」雖然只差一個字,兩者意義卻天差地遠。

nuclear是nucleus的形容詞,與「核子」並無直接關聯,嚴格說來只能譯成「核」,例如核物理學(nuclearphysics)、核化學(nuclear chemistry)、核反應(nuclear reaction)、核能(或核動力, nuclear power)、核武器(nuclear weapon)與核動力潛艇(nuclear submarine)等。

然而考慮到中文的習慣,諸如核子科學(nuclear science)、核子工程(nuclear engineering)與核子醫學(nuclear medicine)等泛稱倒是可以從寬處理。這並非沒有前例可尋,例如電子學(electronics)就不是研究電子的學問,而是指研究真空管、半導體等「電子元件」的應用科學。不過凡是牽涉到電子元件的事物,冠上「電子」(electronic)當形容詞卻都很恰當,例如電子儀表、電子計算機、電子檔案與電子郵件等等。