2015年3月3日

由淡入濃—如是我觀涂靈形象

涂靈形象日益隆盛的主要理由,在於他從反省思考時的心靈活動開始,建立起一個容易想像,又富於啟發性的機器模式,產生了極大的開創力。

作者/李國偉(任職中央研究院數學研究所)

對於科學史上心儀的大師,除了冷靜學習他們留給人間的智慧遺產外,我們往往還會懷抱著溫熱的心去探索他們的生命處境。今年(2012)很多國家都在紀念涂靈百歲誕辰,然而涂靈41年不算長的人世歷程裡,他未曾佔據到舞台中央的聚光燈。在我開始學習他的開創性理論多年之後,才逐漸認識到他那悲欣交集些許傳奇的一生。

躋身科學巨人
今年2月23日英國著名的科學期刊Nature以涂靈百歲誕辰為專題,讚揚他是Universal Mind,並且認為他是自古以來最偉大的科學家之一。編者的話寫到:「涂靈的成就廣度驚人:數學家景仰他是因為他解決了希爾伯特(David Hilbert, 1862~1943)的Entscheidungs problem ,也就是所謂的『判定性問題』;密碼學者與歷史學家會紀念他,是因為他解開了納粹德國的密碼Enigma,有功於早日打完了第二次世界大戰;工程師會向數位時代與人工智慧的鼻祖歡呼;生物學家會向形態發生學的理論家致敬;物理學家會對非線性動力學的先驅舉杯;而他對理性與直覺的侷限性的看法,有可能讓哲學家皺眉頭,因為1947年他在倫敦數學會演講時說:『如果要期望機器永不犯錯,那麼機器就不可能有智慧。』」

1999年美國的《時代》雜誌挑選出20世紀最具影響力的100人,涂靈也名列在3月29日刊出的科學家與思想家清單裡。以Nature與《時代》推崇涂靈的程度而言,也許會讓人揣測涂靈在世時的風光,有可能直追20世紀知名度最高的科學家愛因斯坦。一般人雖然搞不清楚愛因斯坦的學術內涵,但都知道他發明了「相對論」,也對他那蓬鬆亂髮甚至頑皮吐舌的形象留有鮮明記憶。可是「涂靈」這個名字最常聯想起的畫面,卻是床頭那顆咬了一口的毒蘋果。甚至有人懷疑蘋果電腦的Logo,就是在暗示這樁謀殺天才的悲劇。
2012年為涂靈誕生一百周年,
科學界將舉行盛大紀念活動,
表揚涂靈對科學以至人類文明的貢獻。
初次聽聞
1964年夏天著名數學家陳省身院士來台講學,曾經在台大醫院鄰近中山南路的第七講堂公開演講數學的重要進展。我當時還在建國中學就讀,因為受同學影響喜歡上數學,便懷著好奇的心去聽這場大師演講。聽講印象最深刻的是,繼哥德爾(K. Gödel, 1906~1978)證明「選擇公設」和「連續統假設」與公設化集合論相容之後,科恩(P. J. Cohen, 1934~2007)最終證明它們其實獨立於公設化集合論。高中學生當然無法理解這類工作的意義,可是那些聽起來神秘兮兮的專有名詞,多麼異於平日課本裡的數學,又多麼引起人的玄想。從陳大師的演講中得知數學邏輯在數學基礎的研究上,有這麼精彩深刻的作用,更促進了我學習數學邏輯的興趣。
哥德爾是數學家、邏輯學家也是哲學家。
其提出的不完備定理,讓解決希爾伯特頭兩個
問題的希望就此幻滅。

大四時我自習一本講理論自動機(Automata)的書,才開始接觸到所謂的涂靈機(Turing Machine),這是我對「涂靈」這個名字的最早記憶。後來我到杜克大學攻讀數學邏輯博士,對於涂靈的成就自然認識增多,不過涂靈仍然被哥德爾的身影遮蔽。以陳省身院士常用的比喻方式來說,當時哥德爾已是「菩薩」,而涂靈只算是「羅漢」。從哥德爾與涂靈都名列《時代》雜誌的20世紀百位最具影響力人物來看,現在涂靈總算也修成了菩薩。

可判定性問題
1928年希爾伯特在國際數學家大會上,再次呼籲數學家研究數學的基礎。他特別指出三類重要問題值得探討:

一、數學是不是完備的(complete)?完備性是說對於每一條數學的命題而言,或者可以證明此命題為真,或者可以證明其否定命題為真。
二、數學是不是相容的(consistent)?相容性是說數學體系不可能依照邏輯的步驟推導出矛盾。
三、數學是不是可判定的(decidable)?可判定性是說有一套明確的方法,把它運用於任何給定的命題,它會告訴你該命題是否為真。

