数学、形式逻辑和算法殊途同归导致计算机发明

大多数人不知道，计算机的发明最初是为了证明数学是不一致和不完整的。对许多数学家来说，这是一个令人深恶痛绝的时刻。

希尔伯特
故事要从德国数学家大卫-希尔伯特（David Hilbert）说起。1900 年，在巴黎举行的国际数学家大会上，希尔伯特列出了 23 个尚未解决的数学问题。但正是他提出的第二个问题，即算术一致性的形式证明，推动了我们今天所知的计算机的发明。

希尔伯特是一位坚定的决定论者。他有一句名言："我们必须知道我们将会知道！"他相信每一个数学问题都有明确的答案--要么是可证实的真，要么是可证实的假。他梦想有一套完整、自足的数学公理。

但是，1931 年，一位名叫库尔特-哥德尔（Kurt Gödel）的年轻人用他的《不完备性定理》（Incompleteness Theorems）摧毁了这一设想。哥德尔证明，在任何足以描述自然数算术的一致形式系统中，都存在无法在该系统中证明的事实陈述--一个系统的一致性无法通过其规则建立！从本质上说，哥德尔证明了希尔伯特关于完整和自洽数学的梦想在数学上是无法实现的。

罗素
英国哲学家和逻辑学家伯特兰-罗素（Bertrand Russell）也在努力研究这些启示。几十年前，罗素开始了一项雄心勃勃的计划，名为 "数学原理"。他的目标是将整个数学建立在一个坚实的逻辑基础上，没有矛盾，并以一套有限的公理为基础。他希望从纯粹逻辑中推导出全部数学。（从形式逻辑到数学）

"我想要确定性，就像人们想要宗教信仰一样。我认为在数学中比在其他地方更容易找到确定性。但我发现，我的老师希望我接受的许多数学证明充满了谬误，而且，如果确定性确实可以在数学中发现，那也将是在一个新的数学领域，它比迄今为止人们认为安全的数学领域具有更坚实的基础。但随着工作的进行，我不断想起关于大象和乌龟的寓言故事。我建造了一头大象，让数学世界可以赖以生存，但我发现大象摇摇欲坠，于是我又建造了一只乌龟，防止大象倒下。但乌龟并不比大象更稳固，经过大约二十年的艰苦努力，我得出结论，在使数学知识变得无可辩驳方面，我已经无能为力了"--伯特兰-罗素。

图灵
大约在同一时期，英国的阿兰-图灵也在思考一个相关的问题。希尔伯特的 "Entscheidungsproblem"（或称 "决策问题"）询问是否有一种标准方法或算法来确定任何数学语句的真假，图灵受此启发，开始构思通用计算的本质。

这促使他发明了 "图灵机"--一种假想的机器，只要能用算法描述，就能模拟任何数学计算（用算法模拟数学）。这将成为未来所有计算机的模型--它启发冯-诺依曼创造了 "存储程序计算机"，也就是你正在阅读的这台计算机。

在试图回答希尔伯特问题的过程中，图灵发现有些问题是图灵机无法解决的。其中一个问题是：给定一个程序，机器是否会停止？也就是说，它会到达程序的终点吗？事实证明，没有办法决定程序是停止还是永远运行。

这种认为存在 "不可计算uncomputable "函数的想法与哥德尔关于不可判定性的发现产生了共鸣。

当不可判定性和不完备性的消息逐渐进入 20 世纪数学界的意识时，纯粹的沸腾和焦虑在整个数学界蔓延开来。许多人感到他们脚下的土地似乎发生了变化，决定论数学宇宙的确定性变成了纯粹的幻想。

总结

• 希尔伯特相信所有数学问题都是可证明。但是失败了
• 罗素试图从形式逻辑推导证明所有数学。但是也失败了
• 阿隆佐·邱奇从英国数学家阿兰·图灵的论文出发证明了基本几何问题的算法不可解性。同时证明了一阶逻辑中真命题全集的解法问题是不可解的。
• 邱奇、图灵和哥德尔以及罗素和维特根斯坦通过不同的道路得出了相同的结论：哥德尔不完备。也就是说：不是所有的真理都能被证明，这一发现导致了计算机的诞生。
• 如果你眯起眼睛，你会发现哥德尔基本上发明了虚拟机，这样他就可以在数学中运行数学。然后，他用它来证明任何足够复杂的数学必然具有未定义的行为。