2016年3月7日

為何涂靈是電腦之父?

作者/李中志〈美國伊利諾州立大學電腦科學教授。〉

涂靈於1945~1948年,回到學院重拾他最大的夢想—造出一台能實踐所有計算概念的機器。他在美國留學時亦師亦友的馮紐曼(John von Neumann)吸收了涂靈的構想,不受戰爭影響,已早幾年著手設計了世上第一台電腦,可儲存程式的「馮紐曼機」。戰後重拾舊夢的涂靈很快就再度超越,由他為英國政府祕密設計的自動計算機(Automatic Computing Engine, ACE)比「馮紐曼機」與稍後賓州大學團隊的ENIAC(EDVAC 的前身)還要先進許多。世界得以進入電腦的新紀元,涂靈為我們跨出了最艱難的第一步。


天才涂靈
對筆者而言,涂靈是最偉大的科學家之一,但他自己並不這樣覺得。電影《模仿遊戲》想要傳達的訊息並不準確,他固然沒有在生前得到應有的榮耀,但也不是鬱鬱寡歡,他其實過得相當愜意,對自己的性傾向也沒有羞於啟齒,還常常以此開玩笑。比較正確的描述是,當代大多數人固然不了解他的天才,但由於他自己也不以天才自居,也就沒有懷才不遇的失落感。對於當代主流科學的重要進展,涂靈一直自認是局外人,布萊切利園的工作是唯一的例外,他在那邊覺得有參與感,也意識到他的工作是重要的,充滿成就感。事實也是如此,涂靈在布萊切利園的成就縮短了戰爭,解救了許多無辜的生命,當然值得尊敬,但就科學史來看,反而沒有太大的科學意義。

馮紐曼(John von Neumann)預見了涂靈的天才,也了解戰爭的壓力並不能讓涂靈自由發揮。因此馮紐曼曾試圖說服涂靈不要回到烽火連天的歐洲,留在美國從事學術研究。但涂靈放棄馮紐曼幫他爭取到的研究工作,選擇報效國家。馮紐曼來自匈牙利,只比涂靈大11歲,屬早慧型的天才,二十世紀的重要科學進展,幾乎都有馮紐曼的身影。涂靈初進劍橋便被馮紐曼關於量子力學的數學基礎吸引,後來兩人在普林斯頓相遇相惜,馮紐曼是涂靈心目中在普林斯頓的指標人物之一,與愛因斯坦並列。馮紐曼不但本身是二十世紀最重要的科學家之一,更是少數能慧眼識英雄的人,一方面一眼就看出哥德爾(Kurt Gödel)1931發表的「不完備定律」是文明史上對理性主義最大的顛覆,一方面也看到涂靈1936年發表的自動機是人類理性的最後實踐。

從他身上可見其鮮明的人格特質,其堅毅卓絕的精神與窮究物理的睿智,更值得我們嚮往與學習。

不完備定律
在一個嚴謹的演繹系統內,如果每一個合法敘述都能在這個系統內證明其真偽,則我們說這個系統是「完備」的;反之,若這個系統存在些合法敘述,但我們無法辨別其真偽,則我們說這個系統是「不完備」的。「不完備定律」證明任何一個演繹系統,如果它不自相矛盾,又足以描述基本的數學四則運算,那麼這個系統必定是不完備的。也就是說,創造一個嚴謹的計算模型來解決一切紛爭,理論上就是不可能的。

涂靈建立理論電腦基礎
1936 年夏天,涂靈來到普林斯頓,兩年內便完成了他的博士論文,該論文試圖為「不完備定律」尋找一個出路,有人認為是普林斯頓大學有史以來最重要的兩篇博士論文之一,另一篇是納許(John Nash)的博弈理論。涂靈依然像個局外人,沒把這篇博士論文當一回事,畢業後再也沒有回到這篇論文的主題,但論文領先當代,發表後約二十年才由後來的學者理解,重新重視。以涂靈提出的相對計算與序數邏輯(ordinal logic),分析計算複雜度的本質與結構,成為現今理論電腦的基礎。

