90年前，哥德尔提出数学界的相对论：「不完备性定理」，还迷倒了爱因斯坦

新智元报道  

来源：Reddit

编辑：yaxin

【新智元导读】1931年，哥德尔提出了「不完备性定理」，至今已有90周年。他对20世纪的科学和哲学产生了巨大的影响，是现代理论计算机科学和人工智能理论之父。

在逻辑学中的地位，一般都将他与亚里士多德和莱布尼兹相比。

在数学中的地位，爱因斯坦将他的贡献与他本人对物理学的贡献相提并论。

他，就是奥地利裔美国著名数学家库尔特·哥德尔（Kurt Gödel），被誉为20世纪最伟大的数学家和逻辑学家之一。

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

1931年，哥德尔发表了 On Formally Undecidable Propositions of Principia Mathematica and Related Systems ，文中提出了「不完备性定理」。

至今，已有90年。

这篇巨作提出的理论让数学基础研究发生跨时代的变化，成为现代逻辑史上的重要里程碑。

要知道，「不完备性定理」与塔尔斯基的形式语言和真理论，图灵机和判定问题，被赞誉为现代逻辑科学在哲学方面的三大成果。

90周年——不完备性定理

究竟什么是「不完备性定理」？

在 1931 年的那项研究中，哥德尔引入了一种通用语言对任意形式化的过程进行编码。

他使用基于素数因数分解的哥德尔编码系统。

他首先把唯一的自然数指派到在他所处理的算术的形式语言中的每个基本符号。

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

不完备性定理一共包含两条：

第一定理：任意一个包含一阶谓词逻辑与初等数论（皮亚诺算术公理）的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

第二定理：任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性（无矛盾性）。

1935 年，阿隆佐·丘齐（Alonzo Church）通过证明 Hilbert & Ackermann 著名的 Entscheidungsproblem（判定问题）没有一个通用解决方案，推导出哥德尔结果的推论/扩展。

丘齐使用了 Untyped Lambda Calculus 的通用编码语言，这门语言构成了极具影响力的编程语言 LISP 的基础。

1936年，阿兰·图灵（Alan Turing）推出了另一个通用模型，这个模型就是最著名的「图灵机」。

图灵重新推导了上述结果。他在 1936 年的论文中同时引用了哥德尔和丘奇。

计算机科学领域著名的「哥德尔奖」就是以哥德尔的名字命名的，以表彰那些「对计算机领域具有长久和重大的技术贡献」。

有趣的是，哥德尔本人从未获得过一个奖项，且不提他奠定了现代理论计算机科学领域的基础，而且哥德尔还在他写给约翰·冯·诺依曼的著名信件中（1956 年）确定了最著名的开放问题「P= NP？」。

‍

哥德尔——不完备的一生

哥德尔生于捷克的布尔诺，早年在维也纳大学攻读物理、数学，并参加哲学小组活动。

‍哥德尔（左二）

网上曾曝光了，哥德尔的最早文字记录是他的小学数学练习本，大约时间是 1912 年，那时的他才 6 岁。

8 岁时，哥德尔患上了严重的风湿性关节炎。

中学时期，哥德尔在数学和几何方面的才能初显，16 岁就开始阅读康德的著作。

他认为康德对他的智力发展具有塑造作用。这一时期，由于富裕和很高的社会地位，哥德尔一家并没有受到一战战后重建的太大干扰，这也为哥德尔的不断求学打好了物质基础。

哥德尔在1930年获博士学位。其博士论文证明了「狭谓词演算的有效公式皆可证」，之后在维也纳大学工作。

1938 年到美国普林斯顿高等研究院任职，1948 年加入美国籍。1953 年成为该所教授。哥德尔发展了冯·诺伊曼和伯奈斯等人的工作，其主要贡献在逻辑学和数学基础方面。

50 年代后，哥德尔的身体健康问题和精神问题越发严重。哥德尔晚年不相信别人做的饭菜，但太太阿黛尔也病倒了，没法照顾他。

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

参考资料：

http://mathcubic.org/article/article/index/id/530/cid/3.html