2021年，我们将庆祝库尔特·G·德尔1931年发表开创性论文90周年，该论文奠定了理论计算机科学和人工智能理论的基础。G del澄清了定理证明、计算、人工智能、逻辑和数学的基本局限性，在学术界引起轰动。这对20世纪的科学和哲学产生了巨大的影响。距离2031年哥德尔纸业百年华诞还有十年！

作者|于尔根·施密德胡贝尔

译者|李媛媛

20世纪30年代初，库尔特·哥德尔阐述了计算数学的基础和极限、计算定理的证明和一般逻辑。因此，他成为现代理论、计算机科学和人工智能理论之父。

G del引入了一种通用语言来编码任何形式的过程。它基于整数，允许任何数字计算机的操作以公理的形式形式化。哥德尔用他所谓的哥德尔数来表示数据和程序。

G del最著名的是他对形式系统的阐述，包括形式系统的计算——给出了一个计算定理的证明，它系统地从一组可枚举的公理中列举了所有可能的定理，但在陈述自引用时将是不可解的。

因此，他确定了算法定理证明、计算以及基于计算的任何类型AI的基本局限性。20世纪40年代至70年代初的人工智能主要是通过专家系统和逻辑程序设计进行定理证明和广义演绎。

像大多数伟大的科学家一样，哥德尔的工作是基于他早期的工作。

他将格奥尔格·坎特的对角化技巧与戈特洛布·弗雷格、苏拉夫·斯科勒姆和雅克·埃尔布朗的基础作品相结合。

这些作者是基于戈特弗里德·威廉·莱布尼茨的思想代数，这相当于后来的布尔代数在1847年。莱布尼茨是“计算机科学之父”候选人之一，被称为“世界上第一位计算机科学家”，甚至是“有史以来最聪明的人”。

他描述了由穿孔卡片控制的二进制计算机的原理。1673年，他设计了第一个可以执行所有四种算术的物理硬件，超过了威廉·席卡德和布莱士·帕斯卡的第一个基于齿轮的自动数据处理计算器。

莱布尼茨不仅是第一个发表微积分的人，而且还进行了一个雄心勃勃的项目，通过计算来回答所有可能的问题。他关于一般语言和一般推理演算的思想非常有影响力。

莱布尼茨曾经有过这样一段重要的描述:“如果有争执，两个哲学家之间没有必要争论，但就像两个会计师之间一样，手里拿着铅笔坐下来，拿着他们的石板对对方说:我们来算算就够了！”然而，在1931年，G . del表明，用这种方法判断或计算什么是有基本限制的。

1935年，阿隆佐·邱奇通过证明希尔伯特和阿克曼著名的Entscheidungs问题没有通解，推导出了哥德尔结果的推广。出于这个原因，他使用了一种替代的通用编码语言，名为非类型化Lambda演算，这构成了有影响力的编程语言LISP的基础。

1936年，艾伦·图灵引入了另一个通用模型:图灵机，它可能会成为最著名的模型之一。他又推导出了上面的结果。当然，在他1937年的论文中，他引用了哥德尔和丘奇的方法。1936年，埃米尔·波斯特发表了另一个独立的通用计算模型，其中也引用了哥德尔和丘奇的方法。今天我们知道很多这样的模型。按照王的说法，正是图灵的工作让哥德尔相信了他自己的方法和丘奇的方法的普遍性。

波斯特和图灵在1936年做了什么是哥德尔和丘奇没有做的？有一个看似很小的区别，它的重要性后来才被发现。

G del的许多指令序列是数字编码存储内容和整数的一系列乘法。G del不在乎这个乘法的计算复杂度会随着存储大小的增加而增加。同样，丘奇在他的算法中忽略了基本指令的时间空复杂度。

然而，图灵和波斯特采用了传统和简化的二进制计算观点——就像康拉德·楚泽一样。他们的机器模型只允许非常简单的基本指令，复杂度不变，就像莱布尼茨早期的二进制机器模型一样。

埃米尔·波斯特当时并没有利用这一点——例如，图灵在1936年使用他的模型只是为了重申G del和Church关于极限的结果的可计算性。然而，后来，这些机器的简单性使它们成为研究复杂性理论的方便工具。

