超越數學的判定——通用圖靈機的誕生_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！2022-12-15 10:09
撰文 | B. Jack Copeland（新西蘭坎特伯雷大學傑出教授）
翻譯 | 王勇、黃紅華
那是劍橋大學1935年的四旬節學期（譯者注：復活節前的六週禁食期，也是劍橋大學冬季學期的名稱。），正值暮冬時分。在暗淡的灰色光線中，劍橋大學古老的尖塔和圍牆環繞的學院更顯年代感。在英國的這個潮濕而寒冷的角落裏，儘管冬天異常温暖，但天氣依然是陰沉沉的。在劍橋大學聖約翰學院旁邊的院子裏，鐘樓上的三一鍾在上午10點響起了刺耳的鐘聲——10下驚心動魄的鐘聲接連10下更高音調的鐘聲，詩人華茲華斯（Wordsworth）曾把三一鐘的鐘聲比作“女性”的聲音。聖約翰學院位於狹窄的中世紀老式街道上，距離國王學院不遠，據説是劍橋大學第二富有的學院，僅次於最富有的三一學院。有一個流傳了幾個世紀的傳言，説從劍橋大學聖約翰學院一直走到遙遠的牛津大學聖約翰學院，都不用踏出聖約翰的土地。馬克斯·紐曼是聖約翰學院的一名研究員，他大步走進了教室。戴着眼鏡，禿頭，年近40歲的紐曼，是英國數學界冉冉升起的新星。走路的時候，身上的學位服會隨着他的步伐不斷擺動。教室已經有幾個世紀的歷史了，給人的感覺好像是一座古老的大教堂或修道院的一部分。紐曼教授的課程“數學基本原理”以難度大而著稱，所以教室裏的學生並不多。圖靈正專心致志地坐在講台下。
該系列課程的“壓軸戲”是闡述庫爾特·哥德爾（Kurt Gödel）取得的一些驚人成果。哥德爾是維也納大學一名25歲的數學家，生性沉默寡言，但非常聰明。1940年，哥德爾逃離了納粹統治下的維也納來到美國——納粹不顧他患有各種真實的或是編造的疾病，要求他參軍，但他寧願成為難民也不參軍。潛伏在德國潛艇中橫渡大西洋的風險太大，所以哥德爾沿着蘇聯的西伯利亞大鐵路一路向東，然後乘船從日本逃到舊金山。他被普林斯頓高等研究所錄取，那裏已經聚集了一批歐洲最偉大的科學家和數學家，其中包括阿爾伯特·愛因斯坦和約翰·馮·諾伊曼，諾伊曼在之後曾深度參與洛斯阿拉莫斯（Los Alamos）原子彈計劃。
1931年，哥德爾證明了算術系統的不完備性，這一驚人而又奇特的結論將是紐曼最後幾節課的主題。哥德爾的成果被稱為“哥德爾不完備性定理”，至今仍是數學領域最令人震驚的發現之一。哥德爾不完備性定理表明，無論算術系統的形式規則是如何制定的，總會有一些算術公理無法通過規則來證明，就如簡單的皮亞諾算術系統中的關係式2+2=4。這給人的感覺有點兒像製造出來的拼圖故意少了一些碎片，或者新地毯永遠無法完美覆蓋到房間的四個角落。消除不完備性的唯一方法似乎是重置規則，使其前後自相矛盾，但這似乎並不是一個完美的解決方案。
哥德爾指出，數學中有些真實性無法被證明。這個結論令人震驚，甚至激怒了一些人。數學家不僅傾向於認為所有真實的事物都可以被證明，而且認為所有重要的事物都應該能夠被證明，因為只有通過清晰的、規則明確的嚴格證明才能帶來確定性。紐曼計劃在未來幾周的時間裏來講述這個令人敬畏的主題，在當天的演講中，他談論的不是哥德爾，而是德國哥廷根大學的著名數學教授希爾伯特（David Hilbert）。希爾伯特比哥德爾年長40多歲，實際上他被譽為歐洲數學界的教皇。在數學領域，希爾伯特有句名言：“我們必須知道，我們必將知道。”1900年，在巴黎國際數學大會的演講中，希爾伯特向國際數學界提出了23個有待解決的數學難題，這為20世紀的數學發展制訂了計劃。而圖靈，一個頗有些憤世嫉俗的劍橋研究生，將證明希爾伯特的部分觀點從根本上就是錯的。
紐曼正在向學生介紹數學中“系統化”程序的概念，這是希爾伯特整個方法論體系的核心概念。我們每個人在學校裏學過的長乘法規則就是一個典型例子，它很好地説明了數學家所謂的系統化程序的含義。系統化程序就像簡單的紙筆法，任何人都可以機械地按步驟執行，而無須任何創意或真知灼見。類似天分或直覺的東西就再也不需要了。有經驗的操作員甚至都不需要知道程序的用途，就可以準確地執行它。操作員可以按照説明書上的指示準確地執行程序，而不必瞭解程序的目的、運作方式和原理。實際上，這不僅僅是一個抽象的概念。在企業、政府和研究機構中，有成千上萬的負責計算的人員在執行系統化的操作流程。他們所做的煩瑣的數學計算工作，如今已被電子計算機取代。有趣的是，這些從事計算工作的職員本身就被稱為“計算機”。只是在那個時代，計算機根本不是一台機器，而是一個人，一個能夠做到死記硬背的數學文員。
紐曼和學生説，這些系統化的數學程序的基本特徵是可以通過機器來執行。這在當時是一種很新穎的表達方式，紐曼的演講激發了圖靈的想象力。許多年後，紐曼回憶起圖靈發明的通用圖靈機，説：“我相信這一切都是源於他參加了我關於數學和邏輯基礎的課程。”紐曼認為，關於機器可以執行系統化程序的提議，啓發了圖靈去“嘗試並説明一個完美的通用計算機器意味着什麼”。紐曼的演講讓圖靈非常着迷，他瘋狂地思考着，以至於對演講內容的研究佔據了他多年的工作生涯。奇特的是，圖靈似乎很少和別人討論自己的想法，或者告訴別人他在想什麼——就連紐曼也不例外。圖靈認為這是他自己的問題，他覺得沒有必要去和別人討論。
一天，在國王學院的高桌晚宴上，學院的另一位研究員理查德·佈雷斯威特（Richard Braithwaite）試圖讓圖靈介紹下他的研究工作。佈雷斯威特意味深長地説自己能理解哥德爾理論的內在聯繫，但是他發現圖靈對此毫無反應。後來佈雷斯威特在一封信中寫道：“圖靈完全不清楚哥德爾的工作。”他還補充道：“在一定程度上，我認為是我讓圖靈注意到他的工作和哥德爾的工作之間的聯繫。”也許圖靈太過沉迷於研究通用計算機，他甚至都懶得去聽紐曼關於哥德爾的後續講座了。或許這就是紐曼後來頗為尖刻地稱“圖靈具有性格缺陷”的一個例證，即“圖靈很難藉助或利用別人的工作成果，反而更喜歡自己解決問題”。哥德爾當然沒有這樣的“缺陷”，他毫不吝嗇地讚揚了圖靈在那一年裏所取得的成就。哥德爾慷慨地説，圖靈向他展示了“正確的視角”。利用圖靈的發現，他成功地將不完備性定理的適用範圍擴展到涵蓋所有包含基本算術形式的數學系統中。數學中的不完備性幾乎無處不在。
1936年4月底，在一番精心準備後，圖靈拜訪了紐曼，並給了他一份詳盡的《論可計算數及其在判定問題上的應用》的論文草稿。紐曼在閲讀這篇論文時一定很震驚。圖靈發明了一種通用機器，這台理想化的機器由一個無限的內存（一個無限的紙帶）和一個“掃描器”組成，掃描器沿着紙帶來回移動，讀取紙帶上打印的內容，然後在紙帶上進一步打印出更多的內容。在開始計算之前，機器的程序和計算所需的所有數據都已打印在紙帶上。通過選取存儲在紙帶上的各種不同程序，操作員可以讓機器執行任何“人類計算機”可以執行的過程。這就是圖靈稱之為“通用”機器的原因。
在那個時代，“計算機器” 特指能夠執行由 “人類計算機” 完成的工作的機器。圖靈把他的發明稱為“通用計算機器”（universal computing machine），不久後，它被簡稱為“通用圖靈機” （universal Turing machine）。今天，現在大量有關通用圖靈機的文獻中，它的名字有時會被誤稱為“Turning machine”或“Türing machine”，甚至是 “universal touring machine”。通用圖靈機是現代計算機的架構基礎，由單一硬件主板構成，通過使用存儲在內存中的程序，可以輕鬆地處理各種迥異的任務，例如數學計算、文字處理和下棋等。
圖靈致力於駁斥希爾伯特關於數學本質的權威觀點，通用計算機的提出是駁斥其觀點的關鍵一步，但也因此招致了希爾伯特的反駁。通過對通用計算機行為的推理，圖靈能夠證明有一些定義明確的數學問題是通用計算機無法解決的。這個結果同哥德爾的不完備性定理一樣令人震驚。正如我們今天可以很清晰地表述，圖靈證明了對於部分有明確定義的數學問題，即使計算機有無限的內存空間，能夠永遠持續計算，在有窮的步驟內也無法給出“是”或者“否”的答案。充滿幹勁的計算機程序員有時認為，只要問題表述得足夠精確，能夠寫出合適的程序，計算機就能解決任何數學問題，但是圖靈的結論表明，這種樂觀是沒有根據的。
圖靈給出了幾個此類定義明確的數學問題作為示例，它們都是計算機在有窮步驟內無法解決的。其中之一就是打印難題，即針對任意一個給定的圖靈機程序，判斷運行該程序後是否一定會在紙帶上打印“0”。許多程序會在某個時刻打印出0，而有些程序則永遠不會。從原理上講，即使不運行圖靈機，只要對程序的性質進行推理，應該是可以做出判斷的。只要證明經過有限步數的推理，我們就可以給出“是”或“否”的明確答案，而且更進一步，不管對哪個圖靈機程序執行推演，我們都應該可以給出明確的答案。如果完成上述兩點的證明，那就解決了打印難題。顯然，沒有一台計算機可以解決這個看起來很簡單的問題。
哥德爾和圖靈給希爾伯特關於數學本質的觀點帶來了雙重打擊，並且從此再也沒有恢復。哥德爾的不完備性結論第一次打擊了希爾伯特關於數學本質上可證明的觀點。5年之後，圖靈徹底推翻了希爾伯特搖搖欲墜的寶座。哥德爾的打擊集中在一個非常具體的系統算術規則上，而圖靈使用通用機器作為武器，在更普遍的範圍進行了反駁。基於圖靈機能夠執行任何系統化程序這一事實——如今我們簡稱其為“圖靈論題”，圖靈能夠得出比哥德爾更普適的結論。圖靈開發了重繪數學藍圖所需的工具，精確指出了與打印難題類似的一些數學問題，是無法通過任何系統化的程序來解決的。
希爾伯特認為，一定存在一個最高階的系統程序，可以用來確定數學中的真假。紐曼嘲諷地稱這個系統程序為“新的魔法石”，暗指能夠幫助鍊金術士把鉛變成黃金的神秘物質。有了這個神奇的系統程序後，任何人不需要任何見識、直覺或創意，都能分辨出任意給定的數學命題是對還是錯。希爾伯特説，為了把整個數學體系建立在“人人都認同的具體基礎上”，就必須存在一個最高階的系統程序。哥德爾的工作動搖了人們對存在最高階系統程序的信念，現在圖靈又提出了一個完全令人信服的論點，那就是不存在最高階程序。如果這個程序確實存在，那麼通用圖靈機就可以實現它，因為通用圖靈機可以執行所有系統程序。有了這個“新的魔法石”，通用圖靈機就能解決所有“是”或“否”的問題。然而，圖靈已經明確地證明，通用圖靈機不能解決所有“是”或“否”的問題。毋庸置疑，希爾伯特的最高階系統程序不可能存在。
儘管當時對圖靈來説，糾正希爾伯特謬誤的工作很重要，但從今天的角度看，這與他發明精妙的通用計算機相比，真的是不值一提。圖靈從一開始就對製造通用計算機產生了濃厚興趣，但他並不瞭解合適的製造技術。在維多利亞時代，頗具遠見的查爾斯·巴貝奇曾經夢想建造一台巨大的通用數字計算機，他稱之為“引擎”，可以接管數百個“人類計算機”的工作（如圖）。如果圖靈是現代計算機之父，那麼巴貝奇無疑就是其祖父。巴貝奇在去世前完成了雄心勃勃的“引擎”機的雛形設計，但是他從來沒有製造出完整的機器來。根據巴貝奇的設計，機器讀取的指令打印在與色帶相連的卡片上——這個想法是巴貝奇從自動提花織布機上借鑑來的。
“分析引擎”的設計初衷，雖然考慮了把數據存儲在其內存（巴貝奇將其簡單地稱為“存儲器”）中，但是並沒有考慮指令本身的存儲。巴貝奇的機器缺少現代計算機的基本特徵，即圖靈的存儲程序設置。由於巴貝奇生活在維多利亞鐵路時代，所以他打算利用鐵路發動機和其他工業機械使用的零部件，如黃銅齒輪、棒、棘輪、小齒輪等，來實現建造計算引擎的計劃。
採用類似巴貝奇的機械部件，當時人們成功地製造出了小型專用計算機。1931年，麻省理工學院研製的模擬微分分析器（Differential Analyser）就是其中之一。該計算機需要一個熟練的技工使用鉛錘來為每項新任務“編程”！不過，巴貝奇“蒸汽鐵路時代”的技術對圖靈來説毫無用處。圖靈需要可以支持高速運行的技術，做到能夠將指令和數據存儲在一個相當緊湊的空間裏，而機械齒輪無法勝任。1936年，機電式繼電器成為製造電子信息處理設備（如電話交換機和穿孔卡片分揀設備）的主要技術。它是一個小型的電動開關，由電磁鐵和彈簧推動的金屬棒組成。當金屬棒朝一個方向移動時，就可以聯通電路，當金屬棒朝相反方向彈回來時，電路就會斷開。繼電器體積大，速度慢，還笨重，而且可靠性也差。圖靈開玩笑説，一台由繼電器製成的通用圖靈機，需要有倫敦市中心的阿爾伯特音樂廳那麼大的空間才放得下。直到第二次世界大戰期間，圖靈和紐曼同在布萊切利莊園從事密碼破譯工作，他們才瞭解到如何製造通用圖靈機。秘訣就是電子管，英國人叫電子管，美國人則稱其為真空管。因為電子管中唯一運轉的部分是電子束，所以它的運行速度比繼電器快很多倍。這兩位密碼破譯者的夢想就是建造一台高速的通用電子計算機。
紐曼曾在聖約翰學院講授過這個棘手的問題，圖靈在他的研究中也直面了這個難題。1939年，哥德爾在訪問距離芝加哥兩小時車程的聖母大學時做了一些邏輯導論的講座，並對圖靈關於判定問題的看法進行了生動的描述。哥德爾提到了一個想象中帶有曲柄的機器。這台機器有點兒像打字機，可以在其中鍵入數學公式。輸入一個可以用所謂的“命題演算”（非常簡單的基礎數學）概念來表示的公式，然後轉動曲柄一次，如果在命題演算中公式能被證明，則機器會響鈴，如果該公式無法被證明，則不會響鈴。也就是説，機器能夠“決定”這個公式是否可證明。圖靈對判定問題的研究顯示，如果公式無法用簡單的命題演算的形式來表示，那麼就不可能建立一台計算機在有窮步驟內來確定公式是否可證明。這是對希爾伯特觀點的又一個致命打擊，因為希爾伯特和他的支持者相信，應該存在一個最高階系統程序來決定所有的數學問題。最後，哥德爾補充説，圖靈的研究結果表明，“人類的思維永遠無法被機器所取代”——這是我將在本書第十一章中説到的有趣觀點。
就在圖靈準備把他的手稿寄給一家期刊的編輯時，美國邏輯學家阿隆佐·丘奇（Alonzo Church）發表的論文的副本也送到了劍橋。丘奇比圖靈大幾歲，是普林斯頓大學數學系的一名年輕的土耳其人。20世紀20年代末，他在哥廷根大學與希爾伯特小組一起花了近6個月的時間進行研究。仔細閲讀丘奇著寫的由數學符號組成的簡單的兩頁論文，會發現其關於判定問題的研究成果與圖靈的研究內容基本一致。這可能是研究人員最不想遭遇的窘態之一。是的，丘奇的論文雖然沒有包含通用圖靈機和存儲程序的概念，但內容與圖靈的手稿有明顯的重合，根據學術規則，一旦有人率先發表了一個數學成果，除非其他人的論文有一些重要的不同或全新的見解，否則不得再次署名發表。幸虧有紐曼在圖靈身邊給他出謀劃策。紐曼很清楚，圖靈論文的意義遠不止狹隘地應用於解決判定問題。他仍然建議圖靈發表論文，甚至親自給倫敦數學學會的編輯寫信，聲明即使丘奇的成果發表在先，也不應阻止圖靈的作品在協會期刊上發表。和往常一樣，紐曼又一次佔了上風，圖靈的代表作於1936年年底正式發表。
丘奇的方法並沒有説服哥德爾，哥德爾發現了論文中有爭議的漏洞。丘奇關於無法構建決策機器的證明並不能讓人信服。哥德爾那個假想的帶有曲柄的機器就很形象。直言不諱是學者的典型特徵，哥德爾率直地告訴丘奇，他的技術方法“完全不能令人滿意”（丘奇在某封信件中提及）。但是當哥德爾讀到圖靈的論文時，他發現圖靈成功地彌補了丘奇的漏洞。哥德爾讚賞地寫道，圖靈的“機械可計算性的定義”是“最令人滿意的”，而且將事實“毫無爭議”地展現了出來。
圖靈的論文中也存在一些小錯誤。不過，相比整篇複雜的數學論文而言，這些小錯誤都是很淺顯的，主要是圖靈粗心大意所致。幾個月後，圖靈發表了一篇修訂版論文，但其中仍有一些小紕漏未被發現。第二次世界大戰後，圖靈在英國國家物理實驗室的年輕助手唐納德·戴維斯（Donald Davies）發現了這些錯誤——戴維斯稱之為“粗心的編程錯誤”。年輕的戴維斯天真地認為圖靈在聽到他所發現的錯誤時會很欣慰。戴維斯回憶道：“我跑去告訴他，當時我非常高興。”然而，圖靈生氣了。“他非常生氣，”戴維斯平靜地回憶説，“他憤怒地指出這些疏忽並不重要，本質上來説這結論是對的。”圖靈的家人很清楚圖靈的這個性格特點，他的母親指出：“真正讓圖靈生氣的是與他在科學觀點上的矛盾。”有時他不得不離開房間，來擺脱糟糕的壞心情。
論文發表後，圖靈是時候展翅高飛了。他選擇前往數學和科學蓬勃發展的新國度——美國。從1935年起，圖靈就一直想去普林斯頓大學訪學，現在他知道了丘奇的存在，去那裏就顯得更有意義了。普林斯頓大學位於新澤西州南部不斷蔓延的城市邊緣，有着新哥特式的石頭建築和四合院，就像一個夢幻般的綠洲，是這個地球上最偉大的數學家居住的“温室世界”。圖靈馬上就有機會能夠與丘奇一起合作進行數學研究了。丘奇很瞭解圖靈，後來也是他率先使用“圖靈機”一詞來指代圖靈的發明成果的。圖靈收拾好行囊，離開了與世無爭的劍橋。
本文經授權節選自《圖靈傳：智能時代的拓荒者》（中信出版社，2022年10月版），圖片為編輯所加。