希爾伯特自己充滿信心認為這些問題都可以得到確定的答案。早在1900年巴黎舉行的國際數學家大會上,他曾經宣布過23條待解的問題,他說:「每一條明確的數學問題必然能有明確的解答……在數學裡沒有絕不可知的地方(ignorabimus)。」
希爾伯特,德國數學家,是跨越19和20世紀最
具影響力的數學家之一。他在1900年巴黎的國
際數學家大會提出23項重要問題,為20世紀數
學研究指出方向,世稱希爾伯特問題。

但是到1931年,年輕的哥德爾證明了出人意表的結果:

一、對於明確建構起來的形式化算術理論系統而言,如果這個系統是相容的,那麼它就不可能是完備的。

二、這個系統的相容性無法在此系統中得到證明,也就是說必須引進比這個系統更強的論證方法,才有可能證明它的相容性。

這兩項結論構成哥德爾著名的「不完備定理」,而渴求解決希爾伯特頭兩個問題的希望也就此幻滅。

1935年的春天,涂靈去聽紐曼(M. H. A. Newman, 1897~1984)的「數學基礎」課。紐曼是劍橋大學的拓樸學家,也是當時劍橋唯一對數學邏輯最新發展有深刻認識的教授。紐曼曾經出席1928年國際數學家大會,熟知希爾伯特研究數學基礎的方法。涂靈在課堂上學習了哥德爾的不完備定理,也因而知道希爾伯特的第三個問題仍然有待解決。依照紐曼的術語來說,就是要問會不會有一種「機械程序」(mechanical process),把它施用在數學命題上時,能辨識此命題在系統裡能否得證?
英國拓樸學家紐曼,是涂靈在劍橋的導師,
在二次大戰中與涂靈一起破解德軍密碼。(圖片來源:colossus-computer)

專業數學家多半不相信會存在這種判定程序。劍橋名氣最大的數學家哈地(G . Hardy, 1877~1947)在1928年就說:「當然不可能有這種定理,而且幸好不會有這種定理,否則我們就有一套機械的規則來解決所有的數學問題,那我們數學家就沒戲唱了。」法國大數學家龐卡雷(H. Poicaré, 1854~1912)在《科學與方法》一書中以嘲弄的口吻說:「我們乾脆想像有一部機器,一頭把公設丟進去,另一頭定理就跑出來。這好像芝加哥傳奇性的屠宰機,一頭把活豬送進去,另一頭就送出火腿與香腸。如此一來,數學家跟機器一樣,都不需要理解自己在搞什麼了。」但是在哥德爾驚人的不完備定理問世後,對於整個數學是否存在判定程序,不能光靠信心說「當然不可能有」,而值得仔細深入地分析。
涂靈的母校劍橋大學國王學院,其電腦房現以涂靈為名。
(圖片來源:Andrew Dunn)
機械性計算的直觀
涂靈有下午長跑的習慣。根據後來他告訴好友甘迪(Robin Gandy, 1919~1995)的說法, 1935年的初夏,在一次長跑途中暫時休息時,他躺在Grantchester的草地上突然靈光一閃,想出一種「機械程序」解決希爾伯特的第三個問題。他把這項劃時代的創見寫成著名的論文“On computable numbers, with an application to the Entscheidungsproblem”(以下簡稱〈論數〉)。
Grantchester的劍河岸。
涂靈有下午長跑的習慣,據說「機械程序」就是他在一次長跑途中,
短暫在Grantchester草地上休息時所構想出的。

涂靈在〈論數〉第一節就引進後人稱為「涂靈機」的定義,並且作了一系列的推導。用他的機器計算出來的數,當然符合直觀認為是可計算的數。到了第9節,涂靈提出一個一般性的問題:「有哪些可能的程序可以用來計算數?」他要用三類論述法說明自己設計的機器足夠計算所有直觀認為可算的數:

(a) 直接訴諸直觀。
(b) 如果有任何別的方法更形直觀,則證明與涂靈機等價。
(c) 盡量給出實例,顯示大量的數都是可用涂靈機計算的。

涂靈針對(a)所作的論述,風格與一般數學論文大相逕庭。他模擬兒童的算術作業簿,把紙面劃分成方格,只不過把方格改成一直線排列開。方格內允許書寫的符號只准有限種,因為他說「如果我們允許無窮多種符號的話,則有些符號之間的差異會任意的渺小。」然後涂靈分析任何一個計算者(他當時用的稱呼是computer)的行為,應該會取決於當下看到方格裡的符號,以及計算者的「心靈狀態」(state of mind)。涂靈認為心靈狀態也只有有限多種,因為「如果我們允許有無窮多種心靈狀態,有些就會『任意地接近』,以致於產生混淆。」涂靈在此節的末段,還說計算者可隨時離開去做別的事,但是如果他還想回來繼續工作,他就必須寫下一張記錄表,記好當時機器的整體狀態,以便可以依照指示重新啟動計算。總之,這些生動的直觀式分析,讓我們理解涂靈定義他的機器的動機。

