懟王講歷史：圖靈被過譽，哥德爾和丘奇才是計算機科學之父

本文作者：我在思考中

2021-09-22 11:32

導語：今年，Jürgen Schmidhuber不再將矛頭指向圖靈獎的公正性，而是直接指向圖靈獎的創(chuàng)始人——艾倫·圖靈。

Jürgen Schmidhuber

編譯 | 吳彤

編輯 | 陳大鑫

作為科技界“公正處”的編外人員，Jürgen Schmidhuber（約爾根·施密杜伯）常年以個人博客為主陣地，對科技界新聞躬身評審，撰寫了超過350篇同行評審論文。作為一位經常發(fā)表主旨演講的人，他還長期就人工智能戰(zhàn)略為各國政府提供建議。

在9月14日，他終于完成一年半之前的約稿，在個人博客上又發(fā)新作：艾倫·圖靈（Alan Mathison Turing) 被過譽。

懟王講歷史：圖靈被過譽，哥德爾和丘奇才是計算機科學之父博文截圖

長期以來，Jürgen Schmidhuber 都像一個精力充沛的戰(zhàn)士，矛頭直指科技界當紅小生，曾與 Ian Goodfellow 爭辯 GAN 的歸屬、還在ACM 將圖靈獎授予「深度學習三巨頭」后，極力肯定和推廣LSTM在人工神經網絡和深度學習領域的巨大作用，引用 200 多條文獻逐條反駁「三巨頭」的不該獲獎。直到去年的IEEE 2021上，神經網絡先驅獎被授予 LSTM 提出者 Sepp Hochreiter，長達近兩年的 LSTM爭論終獲正名，科技界“抬杠選手” Schmidhuber 的指正也獲得迂回性的勝利。

注：圖靈獎（Turing Award），全稱A.M.圖靈獎（A.M Turing Award），是由美國計算機協(xié)會（ACM，）于1966年設立的計算機獎項，名稱取自艾倫·麥席森·圖靈（1912年－1954年），旨在獎勵對計算機事業(yè)作出重要貢獻的個人。圖靈獎對獲獎條件要求極高，評獎程序極嚴，一般每年僅授予一名計算機科學家。圖靈獎是計算機領域的國際最高獎項，被譽為"計算機界的諾貝爾獎"。

正因為帶有種種爭議和故事，Jürgen Schmidhuber 的動態(tài)更加引入關注。

今年，Jürgen Schmidhuber不再將矛頭指向圖靈獎的公正性，而是直接指向圖靈獎的創(chuàng)始人——艾倫·圖靈（以下簡稱圖靈）：

長期以來，圖靈確實對計算機科學做出了某些重大貢獻，然而，這一領域的先驅們的貢獻常常被忽視，圖靈的個人價值卻經常被過分夸大。盡管這并不是圖靈的錯，但我們需要停止以犧牲先輩為代價而過度夸大單個科學家的貢獻。尋找和引用科技創(chuàng)新的原始來源相當重要。在新作中，Jürgen Schmidhuber引用了97條參考文獻，并直言：本文是為有同樣見解的計算機科學家提供的資源。

同時，《Nature》雜志也在呼吁："要重視那些修正科學的人"。

在新作中，Jürgen Schmidhuber重點討論了計算機科學的基本概念，以及哥德爾、祖斯、萊布尼茨先驅們研究的個中關系。他們的研究有時被錯誤地認為是英國數(shù)學家圖靈的發(fā)明，尤其是在英語圈（以英語為母語的人）。

AI科技評論對其博文進行了不改變原意的整理，以下為具體內容。

矛盾點：并不完全錯誤，但極具誤導性

有人聲稱圖靈創(chuàng)立了計算機科學，就連同行評議的英國《Nature》雜志此前也發(fā)表過夸大其詞的言論，比如：圖靈1936年的論文為未來所有計算機提供了"理論支柱"。事實并非如此。

