哥德尔：计算机科学和AI理论之父

Schmidhuber 返朴

点击上方蓝字“返朴”进入主页，可关注查阅往期文章

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