哥德尔90年前的「不完备性定理」，奠定了计算机与AI的理论基础

本文来自微信公众号“机器之心”（ID:almosthuman2014），编辑：蛋酱、小舟，36氪经授权发布。

大神早已远去，而他的光芒仍在人间。

1931 年，奥地利裔美国著名数学家库尔特 · 哥德尔（Kurt Gödel）在一篇论文《Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme》中正式发表了不完备性定理。

这一理论使数学基础研究发生了划时代的变化，更是现代逻辑史上的重要里程碑。该定理与塔尔斯基的形式语言和真理论，图灵机和判定问题，一同被赞誉为现代逻辑科学在哲学方面的三大成果。

1951 年，哥德尔获得爱因斯坦勋章，冯 · 诺依曼评价说：「在现代逻辑中的成就是非凡的、不朽的——他的不朽甚至超过了纪念碑，他是一个里程碑，是永存的纪念碑。」

1978 年，哥德尔在美国普林斯顿市去世，享年 71 岁。死亡报告显示，哥德尔死于「因人格障碍导致的营养不良」。

今年是哥德尔不完备性定理发表的 90 周年，为此，Jürgen Schmidhuber 特别发文纪念哥德尔及其卓越的理论贡献。

「在 2021 年，庆祝哥德尔 1931 年开创性的论文发表 90 周年。这篇论文奠定了理论计算机科学和人工智能理论的基础，展示了定理证明、计算、人工智能、逻辑和数学本身的基础局限性，在学术界引起了轰动。这一研究对 20 世纪科学和哲学发展产生了巨大影响。」

库尔特 · 哥德尔被称为现代理论计算机科学和人工智能理论之父，曾被美国《时代周刊》评为 20 世纪最具影响力的 100 位人物之一。

不完备性定理发表于论文《Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme》。

在 1931 年的那项研究中，哥德尔引入了一种通用语言来编码任意形式化的过程。他使用基于素数因数分解的哥德尔编码系统。他首先把唯一的自然数指派到在他所处理的算术的形式语言中的每个基本符号。

哥德尔证明了，任何一个形式系统，只要包括了简单的初等数论描述，而且是自洽的，它必定包含某些系统内所允许的方法既不能证明真也不能证伪的命题。

同时，他证明了算法定理证明、计算和任何类型的基于计算的 AI 都具有基础局限性（有些人误解了他的结果，认为他证明的是人类优于 AI）。1940 年代至 70 年代的大部分 AI 和定理证明有关，并且都是以哥德尔范式进行推论的，包括专家系统和逻辑编程。

1935 年，阿隆佐 · 丘齐（Alonzo Church）通过证明 Hilbert & Ackermann 著名的 Entscheidungsproblem（判定问题）没有一般解决方案，推导出哥德尔结果的推论 / 扩展。丘齐使用了叫做 Untyped Lambda Calculus 的通用编码语言，这门语言构成了极具影响力的编程语言 LISP 的基础。

1936 年，阿兰 · 图灵引入了另一个通用模型「图灵机」，至少在计算机领域，它是最著名的模型之一。图灵重新推导了上述结果。当然，他在 1936 年的论文中同时引用了哥德尔和丘奇。

阿兰 · 图灵

同年，Emil Post 发表了另一个独立的通用计算模型，也引用了哥德尔和 Church 的研究。正是图灵的工作 (1936) 使哥德尔相信他自己的方法 (1931-34) 和丘齐 (1935) 的方法具备普遍性。

理论计算机科学领域的「哥德尔奖」就是以哥德尔的名字命名的。奖金更高的图灵奖创建于 1966 年，以表彰那些「对计算机领域具有长久和重大的技术贡献」。有趣但同时也令人尴尬的是，哥德尔 (1906-1978) 本人从未获得过一个奖项，且不提他奠定了现代理论计算机科学领域的基础，而且哥德尔还在他写给约翰 · 冯 · 诺依曼的著名信件中（1956 年）确定了最著名的开放问题「P= NP？」。

应该提到的是，实际应用中的「人工智能」比哥德尔对人工智能基本局限性的理论分析要古老得多。1914 年，西班牙人 Leonardo Torres y Quevedo 是 20 世纪第一个应用 AI 的先驱，当时他构建了第一个可工作的国际象棋终局棋手。

几十年后，当人工智能先驱 Norbert Wiener 在 1951 年巴黎会议上与它对弈时，这台机器依然给人们留下了深刻的印象，1951 年巴黎会议通常被视为第一个关于人工智能的会议，尽管 1956 年「人工智能」这个词才在达特茅斯（Dartmouth）学会上提出。而在 1951 年，现在被称为人工智能的大部分内容仍然被称为控制论，其重点与现代基于深度神经网络的人工智能非常一致。

同样值得一提的是，实用「计算机」科学比哥德尔的理论计算机科学基础要古老得多。也许世界上第一台可以实际应用的可编程机器是公元 1 世纪制造的自动化剧场。其中可编程自动机的能源是一个落锤，拉动缠绕在旋转圆柱体上的绳子。控制门和木偶的复杂指令序列由复杂的包装进行编码。

公元 9 世纪，班努 · 穆萨兄弟发明了一种可以自动演奏乐曲的乐器，它使用旋转圆柱体上的销钉存储控制蒸汽驱动长笛的程序。从本质上说，这正是一台可以编程的机器，并且带有存储程序。

大约 1800 年，Joseph-Marie Jacquard 等人在法国建造了第一台商用程序控制机器，即基于打孔卡的织机，也许他们算是编写世界上第一个工业软件的第一批「现代」程序员。

这种机器设计思想启发了 Ada Lovelace 和她的导师 Charles Babbage，当时他们计划但却无法构建十进制的可编程通用计算机。1941 年 Zuse 制造出世界上第一台能编程的计算机 Z3，而在 1944 年，Howard Aiken 构建了第一个通用可编程机器十进制的马克一号（MARK I）。

马克一号（右面部分）

哥德尔经常被称为亚里士多德以来最伟大的逻辑学家。《时代》杂志曾将他列为 20 世纪最有影响力的数学家，尽管一些数学家认为他最重要的研究成果在于逻辑和计算，而不是数学。有些人称哥德尔的理论是理论计算机科学的基础，后来理论计算机科学成为一个专门的学科。哥德尔的理论和思想激励了一代又一代的年轻人学习计算机科学。

在不到一个世纪的时间里，曾经只存在于伟人脑海中的东西，如今已成为现代社会不可忽视的存在，这些科学家理应获得更多的鲜花和掌声。

参考链接

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