一部受歡迎的英國電影《模仿游戲》甚至說他發(fā)明了電腦。他沒有。（電影改編自安德魯·霍奇斯編著的《艾倫·圖靈傳》。二戰(zhàn)期間，盟軍苦于德國的秘密系統(tǒng)"英格瑪"無法破譯，政府召集了一批民間數(shù)學家、邏輯學家進行秘密破解工作，圖靈就是其中之一）

一位著名的歷史學家寫道："我可以寫很多專欄，只不過是歪曲關于圖靈的荒謬文章，但大多數(shù)應該是由更了解的人寫的。"其中ACM對2018年對圖靈獎的官方解釋是， "圖靈獎是以英國數(shù)學家艾倫·M·圖靈(Alan M. Turing)的名字命名的，他闡明了計算的數(shù)學基礎和局限性?！?/span>

盡管ACM關于圖靈的聲明并不是完全錯誤的，但它極具誤導性，就像它的其他一些聲明一樣。ACM說圖靈"闡明了計算的數(shù)學基礎和極限" ，然而，幾十年來許多人已經這樣做了。當科學蓋棺定論時，重要的問題是誰先做的？

圖靈在奧地利數(shù)學家?guī)鞝柼亍じ绲聽?( Kurt G?del ) 開創(chuàng)性工作的五年后，以及圖靈的博士導師美國人阿隆佐·丘奇（ Alonzo Church）一年后發(fā)表了論文。當然，他在1936年的論文(其更正在1937年發(fā)表)中引用了這兩篇文章。帶著這一點，讓我們更仔細地看看現(xiàn)代計算機科學的誕生。

哥德爾的工作 (1906-1978)

20世紀30年代初（1931年），哥德爾成為現(xiàn)代計算機理論科學的奠基人。他引入了一種基于整數(shù)的通用編碼語言。它允許以公理的形式形式化任何數(shù)字計算機的操作。哥德爾用它來表示數(shù)據(如公理和定理)和程序 (如數(shù)據操作的證明生成序列)。他構建了一個著名的形式命題，討論了其他形式命題的計算，特別是自指式命題，這意味著它們是不可判定的，給出了一個計算定理證明，系統(tǒng)地從一組可列舉的公理中列舉出所有可能的定理。因此，他確定了算法定理證明、計算和任何基于計算的人工智能的基本極限。

哥德爾

20世紀40 -70年代早期的人工智能實際上是關于定理證明和通過專家系統(tǒng)和邏輯編程的哥德爾風格的演繹。

哥德爾建立在Gottlob Frege（在1879年他引入了第一個形式語言)、Georg Cantor(1891年，對角化技巧)、Thoralf Skolem(1923年他引入了原始遞歸函數(shù))和Jacques Herbrand(他發(fā)現(xiàn)了Skolem方法的局限性)的早期工作的基礎上。這些作者是建立在萊布尼茨（Gottfried Wilhelm Leibniz）的形式代數(shù)思想(1686)的基礎上，它與后來1847年的布爾代數(shù)是演繹等價的。

萊布尼茨（Gottfried Wilhelm Leibniz）是“計算機科學之父”的候選人之一，他被稱為“世界上第一位計算機科學家”，甚至被稱為“有史以來最聰明的人”。他不僅是第一個發(fā)表無限小微積分(1684)的人，也是第一個描述穿孔卡片控制的二進制計算機原理(1679)的人。(二進制編碼本身要比這古老得多，可以追溯到古埃及。二進制運算的算法部分是相對較新的。比較Juan Caramuel y Lobkowitz發(fā)表的二進制編碼(1670)和Thomas Harriott未發(fā)表的論文)

此外，萊布尼茨追求一個雄心勃勃且極具影響力的項目，通過一種通用語言和用于推理的一般演算來回答所有可能的問題:《普遍性特征與微積分推理者》 (靈感來自13世紀的學者Ramon Llull)。然而，在20世紀30年代早期，哥德爾的著名結果顯示了萊布尼茨計劃的局限性。

丘奇的工作 (1903–1995)

