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