在普林斯頓的同時,涂靈完成了他在劍橋時期即有的構想,於1936 年發表了他最重要的論文:〈關於可計算數,一個決定問題的運用〉(On Computable Numbers, with an Application on the Entscheidungsproblem),最後一字為「決定問題(decision problem)」的德文,來自希爾伯特(David Hilbert)在1928 年提出的挑戰。用今天的語言來講,這個挑戰是問:給定任何一套計算系統,能不能有效地驗證這個系統裡所有程式的語意?

其實哥德爾1931 年的「不完備定律」已隱含了否定的答案,邱奇(Alonzo Church)稍早也得到相同的結論,因此一如以往,涂靈沒把這篇論文當成讓他擠身科學史英雄榜的重要成就,他覺得他只是把別人的東西再證明一次。他原本還不想發表,是他劍橋的老師認為他的證明十分原創,催促多次才完成,涂靈還為其中無關緊要的小錯誤懊惱不已,1937 年發表修訂版。儘管如此,這篇論文遠遠超出純數學符號的意義,涂靈憑空建造的簡單小機器,雖然原始目的是讓它無望地算著不可解的問題,世界卻因此有
了電腦。涂靈稱那個簡單異常的機器為a-machine,取「automatic」的第一個字母,後人稱之為「涂靈機(Turing machine)」,也稱「自動機(automata)」。這個小機器就如一個結構簡單的胚胎,是當今一切電腦發展的原點。

大膽革命引支持反對聲浪
涂靈初入學術界時數學界正處在一個革命被完全殲滅、頹喪的超穩定狀態。二十世紀初由羅素(Bertrand Russell)與懷海德(Alfred Whitehead)領軍的搶救數學基礎計畫,被哥德爾震古鑠今的「不完備定律」徹底擊敗。理性主義者的終極願望,以一個絕對嚴謹的計算模型來解決一切紛爭,成為一個永不可能實現的夢想。這是一個死刑宣告,羅素轉向哲學與政治,再也沒有回到數學領域。

頹喪的數學家彷彿回到中世紀,在一片廢墟中各自建立自己的城堡,各式各樣的計算模型,精巧嚴謹,但完全抽象,無法直觀理解。其中較有名的計算模型有羅素在《數學原理》裡創立的型論,哥德爾的「遞迴函數」,邱奇的「λ– 演算法」等等。邱奇為涂靈在普林斯頓時的指導教授,曾大膽提出「邱奇假說」,這個假說是一個經驗式的結論,認為所有合理的計算模型都是一致的,但頑固小心的哥德爾拒絕相信。

來自維也納的維根斯坦(Ludwig Wittgenstein)為羅素的學生,任教於英國劍橋大學哲學系。維根斯坦戰前已聲名遠播,他刻意要避免「不完備定律」帶來的失敗主義,企圖淡化它的衝擊,倒不是為了替他的老師羅素留些顏面,而是此時的他,根本不相信機械計算是人類理性的展現。涂靈曾經在課堂上與維根斯坦就數學不完備的意義有過辯論,逼得維根斯坦不知如何回答,只好提早下課。維根斯坦一夜苦思,在下一堂課承認數學不完備可能導致的重大危機,說不定倫敦大橋會因而倒下,幾乎違背了自己的哲學觀。

在這樣的氛圍下,涂靈捨傳統利用悖論的方式論證「不完備定律」,希望能以建構數學的原則找到一個無法計算的數,不久他便創造了「涂靈機」的標準運算機制。維根斯坦對涂靈機下了一個注解,他說:「涂靈機是一個計算的人。」所謂「一個計算的人」是指一個沒有心智、只知按表操課、依規則計算的人。雖然這是很精確的描述,兩人對人工智慧截然不同的看法,由此已經顯露。

