哥德尔证明了逻辑学家的一切努力都是徒劳无功的：数学的任何基础都必定只是一座纸牌屋。我们永远不可能证明这些基础无法动摇。这就是哥德尔（第二）不完备性定理。
在 20 世纪初，数学正处于危机之中。伯特兰·罗素刚刚发表了以他名字命名的悖论。这个具有毁灭性的悖论表明，要将数学建立于坚实的基础之上实在无比困难。 在缺少这种坚实基础的情况下，数学就像一座纸牌屋，稍有触碰便会轰然倒塌。
01 算法基础
戴维·希尔伯特也意识到了这一点。加固这座纸牌屋必须成为逻辑学家和数学家的最优先目标。弗雷格、康托尔、皮亚诺、罗素、怀特海、勒贝格、策梅洛、弗兰克和塔斯基，他们只是参与这项艰巨任务的伟大智者之中的一部分人。数十年来的工作累积成了对外行来说越来越晦涩难懂的著作。但希尔伯特仍未放弃。“我们必须知道，我们必将知道”，他在广播中发出了这一宣言。
但在 1931 年，一位 25 岁的年轻逻辑学家令希尔伯特的期望化为乌有。他通常被认为是历史上最伟大的逻辑学家，他就是库尔特·哥德尔。哥德尔证明了逻辑学家的一切努力都是徒劳无功的： 数学的任何基础都必定只是一座纸牌屋。 我们永远不可能证明这些基础无法动摇。这就是哥德尔（第二）不完备性定理。
尽管无法给希尔伯特和数学界带来安慰，但哥德尔的工作以及其他逻辑学家构筑的形式逻辑有着很好的眼光。从非常形式化的角度来看， 数学可以由此归结为一门非常精确的语言， 其句法和语法都非常严格。这门语言（假设它没有矛盾）中的语句可以就此分为 4 个类别：可证明、可否证、不符合句法、无法判定。另外，给定一个语句，要确定它属于哪个类别，相当于询问是否存在某个符号推演的序列可以从所谓的公理，即被承认正确的由符号组成的语句出发，最终到达给定的语句（或它的否定）。
也许正是形式逻辑这种对符号推演的研究，让库尔特·哥德尔、阿朗佐·丘奇和艾伦·图灵各自独立发现了一串“在物理学上可行”的符号推演的三个不同定义。哥德尔定义了一般递归函数这一类别，丘奇引入了 λ 演算，而图灵则发明了今天以他的名字命名的计算机器。令人震惊的是，丘奇和图灵发现，所有这些定义实际上都是等价的！
这项发现如此深刻，使得丘奇和图灵提出了所谓的“丘奇 – 图灵论题”。这一论题断言，所有“物理上可行的操作序列”“纯粹机械化的符号推演”“机器实行的计算”以及“算法”的概念，实际上都等价于哥德尔、丘奇和图灵的定义。正如斯科特·阿伦森说的那样：“如果你花上足够长的时间来思考这件事的话，最终就会得出结论：所有计算都可以通过图灵机完成。”
艾伦·图灵的基本定理是理论计算机科学的基础，它证明了所谓 通用图灵机 的存在性。这种通用图灵机可以模拟任意图灵机，因此它能计算哥德尔的一般递归函数以及丘奇的 λ 演算可以计算的所有东西。换句话说，存在这样一台机器，只要让它执行正确的代码，它就能够完成可以想象的任何（符合物理的）计算。
从表面上看，我们可能会认为，对这个计算的概念感兴趣的人只有那些逻辑或纯理论的研究者，也许还有一些研究模拟的科学家。然而，我们可以将丘奇 –图灵论题诠释为这个宇宙的一条物理法则，因为它提出，在宇宙中没有任何计算机器能够解决图灵机不能解决的问题。这个假设牵涉整个宇宙！因此，如果丘奇 –图灵论题正确，那么用上整个宇宙的计算能力都不能完成某件通用图灵机无法计算的事情。换句话说，这个宇宙中的所有东西都可以用通用图灵机来模拟。特别是，如果丘奇 – 图灵论题被证实的话，那么我们的大脑就不外乎是一台图灵机。
丘奇 – 图灵论题对新技术产业有着深远的影响。这是因为，从计算的意义上来说，既然我们的大脑不可能超越通用图灵机，那么我们不如大力投资通用图灵机的生产。这些名称各异的通用图灵机已经占据了我们的日常生活。我们今天把它们叫作计算机、平板电脑或者智能手机。
02 “模式”是什么？
无论是在数学、物理还是技术上，图灵机都有着众多应用。但我讨论图灵机不是出于这些原因，而是出于哲学上的原因。这是因为在认识论的意义上， 要严格定义数学家经常粗略谈到的“模式”或“规则性”的概念，图灵机似乎是最完美的工具。
考虑以下数列：1, 2, 4, 8, 16。你知道下一项是什么吗？你很可能会猜 16 的下一项是 32，甚至对这项猜测特别有自信。但为什么呢？我只给出了这个数列的一个非常有局限性的抽样——只有 5 个数据点，为什么它之后的项看起来那么容易预测？你对自己猜测的高置信度又有何依据？
你脑海中的论证大概是这样的：1 乘以 2 就能得到 2，将 2 变成 4 也是乘以 2，从 4 到 8、从 8 到 16 也是这样。所以问题中的数列就应该是将前一项乘以 2 得到的。这个模式这么规则而简单，似乎必定会延伸下去。换种说法，存在一个非常简单的算法，也就是计算的规则，可以产生这个数列中的每一项。根据奥卡姆剃刀（我们之后会再谈到），算法如此简洁似乎就是一种几近决定性的论据。
然而，上文中的数列还有一种完全不同的解释方法。我们先画一个圆，然后在圆上取两个点，画出一条通过这两个点的直线。这样圆的内部就被分成了两份。在圆上再取第三个点，然后画出它与之前两个点的连线，我们实际上就画了一个圆内接三角形，把圆分成了三角形和外面的 3 个部分，也就是一共 4个部分。如果再加上第四个点，画出它与其他三个点的连线的话，圆就被分成了 8个部分。加上第五个点的话，圆就会被分成 16 份！
所以 1, 2, 4, 8, 16 这个数列就对应着每次在圆上添加一个点，然后画出它与其他点的连线之后，将圆划分成的份数。于是，为了得到下一项，我们可以计算加上第六个点之后圆被切成多少份。结果会让你大吃一惊，这个数字是 31，而不是32 ！所以，这就是补全该数列的另一种方法。
如此一来，我们必须重新考虑一开始应该对数列下一项的猜测赋予多少置信度了。应该给数列添加 31 还是 32 ？存在唯一的正确答案吗？我们对于不同的答案又应该赋予多少置信度？数列的下一项还有没有第三种可能性？
我们仍然觉得，即使数列下一项有充分的理由是 31，而且该项也许还有别的可能性，但 32 仍然是最可信的。我们有没有办法将这种想法严谨地叙述出来？
1963 年，数学家安德烈·柯尔莫哥洛夫做出了肯定的回答。柯尔莫哥洛夫依靠哥德尔、丘奇和图灵关于计算的概念，定义了一种方法，用于衡量类似 1, 2, 4, 8, 16, 32 和 1, 2, 4, 8, 16, 31 这种数列的复杂度。这种复杂度今天又被称为 柯尔莫哥洛夫复杂度 ，它已成为可计算性理论中的基础概念。
但柯尔莫哥洛夫并不是第一个想到这个复杂度概念的人。所罗门诺夫对此知道得更早，在 1960 年就发表了相关研究的初步报告。所以，把这个概念叫作 所罗门诺夫复杂度 才更准确！然而，大概是因为所罗门诺夫不巧将他的复杂度与在美国被认为是异端的贝叶斯主义联系在了一起，所以最终还是俄国的柯尔莫哥洛夫的研究结果被广泛阅读和引用。讽刺的是，所罗门诺夫在 2003 年被授予柯尔莫哥洛夫奖，获奖原因正是他发现了柯尔莫哥洛夫复杂度！
上文转自人邮图灵《贝叶斯的博弈》，作者黄黎原，[遇见数学]已获转发许可。
推荐阅读
作者：[法] 黄黎原, 译者：方弦
法国数学科普类大学数学参考类畅销图书
读者无须过多专业数学知识，无须身为数学家，也可领略本书的精彩之处
