年，我们将庆祝KurtG?del年发表的开创性论文90周年纪念，该论文奠定了理论计算机科学和人工智能(AI)理论的基础。G?del阐明了定理证明、计算、人工智能、逻辑和数学本身的基本局限性，在学术界引起了轰动。这对20世纪的科学和哲学产生了巨大的影响。距离年G?del百年诞辰还有十年！
撰文
JürgenSchmidhuber（知名AI学者，LSTM之父）
译者
刘媛媛
20世纪30年代初期，KurtG?del阐明了计算数学基础和极限、计算定理证明和一般逻辑的。因此，他成为了现代理论计算机科学和人工智能理论之父。
G?del引入了一种通用语言来编码任意形式化过程。它基于整数，并允许以公理形式对任何数字计算机的操作进行形式化。G?del使用他所谓的G?del编号来表示数据（例如公理和定理）和程序（例如对数据进行的证明生成操作序列）。
G?del最著名的是对形式系统的阐述，其中包括形式系统的计算——给定一个计算定理证明器，该证明器从一组可枚举的公理中系统地枚举所有可能的定理，但是当陈述自我指涉时它将是不可解的。
因此，他确定了算法定理证明、计算和任何类型的基于计算的AI的基本限制（有些人误解了他的结果，认为他表明人类优于AI）。20世纪40年代至70年代早期的人工智能，大部分是关于定理证明以及通过专家系统和逻辑编程的G?del式演绎。
像大多数伟大的科学家一样，G?del的工作建立在早期工作的基础之上。
他将GeorgCantor的对角化技巧与GottlobFrege、ThoralfSkolem和JacquesHerbrand的基础工作相结合。
这些作者又以GottfriedWilhelmLeibniz的《思想的代数》()为基础，《思想的代数》在演绎上等同于后来的《年布尔代数》。Leibniz是“计算机科学之父”的候选人之一，被称为“世界上第一个计算机科学家”，甚至是“有史以来最聪明的人”。
他描述了由穿孔卡片控制的二进制计算机的原理(年)。年，他设计了第一个可以执行所有四种算术的物理硬件（步进计算器），超越了WilhelmSchickard()和BlaisePascal()的第一个基于齿轮的自动数据处理计算器。
Leibniz不仅是发表微积分的第一人，而且还进行了一个雄心勃勃的项目，通过计算来回答所有可能的问题。他关于通用语言和推理的通用微积分的想法极具影响力（《通用的特性和演算推理者》灵感来自13世纪的学者RamonLlull）。
Leibniz曾有这样一段重要描述：“如果出现争议，两个哲学家之间就不需要争论，而是像两个会计师之间一样，手里拿着铅笔，坐下来就足够了，用他们的石板互相说：让我们计算一下！”然而，在年，G?del表明，以这种方式可判定或可计算的东西存在根本的局限性。
年，AlonzoChurch通过证明Hilbert和Ackermann著名的Entscheidungsproblem（决策问题）没有通用解决方案，推导出G?del结果的扩展。为此，他使用了名为UntypedLambdaCalculus的替代通用编码语言，该语言构成了极具影响力的编程语言LISP的基础。
年，AlanTuring引入了另一个通用模型：图灵机，该模型可能成为其中最著名的模型（至少在计算机科学领域）。他重新推导出了上述结果。当然，他在年的论文中同时引用了G?del和Church的方法。年，EmilPost发表了另一个独立的通用计算模型，同时也引用了G?del和Church的方法。今天我们知道很多这样的模型。根据Wang的说法，正是图灵的工作（）使G?del相信他自己的方法（-34）和Church（）的方法的普遍性。
Post和Turing在年究竟做了哪些G?del（-34）和Church（）没有做过的事情？有一个看似微小的差异，其重要性后来才显现出来。
G?del的许多指令序列是数字编码存储内容与整数的一系列乘法。G?del并不关心这种乘法的计算复杂度会随着存储大小的增加而增加。同样，Church在他的算法中也忽略了基本指令的时空复杂性。
然而，Turing和Post采用了传统的、简化的二进制的计算观点——就像KonradZuse()一样。他们的机器模型只允许非常简单的具有恒定复杂性的基本指令，就像Leibniz早期的二进制机器模型()。
EmilPost他们当时并没有利用这一点——例如，年，Turing使用他的（相当低效的）模型只是为了重新表述G?del和Church在极限上的结果可计算性。然而，后来，这些机器的简单性使它们成为复杂性理论研究的便利工具（他也很高兴地将它们用于永无止境的计算）。
哥德尔理论计算机科学奖以G?del命名。目前奖金更丰厚的美国计算机学会图灵奖创建于年，以表彰“对计算机领域具有持久和重大技术重要性”的贡献。
有趣的是——同时也令人尴尬的是——G?del(-)从未得到过该奖项的认可，尽管他不仅奠定了该领域“现代”版本的基础，而且在他写给JohnvonNeumann的著名信件中()，还确定了其最著名的开放问题“P=NP？”。
G?del(-34)、Church()、Turing()和Post()的正式模型是理论结构，不能直接作为实用计算机的基础。
值得注意的是，KonradZuse的第一台实用通用程控计算机的专利申请也可以追溯到年。它描述了通用数字电路（并且早于ClaudeShannon年关于数字电路设计的论文）。
然后，在年，Zuse完成了Z3，这是世界上第一台实用、可运行的可编程计算机（基于年的应用程序）。忽略任何物理计算机不可避免的存储限制，Z3的物理硬件确实是G?del、Church、Turing和Post的“现代”意义上的通用——简单的算术技巧可以弥补Z3缺乏明确的条件跳转指令。Zuse还在20世纪40年代初期创建了第一个高级编程语言(Plankalkül)。他于年将其应用于国际象棋，并于年应用于定理证明。
值得一提的是，实用人工智能比G?del对人工智能基本局限性的理论分析要古老得多。
年，西班牙人LeonardoTorresyQuevedo是20世纪第一个实用AI的先驱，当时他建造了第一个可工作的国际象棋终局棋手（当时国际象棋被认为是一种仅限于智能生物领域的活动）。
几十年后，当AI先驱NorbertWiener年在巴黎会议上与它对抗时，这台机器仍然被认为令人印象深刻。现在通常被视为第一个关于人工智能的会议——尽管“AI”是在年晚些时候由约翰麦卡锡在达特茅斯的另一次会议上提出的。事实上，在年，现在称为人工智能的大部分内容仍然被称为控制论，其重点非常符合基于深度神经网络的现代人工智能。
同样，实用计算机科学比G?del的理论计算机科学基础要古老得多（比较上面对Leibniz的评论）。
也许世界上第一台实用的可编程机器是1世纪由Alexandria的Heron制造的automatictheatre（他显然也拥有第一个已知的工作蒸汽机——Aeolipile）。
他的可编程自动机的能量来源，是一个落锤拉动缠绕在旋转圆柱体销上的绳子。控制门和木偶几分钟的复杂指令序列由复杂的包装编码。9世纪由BanuMusabrothers发明的音乐自动机可能是第一台带有存储程序的机器。对比年Al-Jazari的可编程的鼓机，它使用旋转圆柱上的销钉来存储控制蒸汽驱动长笛的程序。
第一台商用程控机器（基于打孔卡的织机），是由Joseph-MarieJacquard等人于年左右在法国建造的——他们也许是第一批编写世界上第一个工业软件的“现代”程序员。他们启发了AdaLovelace和她的导师CharlesBabbage（英国，大约年），他们计划但无法构建非二进制、十进制、可编程的通用计算机。由Zuse()以外的其他人制造的第一台通用可编程机器是HowardAiken的十进制MARKI（美国，）。
G?del经常被称为继Aristotle以来最伟大的逻辑学家。在上个世纪末，时代杂志将他列为20世纪最有影响力的数学家，尽管一些数学家说他最重要的成果是关于逻辑和计算，不是数学。还有一些人认为他的成果是理论计算机科学的基础，该学科当时尚未正式存在，但正是通过G?del的努力得以产生。获得过普利策奖的畅销书《G?del,Escher,Bach》，激励了几代年轻人学习计算机科学。
年，我们不仅要庆祝G?del年著名论文发表90周年，还要庆祝Zuse（年）研制出世界上第一台功能性通用程控计算机80周年。令人难以置信的是，在不到一个世纪的时间里，曾经只存在于巨擘头脑中的东西已成为现代社会不可分割的东西。世界欠这些科学家一大笔债。
距离年G?del百年诞辰还有10年，距离年Zuse百年诞辰还有20年！有足够的时间来计划合适的庆祝活动。
参考文献
[1]