1935年，丘奇（Church）證明了希爾伯特和阿克曼（Hilbert & Ackermann）的決策問題沒有通解，從而導出了哥德爾結果的一個推論。為了做到這一點，他使用了另一種通用編碼語言，稱為非類型Lambda微積分（Untyped Lambda Calculus），它構成了極具影響力的編程語言LISP的基礎。

丘奇

1936年，圖靈引入了另一個通用模型，這可能是其中最著名的一個(至少在計算機科學領域): 圖靈機。他重新推導了上述結果。當然，他在1936年的論文中同時引用了哥德爾和丘奇。

同年，波斯特（Emil Post）發(fā)表了另一個獨立的通用計算模型，也引用了哥德爾和丘奇。丘奇證明了他的模型與哥德爾的模型具有同樣的表達能力。然而，據美籍華裔數(shù)學家、邏輯學家、哲學家王浩說，是圖靈的工作(1936)使哥德爾相信了自己（1931）和丘奇(1935)方法的普適性。

就像哥德爾在1931- 1934年發(fā)明的最初的通用語言一樣，圖靈機和1936年發(fā)明的波斯特機器都是理論的、不切實際的結構，不能直接作為現(xiàn)實世界計算機的基礎。值得注意的是，康拉德·祖斯為第一臺實用的通用程序控制計算機申請的專利也可以追溯到1936年。

圖靈究竟做了什么

圖靈和波斯特在1936年究竟做了什么，是哥德爾(1931)和丘奇(1935)沒有做過的?

有一個看似微小的差異，但其重要性后來才顯現(xiàn)出來：哥德爾的許多指令序列都是數(shù)字編碼的存儲內容的整數(shù)乘法，但他并不關心這種乘法的計算復雜度會隨著存儲空間的增大而增加。同樣，丘奇也忽略了他的算法中基本指令的上下文依賴性時空復雜性。

然而，圖靈和波斯特采用了傳統(tǒng)的、簡化主義的、極簡主義的二進制的計算觀點。他們的機器模型只允許非常簡單、復雜度不變的基本二進制指令，比如萊布尼茨(1679)的早期二進制機器模型和祖斯1936年的專利申請。他們并沒有利用這一點——圖靈只是用他的(相當?shù)托У?模型來重新表述哥德爾和丘奇關于可計算極限的結果。然而，后來，這些機器的簡單性使它們成為復雜性理論研究的方便工具。(我也很高興在無窮無盡的計算中使用并推廣了它們）

祖斯

有世人稱，圖靈至少為人工智能奠定了基礎。這有什么意義嗎?

1948年，圖靈寫下了與人工進化和學習人工神經網絡有關的想法，其架構至少少可以追溯到1943年(參見自20世紀20年代以來與之密切相關的物理學工作)。圖靈沒有發(fā)表，這也解釋了為什么他的論文缺乏影響力。

1950年，他提出了一個簡單而著名的主觀測試，用來評估計算機是否智能。

1956年，在達特茅斯的一次會議上，約翰·麥卡錫（John McCarthy）創(chuàng)造了“人工智能”一詞，作為相關研究的新標簽。然而，第一次關于人工智能的會議早在1951年就在巴黎召開了，當時的人工智能仍被稱為控制論，重點是與基于深度神經網絡的現(xiàn)代人工智能非常一致。

但是早在1914年，西班牙人Leonardo Torres y Quevedo就已經成為20世紀第一個實用人工智能的先驅，他創(chuàng)造了第一個可以使用的象棋終局棋手(當時象棋被認為是一種僅限于智能生物領域的活動)。幾十年后，當人工智能先驅Norbert Wiener在1951年的巴黎會議上與它交手時，這臺機器仍大展拳腳。

然而，祖斯（Konrad Zuse）早在1945年就有了更通用的象棋套路。他也在1948年應用了他開創(chuàng)性的Plankalkül編程語言來證明定理，遠早于Newell和Simon 1956年的工作。通過專家系統(tǒng)自動證明和推導定理，為人工智能奠定了形式化的基礎(有些人錯誤地認為他也證明了人類優(yōu)于人工智能)。總之，人工智能的基礎性成就遠遠早于圖靈的成就。

奇怪的頒獎

哥德爾理論計算機科學獎以哥德爾命名，但目前獎金更加豐厚的ACM 的圖靈獎成立于1966年，以表彰“對計算機領域具有持久和重大技術重要性”的貢獻。有趣而尷尬的是，哥德爾(1906-1978)從未得到過一個，盡管他不僅為該領域的“現(xiàn)代”版本奠定了基礎，而且還在給約翰·馮·諾依曼(1956)的著名信中指出了該領域最著名的開放問題“P=NP?” 盡管這些先驅者在該獎項設立數(shù)年后就去世了，但中間還有12年的時間。

同樣，祖斯(1910-1995)也從未獲得過圖靈獎，盡管他在1935-1941年間創(chuàng)造了世界上第一臺可編程通用計算機。并且他在1936年的專利申請描述了可編程物理硬件所需的數(shù)字電路，這比香農在1937年關于數(shù)字電路設計的論文要早。

祖斯也在20世紀40年代早期創(chuàng)造了第一種高級程序設計語言，以及在1941年發(fā)明的Z3電腦。Z3不像哥德爾(1931)、丘奇(1935)、圖靈(1936)和波斯特(1936)那樣，只是一種理論上不切實際的紙筆結構，忽略任何物理計算機不可避免的存儲限制。它的物理硬件在上述理論的現(xiàn)代意義上確實是通用的——簡單的算術技巧可以彌補它缺乏一個顯式條件跳轉指令的類型 “IF…然后轉到地址…

順便說一下，圖靈的編程或波斯特的機器更尷尬，它們也不允許“現(xiàn)代的”條件跳轉——它們甚至沒有指令指針可以跳轉到的編號內存地址。

Z3 在計算硬件的歷史中處于什么位置?

已知的第一個基于齒輪的計算裝置是2000多年前古希臘的天球儀(一種天文鐘)。1500年后，彼得·亨萊因仍在制造概念上類似的機器——盡管更小——也就是第一個小型化懷表(1505年)。但這些設備總是計算相同的東西，例如，用分鐘除以60得到小時。

17世紀出現(xiàn)了更靈活的機器，可以根據輸入數(shù)據計算答案。1623年，威廉·?？ǖ?Wilhelm Schickard)建造了第一臺基于數(shù)據處理齒輪的簡單算術專用計算器，他是“自動計算之父”的候選人之一，緊隨其后的是Blaise Pascal（1642年）的高級Pascaline。

在1673年，上述不可避免的萊布尼茨設計了第一臺能執(zhí)行所有四種算術運算的機器(步數(shù)計算器)，而且第一臺有內存的機器。他還在1679年描述了二進制計算機的原理，幾乎是所有現(xiàn)代計算機的原理，包括Zuse的Z3。

Z3采用電磁繼電器，開關明顯移動。第一個電子專用計算器（其運動部件是太小而看不見的電子）是由John Atanasoff(“基于電子管的計算之父”)發(fā)明的二進制ABC(美國，1942年)。與17世紀以齒輪為基礎的機器不同，ABC使用的是電子管——今天的機器使用的是晶體管原理，由Julius E. Lilienfeld在1925年獲得專利。但是不像Z3, ABC不是自由編程的。湯米·弗勞爾斯(Tommy Flowers，英國，1943-45年)發(fā)明的用來破解納粹密碼的電子巨像機(NASC6)也不是。

另一方面，程序的概念當時已經眾所周知。也許世界上第一臺可編程機器是亞歷山大的赫倫(顯然他也有第一個已知的蒸汽機- Aeolipile) 在1世紀制造的自動劇院。他的可編程機器人的能量來源是一個下落的重物，拉著一根纏繞在旋轉圓筒銷上的繩子?？刂崎T和木偶幾分鐘的復雜指令序列由復雜的包裝編碼。