哥德尔理论计算机科学奖以哥德尔命名。目前，利润更丰厚的美国计算机学会图灵奖设立于1966年，旨在表彰“对计算机领域具有持久和重大技术重要性”的贡献。

有趣的是——同时也令人尴尬的是——G Del从未获得过这一奖项的认可，尽管他不仅为这一领域的“现代”版本奠定了基础，还确定了他最著名的开放性问题“P=NP？”在他给约翰·冯·诺依曼的那封著名的信中。

哥德尔、丘奇、图灵和波斯特的形式模型都是理论结构，不能直接作为实际计算机的基础。

值得注意的是，康拉德·楚泽第一台实用通用程控计算机的专利申请也可以追溯到1936年。它描述了一个通用的数字电路。

然后，在1941年，Zuse完成了Z3，这是世界上第一台实用和可操作的可编程计算机。忽略了任何物理计算机不可避免的存储限制，Z3的物理硬件确实在G del、Church的“现代”意义上是通用的，图灵和Post-simple算术技巧可以弥补Z3缺乏显式条件跳转指令的不足。Zuse还在20世纪40年代初创造了第一种高级编程语言。他于1945年将其应用于国际象棋，并于1948年应用于定理证明。

值得一提的是，实用人工智能比G del对人工智能基本局限性的理论分析要古老得多。

1914年，西班牙人莱昂纳多·托雷斯是20世纪第一个实用人工智能的先驱，当时他建造了第一个工作的国际象棋选手。

几十年后，当人工智能先驱诺伯特·维纳1951年在1951年的巴黎会议上面对它时，这台机器仍然被认为是令人印象深刻的。现在它通常被认为是第一次关于人工智能的会议——尽管“人工智能”是由约翰·麦卡锡在1956年末达特茅斯的另一次会议上提出的。其实在1951年，现在所谓的人工智能大部分还是叫控制论，它的侧重点与基于深度神经网络的现代人工智能非常一致。

同样，实用计算机科学比G del的理论计算机科学基础要古老得多。

也许世界上第一台实用的可编程机器是1世纪亚历山大的海伦制造的自动剧场。

他的可编程自动机的能量来源是一个落下的锤子，拉动缠绕在旋转圆柱销上的绳子。控制门和木偶几分钟的复杂指令序列由复杂的包编码。巴努·穆萨兄弟在9世纪发明的音乐自动机可能是第一台带有存储程序的机器。与2006年Al-Jazari的可编程鼓机相比，它使用旋转气缸上的销来存储控制蒸汽驱动长笛的程序。

1800年左右，约瑟夫-玛丽·贾卡等人在法国制造了第一台商用程控机器，他们可能是第一批编写世界上第一个工业软件的“现代”程序员。他们启发了阿达·洛芙莱斯和她的导师查尔斯·巴贝奇，他们计划但不能建立一个非二进制，十进制和可编程的通用计算机。第一台由Zuse以外的人制造的通用可编程机器是霍华德·艾肯的十进制Mark I。

哥德尔常被称为自亚里士多德以来最伟大的逻辑学家。上世纪末，《时代》杂志将他列为20世纪最具影响力的数学家，尽管有数学家说他最重要的成就是关于逻辑和计算，而不是数学。还有人认为，他的成果是理论计算机科学的基础，这在当时还没有正式存在，但正是通过G del的努力才产生的。普利策奖获奖畅销书《哥德尔、埃舍尔、巴赫》激励了一代又一代年轻人学习计算机科学。

2021年，我们不仅要庆祝GDEL 1931年发表著名论文90周年，还要庆祝Zuse研制出世界上第一台功能性通用程控计算机80周年。令人难以置信的是，在不到一个世纪的时间里，曾经只存在于巨人头脑中的东西，已经成为现代社会不可分割的一部分。世界欠这些科学家一大笔债。

距离2031年G del论文的生日还有10年，距离2041年Zuse电脑百年还有20年！有足够的时间来计划合适的庆祝活动。

参考

https://people . idsia . ch/~ juergen/goedel-1931-创始人-理论-计算机-科学-AI.html

本文转载自微信官方账号中的微信“数据实践派”，原标题为“LSTM之父撰文，纪念本次图灵奖，“AI理论之父”。理论计算机科学的创始人库尔特·g·德尔展示了数学、逻辑、计算和人工智能的极限