在涂靈之前,對於數學系統裡機械化的過程,已經有別人提出各種模式。譬如,哥德爾提出一般遞迴函數(general recursive function),丘奇(Alonzo Church, 1903~1995)提出蘭布達演算(lambda calculus)。這些外貌差異甚大的各種模式,其實都計算出同樣的自然數的函數。丘奇甚至在1935年4月19日美國數學會的研討會上公開宣稱,所有直觀上認為可以明確計算的函數,都已歸屬於一般遞迴函數了。這就成為有名的丘奇論點(Church's Thesis)。這個論點不屬於一般數學裡的猜想(conjecture),因為它涉及無法嚴格定義的直觀概念,所以也無從加以證明,只能盡量舉出實例當做證據,這種狀況類似自然科學裡須用大量的實驗來支持定律。
美國數學家丘奇是涂靈在普林斯頓的導師,
其最為知名的貢獻是蘭布達演算與丘奇論點。
涂靈機後來居上
涂靈在完全沒有跟人討論的環境裡,完成了對於最一般的可計算性的研究,創發了劃時代的涂靈機。當他把論文給老師紐曼看時,紐曼簡直不敢相信希爾伯特的判定性問題(Entscheidungsproblem),居然可以用這麼簡單直觀的辦法解決掉。不幸的是在1936年4月15日丘奇已經發表了他的論文“A note on the Entscheidungsproblem”,而涂靈是在5月28日才把〈論數〉投給倫敦數學會的會誌,所以丘奇領先涂靈解決了希爾伯特的可判定性問題。5月底紐曼寫信給丘奇,強調涂靈在完全沒有人指導與詰辯的情形下獨力完成原創性工作。他希望丘奇能替涂靈向劍橋寫一封爭取獎學金的推薦函,以便涂靈能打破孤獨去普林斯頓追隨丘奇學習數學邏輯。

結果涂靈並沒有獲得獎學金,他靠著劍橋國王學院的單薄薪水留學普林斯頓大學。此時丘奇已經不太活躍,一些對數學邏輯有貢獻的學生也都不在,所以涂靈既沒能解除他的孤獨狀況,也沒從丘奇那裡學到多少新東西。當〈論數〉校稿寄到普林斯頓時,丘奇安排他做一場公開報告。他在家書裡說:「很少人來聽12月2日我在數學俱樂部的演講。要想有人來聽講就必須是有名的人。我演講後的下一週是伯考夫(G. D. Birkhoff, 1884~1944)主講,他的名聲很大,所以講堂都擠滿了人。但是他的演講其實很不夠水準,大家都在背後笑話他。」不僅涂靈的演講沒幾個人來聽,〈論數〉這篇在科學史上永垂不朽的論文出版後,當時也只有兩個人曾經向涂靈索取抽印本。

然而哥德爾是慧眼識英雄的。他原來對於丘奇論點並不完全有信心,直到他看了涂靈對於計算本質的分析,才被說服所有機械性的計算都已經為涂靈機所捕捉。哥德爾與涂靈這兩位偉大的心靈,雖然殊途同歸地推動了可算性理論的發皇,但是終其一生,涂靈都沒有見過哥德爾一面,也沒有跟哥德爾通信討論過問題。

涂靈機所定義的可計算函數既然與眾多其他的模式都等價,為什麼涂靈機後來會變為特別突出的貢獻呢?我個人認為涂靈從分析人類作計算的心靈歷程出發,所得到的模式最容易讓人想像,也最能給出進一步的直觀暗示。譬如在涂靈機模式裡,指導機器運算的指令也是一組有限個符號,它們與在紙帶上作為計算對象的符號,本質上沒有什麼不同。因此導引涂靈很自然地構想出一個通用(universal)涂靈機,它可以把任何其他涂靈機的指令當作自己的運算對象,針對任何給定的起始值模擬原來那台涂靈機的動作並得出相同結果。

因為理論上有通用涂靈機的保證,現代幾乎無所不能的電子計算機,才有了建造的基礎。即使是在涂靈提出他的通用涂靈機概念之後,相當多的人仍然難以想像主要用來計算數字的計算機,有可能用在日常生活的事務上。連製造電子計算機的先驅艾肯(Howard Aiken, 1900~1973)在1953年還說:「如果用來找微分方程數值解的機器,和替百貨公司開帳單的機器,在基本邏輯架構上恰好相同,我會認為這是我曾碰過的最奇妙的巧合。」

計算複雜度
涂靈在普林斯頓近兩年的時間裡,名義上丘奇指導他完成一篇博士論文。其實從後見之明,我們知道涂靈在抵達普林斯頓之前,就已經作出比丘奇更深遠的貢獻。所以他們倆並不像一般博士班師徒間的關係,涂靈不僅沒有從丘奇那裡得到很多有用的思想,甚至他的博士論文因為遷就丘奇的偏好,不得不採取蘭布達符號系統,長度因而增加,並且削弱了涂靈原來更近直觀的風格。這篇名為 “Systems of logic based on ordinals” (以下簡稱〈系統〉)的博士論文發表後,比〈論數〉更缺乏讀者。

〈系統〉想在哥德爾不完備定理破滅了數學整體機械化的夢想之後,重新檢討如果適度地用直觀輔助機械化,數學體系還能走到什麼程度。涂靈在他原有的機器模式裡,再加上一個有問必答的元件,他稱之為oracle,我們暫且譯為「玄器」。當機器按照涂靈機的指令運算到某個階段時,它需要知道某個問題的答案為「是」或「否」時,玄器即刻給出正確的答案。這個步驟在涂靈機的指令裡無法預先設計,因此它相當於運用「直觀」的一次跳躍。

因為涂靈機給予了極富啟示性的思想圖像,使得加入玄器也變得十分自然。另一位與涂靈同時代的美國邏輯學先驅波斯特(Emil Post, 1897~1954),迅速掌握到玄器的重要意義。當我們用涂靈機計算A函數時,如果把B函數的值當作玄器,就表示計算A的難度不會超過計算B的難度。所有只用涂靈機而不需要任何玄器協助就能計算的函數,就構成了難度最低的所謂的可計算函數(也稱為遞迴函數)。波斯特用裝備玄器的涂靈機來區分計算函數時相對的難度,從此開創了計算複雜度(computational complexity)理論的研究。

涂靈機儲存資料的紙帶,以及運算過程中所耗費的步驟數與方格數,很容易啟發人們考慮到計算時使用的時間與空間資源。要使計算在現實世界裡可行,這些資源的消耗必須加以合宜的限制。受不可計算世界裡複雜度研究的影響,在可計算的世界裡也可用消耗資源的多寡來區分相對難易程度。1971年加拿大邏輯學家庫克(Stephen Cook, 1939~)引入了P與NP兩種問題類。粗略地講, P裡的問題都有快速的計算方法,而NP裡的問題到目前為止都還沒找到快速的計算方法。庫克還證明有一些在NP裡的問題如果一旦有快速的計算方法,則所有NP裡的問題都可以有快速的計算方法,這些問題稱為NP完備問題。P與NP到底是不是相異的兩類,已經成為克雷(Clay)數學研究所懸賞百萬美元的矚目問題之一。

形象日隆
涂靈的起步是那麼的不引人矚目,後續的發展也與傳統的學院人士大異其趣。他從普林斯頓返回英國後不久,就加入了替英國情報組織破解納粹密碼的工作,並且取得重大的成就。涂靈在密碼單位的工作經驗,讓他看到許多工作人員整天按照指示埋頭苦算,其實完全不知道背後的動機,最終也解決了非常困難的問題。這使他基本上揚棄了在博士論文裡論辯的立場,從而全然傾向心靈的機械觀,促使他在1952年提出「模仿遊戲」,也成為當今檢驗計算機能否展現智慧行為的著名涂靈測試(Turing test)。

涂靈在1948年才首度獲得大學教職,參加紐曼在曼徹斯特大學建造電子計算機的團隊。他在學術界裡受到的最大肯定,是1951年因為紐曼與羅素的提名,而當選了皇家學會會士。但是因為他在數學邏輯上的成就難為人懂,而二戰破解密碼的工作又難為人知,所以很少人真正認識他的學術地位。1952年涂靈還因為同性戀被捕,受到警方化學藥物處理的羞辱。到1954年更莫名其妙地死於遭氰化物沾染的蘋果。

涂靈是那種真正超越時代的天才,必須假以時日才能肯定他對人類深遠的影響。即便是在英國那種較寬容菁英分子的國家裡,涂靈的一生也並非順暢愉悅。我們很難想像在斤斤計較評鑑、考核、獎賞的功利社會裡,會有可能產生一位不循常軌創新的涂靈。自二十世紀後半期以來,電子計算機逐步而全面地改變了人類生活的樣貌。做為計算機理論先驅的涂靈,因為建構起最貼近實際的模式,也最能突顯軟體在計算程序裡的核心作用,我們可以合理地預期,他的聲望必將持續揚升。

沒有留言: