哥德尔：计算机科学和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