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