涂靈機誕生
涂靈機模型不但統合了所有數學上抽象的計算概念,還在符號之外賦予直觀的操作定義,計算完全可由機器取代。涂靈機的組成包括一個格式化的磁帶,一個讀寫頭,一個內建的狀態轉換表。這些要素也就是當今電腦的三大元件,磁帶為記憶體,讀寫頭為輸出入裝置,狀態轉換表為指揮中央處理器(CPU)程式,掌控計算的基本邏輯。磁帶記錄讀寫頭能辨識的符號,例如0 與1,而計算就是根據讀寫頭讀到的符號與狀態轉換表的指示所產生的一連串動作。這一連串的動作不出四個簡單的指令:讀、寫、右移磁帶一格、左移磁帶一格,可視為當今一連串的CPU 微指令。

最重要的,涂靈提出「通用涂靈機(Universal Turing Machine)」,創造了「儲存指令」與「可程式」涂靈機的構想。每一個狀態轉換表代表一個涂靈機,如果將狀態轉換表加以編碼,狀態轉換表就可編寫為我們現今理解的電腦程式,依不同的狀態執行不同的指令。也就是說,一個程式就是一個執行特殊計算的涂靈機,而通用涂靈機能根據任何儲存在磁帶上的程式(狀態轉換表),準確的模擬該程式所代表的涂靈機。換句話說,通用涂靈機具備了「可程式」的能力,讓我們能透過編寫程式,讓通用涂靈機執行任何我們要的計算。全功能計算機正式誕生了!

在涂靈交給邱奇的博士論文裡,他下了一個註腳:「我們應該以『可計算函數』來表示一個可用機器計算的函數,並且讓『有效計算』代表任何直觀的計算步驟,不必限定在任何特殊的計算定義。」

這正是「邱奇假說」的精神,所有合理的計算模型都是一樣的,不必限定在某種計算定義。證明特定的計算模型等同於涂靈機的計算能力並不困難,涂靈便證明哥德爾的遞回函數、邱奇的λ– 演算法、涂靈機三者的計算能力等價。

馮紐曼勸涂靈留下不成後,便依其「可程式」與「儲存指令」的構想,自行以真空管在普林斯頓高等研究院設計出第一台電腦,實現了西方自古希臘以來三千年的計算之夢。戰後涂靈替英國政府設計的ACE 自動計算機已具備現今電腦結構的雛形,包括大量使用記憶體、插斷處理、簡易程式語言,比美國稍後著名的「離散變量自動電子計算機(Electronic Discrete Variable Automatic Computer, EDVAC)」還要先進。但因英國把ACE 的設計列入國家機密,所以不似EDVAC 受到各方的注意。

這些著手製造電腦的先驅者,包括涂靈自己,一開始便使用暫存器與記憶體取代涂靈機的標準磁帶,但兩者計算能力並無不同。之後許多學者紛紛提出證明,如麻省理工學院的明思基(Marvin Minsky)與我國已故院士王浩,均有詳細的證明。短短不到七十年的時間,電腦的軟硬體已歷經數代的革命,但無論如何花俏先進,仍不離涂靈機的基本原理。涂靈機成為電腦科學系計算理論必修的主題,以他命名的「涂靈獎」等同於電腦科學的諾貝爾獎,是電腦科學家的最高榮譽。

涂靈替英國政府設計ACE 成功之後,對探究計算極限的渴望更加熱烈。那時全世界剛見識到屈指可數的電腦,當報紙頭條還在為笨重的電腦能在數秒之內算出頗為無趣的數字計算而雀躍不止時,涂靈對電腦的想像已跳到另一個層級了,機器能思考嗎?電腦能表現智慧嗎?

延伸閱讀
1. Alan Turing. On Computable Numbers, with an Application on the Entscheidungsproblem, Vol. 42: 230-256, Proc. London Math, 1965.
2. Marin Davis, The Road from Leibniz to Turing, The Universal Computer, 2000.
3. Andrew Hodges, Alan Turing: The Enigma. Updated edition with a New preface, Princeton University Press, 2014.

沒有留言: