哥德爾：計算機科學和AI理論之父_風聞

2021 年，我們將慶祝 Kurt Gödel 1931 年發表的開創性論文 90 週年紀念，該論文奠定了理論計算機科學和人工智能 (AI) 理論的基礎。Gödel 闡明瞭定理證明、計算、人工智能、邏輯和數學本身的基本侷限性，在學術界引起了轟動。這對 20 世紀的科學和哲學產生了巨大的影響。距離 2031 年 Gödel 論文百年還有十年！

撰文 | Jürgen Schmidhuber （知名 AI 學者，LSTM 之父）

譯者 | 劉媛媛

20 世紀 30 年代初期，Kurt Gödel 闡明瞭計算數學基礎和極限、計算定理證明和一般邏輯的。因此，他成為了現代理論計算機科學和人工智能理論之父。

Gödel 引入了一種通用語言來編碼任意形式化過程。它基於整數，並允許以公理形式對任何數字計算機的操作進行形式化。Gödel 使用他所謂的 Gödel 編號來表示數據（例如公理和定理）和程序（例如對數據進行的證明生成操作序列）。

Gödel 最著名的是對形式系統的闡述，其中包括形式系統的計算 —— 給定一個計算定理證明器，該證明器從一組可枚舉的公理中系統地枚舉所有可能的定理，但是當陳述自我指涉時它將是不可解的。

因此，他確定了算法定理證明、計算和任何類型的基於計算的 AI 的基本限制（有些人誤解了他的結果，認為他表明人類優於 AI）。20 世紀 40 年代至 70 年代早期的人工智能，大部分是關於定理證明以及通過專家系統和邏輯編程的 Gödel 式演繹。

像大多數偉大的科學家一樣，Gödel 的工作建立在早期工作的基礎之上。

他將 Georg Cantor 的對角化技巧與 Gottlob Frege、Thoralf Skolem 和 Jacques Herbrand 的基礎工作相結合。

這些作者又以 Gottfried Wilhelm Leibniz 的《思想的代數》(1686) 為基礎，《思想的代數》在演繹上等同於後來的《1847 年布爾代數》。Leibniz 是 “計算機科學之父” 的候選人之一，被稱為 “世界上第一個計算機科學家”，甚至是 “有史以來最聰明的人”。

他描述了由穿孔卡片控制的二進制計算機的原理 (1679 年)。1673 年，他設計了第一個可以執行所有四種算術的物理硬件（步進計算器），超越了 Wilhelm Schickard (1623) 和 Blaise Pascal (1642) 的第一個基於齒輪的自動數據處理計算器。

Leibniz 不僅是發表微積分的第一人，而且還進行了一個雄心勃勃的項目，通過計算來回答所有可能的問題。他關於通用語言和推理的通用微積分的想法極具影響力（《通用的特性和演算推理者》靈感來自 13 世紀的學者 Ramon Llull）。

Leibniz 曾有這樣一段重要描述：“如果出現爭議，兩個哲學家之間就不需要爭論，而是像兩個會計師之間一樣，手裏拿着鉛筆，坐下來就足夠了，用他們的石板互相説：讓我們計算一下！” 然而，在 1931 年，Gödel 表明，以這種方式可判定或可計算的東西存在根本的侷限性。

1935 年，Alonzo Church 通過證明 Hilbert 和 Ackermann 著名的 Entscheidungs problem（決策問題）沒有通用解決方案，推導出 Gödel 結果的擴展。為此，他使用了名為 Untyped Lambda Calculus 的替代通用編碼語言，該語言構成了極具影響力的編程語言 LISP 的基礎。

1936 年，Alan Turing 引入了另一個通用模型：圖靈機，該模型可能成為其中最著名的模型（至少在計算機科學領域）。他重新推導出了上述結果。當然，他在 1937 年的論文中同時引用了 Gödel 和 Church 的方法。1936 年，Emil Post 發表了另一個獨立的通用計算模型，同時也引用了 Gödel 和 Church 的方法。今天我們知道很多這樣的模型。根據 Wang 的説法，正是圖靈的工作（1936）使 Gödel 相信他自己的方法（1931-34）和 Church（1935）的方法的普遍性。

Post 和 Turing 在 1936 年究竟做了哪些 Gödel（1931-34）和 Church（1935）沒有做過的事情？有一個看似微小的差異，其重要性後來才顯現出來。

Gödel 的許多指令序列是數字編碼存儲內容與整數的一系列乘法。Gödel 並不關心這種乘法的計算複雜度會隨着存儲大小的增加而增加。同樣，Church 在他的算法中也忽略了基本指令的時空複雜性。

然而，Turing 和 Post 採用了傳統的、簡化的二進制的計算觀點 —— 就像 Konrad Zuse (1936) 一樣。他們的機器模型只允許非常簡單的具有恆定複雜性的基本指令，就像 Leibniz 早期的二進制機器模型 (1679)。

Emil Post 他們當時並沒有利用這一點 —— 例如，1936 年，Turing 使用他的（相當低效的）模型只是為了重新表述 Gödel 和 Church 在極限上的結果可計算性。然而，後來，這些機器的簡單性使它們成為複雜性理論研究的便利工具（他也很高興地將它們用於永無止境的計算）。

哥德爾理論計算機科學獎以 Gödel 命名。目前獎金更豐厚的美國計算機學會圖靈獎創建於 1966 年，以表彰 “對計算機領域具有持久和重大技術重要性” 的貢獻。

有趣的是 —— 同時也令人尷尬的是 ——Gödel (1906-1978) 從未得到過該獎項的認可，儘管他不僅奠定了該領域 “現代” 版本的基礎，而且在他寫給 John von Neumann 的著名信件中 (1956) ，還確定了其最著名的開放問題 “P=NP？” 。

Gödel (1931-34)、Church (1935)、Turing (1936) 和 Post (1936) 的正式模型是理論結構，不能直接作為實用計算機的基礎。

值得注意的是，Konrad Zuse 的第一台實用通用程控計算機的專利申請也可以追溯到 1936 年。它描述了通用數字電路（並且早於 Claude Shannon 1937 年關於數字電路設計的論文）。

然後，在 1941 年，Zuse 完成了 Z3，這是世界上第一台實用、可運行的可編程計算機（基於 1936 年的應用程序）。忽略任何物理計算機不可避免的存儲限制，Z3 的物理硬件確實是 Gödel、Church、Turing 和 Post 的 “現代” 意義上的通用 —— 簡單的算術技巧可以彌補 Z3 缺乏明確的條件跳轉指令。Zuse 還在 20 世紀 40 年代初期創建了第一個高級編程語言 (Plankalkül)。他於 1945 年將其應用於國際象棋，並於 1948 年應用於定理證明。

值得一提的是，實用人工智能比 Gödel 對人工智能基本侷限性的理論分析要古老得多。

1914 年，西班牙人 Leonardo Torres y Quevedo 是 20 世紀第一個實用 AI 的先驅，當時他建造了第一個可工作的國際象棋終局棋手（當時國際象棋被認為是一種僅限於智能生物領域的活動）。

幾十年後，當 AI 先驅 Norbert Wiener1951 年在巴黎會議上與它對抗時，這台機器仍然被認為令人印象深刻。現在通常被視為第一個關於人工智能的會議 —— 儘管 “AI” 是在 1956 年晚些時候由約翰麥卡錫在達特茅斯的另一次會議上提出的。事實上，在 1951 年，現在稱為人工智能的大部分內容仍然被稱為控制論，其重點非常符合基於深度神經網絡的現代人工智能。

同樣，實用計算機科學比 Gödel 的理論計算機科學基礎要古老得多（比較上面對 Leibniz 的評論）。

也許世界上第一台實用的可編程機器是 1 世紀由 Alexandria 的 Heron 製造的 automatic theatre （他顯然也擁有第一個已知的工作蒸汽機 ——Aeolipile）。

他的可編程自動機的能量來源，是一個落錘拉動纏繞在旋轉圓柱體銷上的繩子。控制門和木偶幾分鐘的複雜指令序列由複雜的包裝編碼。9 世紀由 Banu Musa brothers 發明的音樂自動機可能是第一台帶有存儲程序的機器。對比 206 年 Al-Jazari 的可編程的鼓機，它使用旋轉圓柱上的銷釘來存儲控制蒸汽驅動長笛的程序。

第一台商用程控機器（基於打孔卡的織機），是由 Joseph-Marie Jacquard 等人於 1800 年左右在法國建造的 —— 他們也許是第一批編寫世界上第一個工業軟件的 “現代” 程序員。他們啓發了 Ada Lovelace 和她的導師 Charles Babbage（英國，大約 1840 年），他們計劃但無法構建非二進制、十進制、可編程的通用計算機。由 Zuse (1941) 以外的其他人制造的第一台通用可編程機器是 Howard Aiken 的十進制 MARK I（美國，1944）。

Gödel 經常被稱為繼 Aristotle 以來最偉大的邏輯學家。在上個世紀末，時代雜誌將他列為 20 世紀最有影響力的數學家，儘管一些數學家説他最重要的成果是關於邏輯和計算， 不是數學。還有一些人認為他的成果是理論計算機科學的基礎，該學科當時尚未正式存在，但正是通過 Gödel 的努力得以產生。獲得過普利策獎的暢銷書《Gödel, Escher, Bach》，激勵了幾代年輕人學習計算機科學。

2021 年，我們不僅要慶祝 Gödel 1931 年著名論文發表 90 週年，還要慶祝 Zuse（1941 年）研製出世界上第一台功能性通用程控計算機 80 週年。令人難以置信的是，在不到一個世紀的時間裏，曾經只存在於巨擘頭腦中的東西已成為現代社會不可分割的東西。世界欠這些科學家一大筆債。

距離 2031 年 Gödel 論文誕辰還有 10 年，距離 2041 年 Zuse 計算機百年還有 20 年！有足夠的時間來計劃合適的慶祝活動。

參考文獻

[1] https://people.idsia.ch/~juergen/goedel-1931-founder-theoretical-computer-science-AI.html

本文轉載自微信公眾號“數據實戰派”，原標題為《LSTM之父撰文，紀念這位圖靈獎遺珠、“AI理論之父”》。原文：1931: Kurt Gödel, founder of theoretical computer science, shows limits of math, logic, computing, and artificial intelligence