圖靈夢

今時今日，談到電腦，大家都只知道蘋果電腦的Steve Jobs，其實電腦科學之父是一位稱為艾倫圖靈(Alan Turing)的英國數學家(1912-1954)，他的故事充滿傳奇色彩，但同時是一個悲劇。

艾倫圖靈(Alan Turing)(1912-1954)

艾倫圖靈之所以被稱電腦科學之父，是因為他在數學上奠定了現代電腦的範式基礎。我們今天用的個人電腦，智能手機，手提電腦和平板電腦，每一顆中央處理器CPU，以至任何一個電腦程式都是基於圖靈的範式運作的。他同時是位數學家、邏輯家和馬拉松選手，是多才多藝的天才。他甚至協助英國製造了電腦，在二次大戰中破解了德軍的密碼系統，使盟軍得到了優勢。他超越了年代，深入地思考了人工智能的可能性，他的「圖靈測試」成為現時量度人工智能性能的基準。

世界各地許多電腦專家和數學家，都將在2012年紀念這位偉人的100歲冥壽，為此舉行許多學術和公開的活動，並把2012年定為「圖靈年」[4]。後人設立的「圖靈奬」一向是電腦科學界的最高殊榮。但大眾似乎依然對圖靈這個人不太了解，到底是甚麼原因呢？

也許這一刻你有一個疑問，甚至懷疑，圖靈這個人如何奠定了現今電腦的基礎。這要從圖靈時代電腦的面貌開始說起了。

電腦的英文名是computer，又可譯作「計算機」，故名思義是負責計算的機器。在圖靈之前的年代，計算都要靠人手，處理大量運算這項工作又沉悶又繁複，十分容易出錯，所以的而且確，最初電腦的出現是為了代替人類擔當計算這苦差。

最早的計算機是以機械而非電子元件構成，所以每一台計算機都十分巨型，而且速度十分慢。手動的計算機有一張書檯大小，之後的自動計算機可以有一個房間那麼大，當時用在儲存資料的是一條條長長的打了孔的卡。所以現今的桌面電腦又叫「微電腦」(microcomputer)。但這都不是當時計算機演進成現代電腦的最大障礙，最大的問題是，圖靈之前的計算機，每一台都只可進行某些運算：要做新的工作，就要造一台新的計算機！

IBM Mark I: 1944年的電腦

數學基礎危機

然而，圖靈研究計算機其實另有原因，而這和整個數學的基礎有關。1920年代是科學界最雄心勃勃的時期，人類的知識因許多偉大的理論而推向新的境界：愛因斯坦發表了相對論，揭示了時間和空間的結構；人類發現了原子的內部結構；得知基因的所在及其遺傳原理；宇宙的膨脹暗示其起源是大爆炸。當時許多學者認為科學的剩下的問題已經不多，人類已經掌握宇宙大部份的知識。

至於數學--這門研究最基本真理的學問，當時也有類似的樂觀情緒，有些數學家正在埋首研究數學所有定理(theorem)的基礎，他們希望找到一套可推導出所有定理的簡單的邏輯系統。這個系統有三個特性：

1. 沒有未證明的命題(完備性completeness)

2. 沒有內在的矛盾(一致性consistency)

3. 只要清楚陳述命題，必定有一個演算法(方法)，找出一個命題是否可以被證(可判定性decidability)。

這些足可證明數學的完美性。可是在這個數學界的運動開始十數年間，就陸續有數學家如哥德爾(Kurt Gödel)和羅素(Bertrand Russell)提出數學邏輯系統中，有些命題並不能被證明或反證(見哥德爾「不完備定理」)，也的確存在內在矛盾(見「羅素悖論」)。

圖靈機

艾倫圖靈在1935年於倫敦國王學院研究數學，對數學基礎的第三個問題--可判定性，產生了濃厚的興趣。為了解答「數學是否可判定」這道難題，圖靈構想了一台自動機器去進行演算的步驟，它可根據簡單的規則，閱讀和改變寫在一紙條上輸入的符號(如1和0)，當有結果的時候就輸出然後停止。後人稱這台構想的機器為「圖靈機」(Turing Machine)。在現代的語言來說，圖靈機其實就是電腦程式。圖靈證明，圖靈機可進行任何演算，但一台機只能進行某些演算。所有圖靈機的集合，就包含了世上所有的演算法。

圖靈機會閱讀一串符號