巴格達的巴努·穆薩兄弟(Banu Musa brothers)于9世紀發(fā)明的自動音樂裝置(music automaton)使用旋轉圓筒上的大頭針來存儲控制蒸汽驅動笛子的程序（與Al-Jazari公司的可編程鼓機1206相比）。

大約1800年，約瑟夫-瑪麗·雅卡爾等人在法國制造了第一臺商用程序控制機器(穿孔卡片織機)，他們也許是世界上第一個工業(yè)軟件的“現(xiàn)代”程序員。

在這種情況下，似乎有必要指出程序和上面提到的17世紀用戶提供的有限輸入數(shù)據之間的區(qū)別。程序是存儲在某些介質(如穿孔卡片上)上的指令序列，可以在不需要人工干預的情況下反復運行。隨著時間的推移，存儲程序所需的物理對象變得越來越輕。古老的機器將它們儲存在旋轉的圓筒上; 提花機把它們放在紙板上; 祖斯將它們儲存在35毫米膠片上，而今天我們通常使用電子和可磁化材料來儲存它們。

雅卡爾的程序(1800年左右)還不是通用型的，但它們啟發(fā)了Ada Lovelace和她的導師Charles Babbage (英國，大約1840年)。他計劃制造一種可編程的通用計算機，但未能成功(只有他的非通用專用計算器制造出了一個20世紀的復制品)。

與Babbage不同，祖斯(1936-1941)使用了萊布尼茨的二進制計算原理(1679)替代傳統(tǒng)的十進制計算。這大大簡化了硬件。除了祖斯之外，其他人制造的第一臺通用可編程機器是霍華德·艾肯(Howard Aiken)的，并仍然是十進制的MARK I(美國，1944年)。

Eckert和Mauchly(1945/1946)設計的更快的十進制ENIAC可以通過重新布線來編程。然而今天，大多數(shù)計算機都是像Z3那樣的二進制。

“"Manchester baby”(Williams, Kilburn & Tootill, 英國, 1948)和1948年升級的ENIAC都將數(shù)據和程序存儲在電子存儲器中，ENIAC通過將數(shù)字指令代碼輸入只讀存儲器進行了重新編程。然而，早在1936-38年，祖斯就可能是第一個建議將程序指令和數(shù)據都放入內存的人。有人指出，除了圖靈自己的ACE設計，20世紀40年代制造的計算機都沒有受到圖靈1936年理論論文的任何影響。

我們再次注意到，哥德爾1931 – 1934的形式模型將數(shù)據（例如公理）和程序（對數(shù)據的操作序列）以及結果（例如定理）編碼/存儲在相同的基于整數(shù)的存儲（現(xiàn)在稱為哥德爾編號）中，就像圖靈和波斯特后來將它們存儲在位字符串中一樣任何圖靈機、波斯特機或任何其他數(shù)字計算機都可以用哥德爾最初的通用模型形式化（這啟發(fā)了我的自我參照哥德爾機）。

然而，應該注意的是，我們在這里使用了現(xiàn)代術語：哥德爾（1931年）、丘奇（1935年）和圖靈（1936年）都沒有在他們的論文中提到"程序"這個術語（盡管祖斯1936年的專利申請經常提到"Rechenplan"，意思是"程序"）。術語“存儲程序”后來首次出現(xiàn)在電子存儲的語境中。

圖靈發(fā)表了生物信息學方面的開創(chuàng)性工作。然而，他最大的影響可能來自于他對破譯德國軍隊在第二次世界大戰(zhàn)期間使用的Enigma密碼的貢獻。他與 Gordon Welchman在英國Bletchley公園共事。然而，著名的密碼破譯巨像機是由 Tommy Flowers設計的。英國密碼學家建立在波蘭數(shù)學家Marian Rejewski、Jerzy Rozycki和Henryk Zygalski的基礎之上，他們是第一個破解Enigma密碼的人，他們在電影《模仿游戲》中甚至都沒有被提及。有人說這是打敗第三帝國的決定性因素。