元数学：计算机、悖论与数学基础 (8-3)

哥德尔不完备性

哥德尔于 1931 年在维也纳大学任教时，提出了希尔伯特的观点，尽管他最初来自现在的捷克共和国布尔诺市（当时是奥匈帝国的一部分）。后来，哥德尔与爱因斯坦一起进入普林斯顿高等研究院。

哥德尔的惊人发现是，希尔伯特大错特错了：事实上，不可能为所有数学建立一个正式的公理系统，让人们一目了然地知道某件事情是否正确。更确切地说，哥德尔的发现是，即使你只尝试处理基本算术，处理数字 0、1、2、3......以及加法和乘法，这个计划也会失败。

任何形式系统，如果试图对关于加法、乘法和数字 0、1、2、3......的全部真理加以包含，而且只包含真理，那么它就必须是不完整的。事实上，它要么是不一致的，要么是不完整的。因此，如果你假设它只说出真理，那么它就不会说出全部真理。特别是，如果你假设公理和演绎规则不允许你对假定理加以证明，那么就会存有你所无法证明的真定理。

哥德尔的不完备性证明非常聪明。非常矛盾/悖论。它看起来几乎是疯狂的。哥德尔实际上是从骗子悖论开始的："我是假的！"这句话既不是真的，也不是假的。实际上哥德尔所做的，是对一个语句加以构造。它自己说："我是不可证明的！" 现在，如果你能在初等数论、算术中构造出这样一个语句，一个描述自身的数学语句，你一定非常聪明，但如果你能做到这一点，很容易就能看出，你有麻烦了。为什么？因为如果这个语句是可以证明的，那么它必然是假的，而你所证明的，乃错误的结果。如果它是不可证明的，就像它自己所说的那样，那么它就是真的，而数学则是不完备的。

哥德尔的证明，涉及许多复杂的技术细节。但是，如果你看一下其原始论文，你会发现其中有些东西看起来很像LISP 编程。这是因为哥德尔的证明，涉及到对大量函数加以递归定义，这些函数处理列表——恰乃 LISP 的全部内容。因此，尽管 1931 年还没有计算机或编程语言，但事后看来，你可以清楚地看到哥德尔原始论文之核心，是一种编程语言。

SSiq

Easy-ISLisp Ver3.5∅

＞ (encode “∃xy~(x)∧(y)”)

395∅17145154∅311835665999∅58572921825682∅144∅5∅224∅∅∅6394147∅444799∅234375∅∅∅∅＞(decode 395∅17145154∅311835665999∅58572921825682∅144∅5∅224∅∅∅6394147∅444799∅234375∅∅∅∅）“∃xy~(x)∧(y)”

＞∏

那个时代的另一位著名数学家约翰-冯-诺依曼（顺便说一句，他对美国计算机技术的发展起到了重要的推动作用）立即领会了哥德尔的洞察力。冯-诺依曼从未想过希尔伯特的计划是不靠谱的。因此，哥德尔不仅非常聪明，而且有勇气想象希尔伯特可能是错的。

在许多人看来，哥德尔的结论绝对是毁灭性的： 所有传统的数学哲学都被打倒在地。然而，1931 年的欧洲还有一些其他问题需要担心。当时欧洲经济大萧条，战争正在酝酿之中。

图灵机

五年后，阿兰-图灵在英国发现了不可计算性（uncomputability），这是下一个重大进步。 记得希尔伯特曾说过，应该有一个 "机械程序"来对一个证明是否符合规则加以决定。希尔伯特从未对其所说的 "机械程序 "是什么意思加以阐明。图灵基本上是说："你真正的意思是一台机器"（我们现在称之为图灵机的那种机器）。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。