圖靈發現，因為圖靈機的內容可以被清楚陳述，它本身也可以利用紙條上的符號來代表，成為圖靈機的輸入。圖靈進一步構想一種特殊的圖靈機，它可接受另一圖靈機M及其輸入，然後模擬M的運算。這一種特殊的圖靈機，叫做「通用圖靈機」(Universal Turing Machine)。於是，世上只要有一種圖靈機--通用圖靈機，就可以執行所有演算。

利用通用圖靈機，圖靈證明，沒有一個圖靈機，可以判定另一個圖靈機是否會輸出結果和停止[3]。換句話說，圖靈證明了數學以內有些命題，即使被清楚陳述，也沒有方法可以判定它可否被證。這可說是繼哥德爾和羅素後，對數學界的第三個打擊。學術界稱這一連串事件為「數學基礎危機」。

這些數學問題至今仍未完滿解決，但通用圖靈機的發現，對於現代電腦的誕生和發展則帶來了深遠而正面的影響，甚至可以說，沒有通用圖靈機的理念，就不會有今日的電腦。我們今天用的電腦，不是一台只進行某些計算的計算機，而是一台有多種用途，能執行多種程式的機器。每一個程式都有圖靈機的結構，有些程式甚至本身是通用圖靈機，可以執行其他程式，例如作業系統(Operating System = "OS")。通用圖靈機的發明，允許電腦內部有一個層階式的結構，使其可以進行越來越複雜的工作。當其他機器可替代人類進行體力或技術上的工作，因為圖靈的貢獻，我們終於有一種機器可替代人類進行智力上的工作，它就是電腦。

電腦層階式的結構使其可以進行越來越複雜的工作

天才隕歿

然而，圖靈的事跡一直不為世所知，電腦之父的榮譽則由發揚圖靈理念的馮•紐曼(John von Neumann)所奪得，這和歷史因素和圖靈的私生活有關。首先，圖靈為英國破解德軍的密碼系統，這個是國家機密；英國也視圖靈在電腦的研究為某程度上的機密。反之，馮•紐曼身處的美國對於他發明的新計算機持開放的態度，學者間可以自由交流，美國的電腦科學因而得到長足的發展，之後一直處於領先的地位。

私生活方面，圖靈其實有當時不為人所認同的一面--他是位同性戀者。當時同性性行為在英國是非法的，同性戀者都儘量把身份隱藏。在1952年，圖靈和一位工人階級的同性戀者發生了關係，可是沒料到圖靈遇人不淑，他的戀人貪圖他的財物，和同黨到圖靈的住所爆竊。圖靈之後報警，但同時在法庭上揭露了自己同性戀者的身份。面對同性性行為的控罪，圖靈只有兩個選擇--一是坐監，一是接受「化學閹割」--注射女性賀爾蒙，以減低其性慾。圖靈選擇了後者，但這並沒有令他逃過被禁止在大學做研究的厄運。不能繼續對知識的追求，對一位學者來說無疑是人生中最殘忍的刑罰；在身心的雙重打擊下，兩年之後，圖靈在寓所吃下沾有山埃的蘋果自殺身亡，終年41歲。所以英國政府一直對圖靈的事避而不談，直到2009年，西方世界比較接受同性戀之後，才公開認錯，向死去的圖靈道歉[1]。

一位天才橫溢，對人類知識和技術有巨大貢獻的學者，因為世人的偏見而含恨而終，無疑是一場令人痛心疾首的悲劇，是對全世界的一個損失。天知道如果圖靈沒有自殺，他會對數學和電腦的發展有何進一步的影響？今天的電腦又會是何模樣？圖靈的故事，不但關於人類追求真理的熱情，也再一次提醒我們偏見和對傳統的不加思索，在歷史上扼殺了多少創造的靈魂，毁滅了多少人類進步的可能性。無論如何，在2012年圖靈年，會有許多人在使用電腦時悼念和感謝這位偉人，沉思歷史給我們的教訓，和延續圖靈的夢。

以通用圖靈機為概念的畫作；留意左上角寫有代表山埃"CN-"的蘋果

參考：
[1] PM apology after Turing petition. BBC News. http://news.bbc.co.uk/2/hi/8249792.stm
[2] Alan Turing (傳記). http://www.turing.org.uk/
[3] Halting problem (“停機問題”--圖靈證明不能被證的問題). http://www.cs.odu.edu/~toida/nerzic/390teched/computability/unsolv-1.html
[4] Turing 2012 (圖靈年紀念網頁). http://www.mathcomp.leeds.ac.uk/turing2012/