算法基础

在 20 世纪初，数学正处于危机之中。伯特兰·罗素刚刚发表了以他名字命名的悖论。这个具有毁灭性的悖论 ^[1] 表明，要将数学建立于坚实的基础之上实在无比困难。在缺少这种坚实基础的情况下，数学就像一座纸牌屋，稍有触碰便会轰然倒塌。戴维·希尔伯特也意识到了这一点。加固这座纸牌屋必须成为逻辑学家和数学家的最优先目标。弗雷格、康托尔、皮亚诺、罗素、怀特海、勒贝格、策梅洛、弗兰克和塔斯基，他们只是参与这项艰巨任务的伟大智者之中的一部分人。数十年来的工作累积成了对外行来说越来越晦涩难懂的著作。但希尔伯特仍未放弃。“我们必须知道，我们必将知道”，他在广播中发出了这一宣言。

但在 1931 年，一位 25 岁的年轻逻辑学家令希尔伯特的期望化为乌有。他通常被认为是历史上最伟大的逻辑学家，他就是库尔特·哥德尔。哥德尔证明了逻辑学家的一切努力都是徒劳无功的：数学的任何基础都必定只是一座纸牌屋。我们永远不可能证明这些基础无法动摇。这就是哥德尔（第二）不完备性定理 ^[2]。

尽管无法给希尔伯特和数学界带来安慰，但哥德尔的工作以及其他逻辑学家构筑的形式逻辑有着很好的眼光，涉及第 3 章谈到的那些符号推演规则的重要性。从非常形式化的角度来看，数学可以由此归结为一门非常精确的语言，其句法和语法都非常严格。这门语言（假设它没有矛盾）中的语句可以就此分为 4 个类别：可证明、可否证、不符合句法、无法判定。另外，给定一个语句，要确定它属于哪个类别，相当于询问是否存在某个符号推演的序列可以从所谓的公理，即被承认正确的由符号组成的语句出发，最终到达给定的语句（或它的否定）。

也许正是形式逻辑这种对符号推演的研究，让库尔特·哥德尔、阿朗佐·丘奇和艾伦·图灵各自独立发现了一串“在物理学上可行”的符号推演的三个不同定义。哥德尔定义了一般递归函数这一类别，丘奇引入了λ演算，而图灵则发明了今天以他的名字命名的计算机器。令人震惊的是，丘奇和图灵发现，所有这些定义实际上都是等价的 ^[3] ！

这项发现如此深刻，使得丘奇和图灵提出了所谓的“丘奇–图灵论题”。这一论题断言，所有“物理上可行的操作序列”“纯粹机械化的符号推演”“机器实行的计算”以及“算法”的概念，实际上都等价于哥德尔、丘奇和图灵的定义。正如斯科特·阿伦森说的那样：“如果你花上足够长的时间来思考这件事的话，最终就会得出结论：所有计算都可以通过图灵机完成。”

艾伦·图灵的基本定理是理论计算机科学的基础，它证明了所谓通用图灵机的存在性。这种通用图灵机可以模拟任意图灵机，因此它能计算哥德尔的一般递归函数以及丘奇的λ演算可以计算的所有东西。换句话说，存在这样一台机器，只要让它执行正确的代码，它就能够完成可以想象的任何（符合物理的）计算。

从表面上看，我们可能会认为，对这个计算的概念感兴趣的人只有那些逻辑或纯理论的研究者，也许还有一些研究模拟的科学家。然而，我们可以将丘奇–图灵论题诠释为这个宇宙的一条物理法则，因为它提出，在宇宙中没有任何计算机器能够解决图灵机不能解决的问题。这个假设牵涉整个宇宙！因此，如果丘奇–图灵论题正确，那么用上整个宇宙的计算能力都不能完成某件通用图灵机无法计算的事情。换句话说，这个宇宙中的所有东西都可以用通用图灵机来模拟 ^[4]。特别是，如果丘奇–图灵论题被证实的话 ²，那么我们的大脑就不外乎是一台图灵机。

丘奇–图灵论题对新技术产业有着深远的影响。这是因为，从计算的意义上来说，既然我们的大脑不可能超越通用图灵机，那么我们不如大力投资通用图灵机的生产。这些名称各异的通用图灵机已经占据了我们的日常生活。我们今天把它们叫作计算机、平板电脑或者智能手机 ³。