玻尔百科计算领域有望解决极其复杂的问题，似乎只受处理能力和时间的限制。然而，在这一领域的核心，却存在一个惊人的悖论：存在一些简单、明确定义的问题，任何计算机，无论多么强大，都永远无法回答。这些不仅仅是难题，而是逻辑上不可能解决的问题。本文旨在探讨我们直觉上认为计算机应该能做到的事情与它们在数学上实际能做到的事情之间的这一根本鸿沟。它揭示了不可判定问题的存在和本质，这一概念重新定义了逻辑推理本身的边界。
我们的旅程始于“原理与机制”一章，在那里我们将使用优雅的图灵机模型来形式化“算法”这一概念。我们将探索这个模型的惊人能力，但也将通过证明最著名的不可判定问题——停机问题——来揭示其最终的局限性。在此基础上，“应用与跨学科联系”一章将揭示这一个不可解点如何向外扩散，影响从软件验证和数据压缩的实际挑战，到纯粹数学的抽象深度，再到经济学和法学等领域中人工智能的哲学限制等方方面面。
想象一下，你有一个完美、不知疲倦的助手，他能遵循任何一套指令，无论多么复杂，从不出错。这正是催生了计算领域的梦想。但如果我告诉你，即使有这样完美的助手，也有些听起来简单的问题在根本上、永恒地无法回答呢？这并非因为它们太难，而是因为它们在原则上就是不可能的。这不是哲学或神秘主义，而是一个如重力般坚实的数学事实。要理解这一点，我们必须首先理解“指令”究竟是什么。
我们都对“算法”有一个直观的理解——它是一个食谱、一张清单，一个为实现目标而设定的有限的、明确的步骤序列。在20世纪30年代，数学家们试图将这一思想形式化。在众多杰出且等价的表述中，经受住时间考验的或许是 Alan Turing 的抽象设备：图灵机。你可以把它想象成最简单的计算机：一条长长的纸带，一个可以在纸带上读、写、移动的读写头，以及一小组规则，比如“如果你看到1，就把它改成0，然后向右移动”。
真正令人惊奇的是丘奇-图灵论题，这是计算机科学的一个基本原则。它断言，这台简单的机器就是你所需要的一切。任何可以通过任何可想象的“有效方法”——任何你能想出的算法——解决的问题，都可以由图灵机解决。这个论题将我们对计算的直观概念与一个具体的数学对象联系起来。
支持这一大胆主张的证据是压倒性的。首先，所有其他发明的计算形式模型（如 Alonzo Church 的 lambda 演算）都已被证明在能力上与图灵机等价。但也许最引人注目的证据来自通用图灵机（UTM）的存在。这不仅仅是任何一台图灵机；它是一台特殊的机器，其天才之处在于其通用性。你可以给它任何其他图灵机 的描述和其纸带上的一个输入 。UTM 随后会读取 的描述，并完美地模拟它在输入 上的行为。
这是一个惊人的想法。它意味着一台单一的、固定的机器，用一套单一的、固定的规则，就足以执行任何其他机器能执行的任何任务。它就是你现在正在使用的现代存储程序计算机的理论蓝图——一个通用设备，在不同数据（“输入 ”）上运行不同软件（“ 的描述”）。UTM 的存在有力地表明，图灵机模型已经捕捉到了计算的普遍本质。
有了这台全能的通用图灵机，似乎我们就有了一个工具来回答任何明确提出的数学问题。这个数是素数吗？是的。这个棋局能赢吗？也许。这个逻辑陈述是真的吗？让我们来找找看！似乎一切皆有可能。
但在这里，我们遇到了第一个，或许也是最深刻的冲击。所有可能问题的集合远远大于所有可能答案的集合。这不是一个观点问题，而是无穷数学的一个推论。
考虑所有可能的计算机程序（或图灵机）的集合。每个程序都只是一个用有限字母表（如英文字母，或0和1）写成的有限文本字符串。我们可以想象列出所有可能的程序：首先是所有长度为1的程序，然后是长度为2的，依此类推。这个列表将是无限长的，但它终究是一个列表。任何其元素可以这样列出的集合被称为可数无限。
现在，让我们考虑所有可能的“判定问题”——那些只有简单“是”或“否”答案的问题。一个判定问题可以被看作一个函数，它为每个可能的输入赋予“是”（1）或“否”（0）。假设输入是自然数 。一个问题可能是“输入是偶数吗？”，这对应于无限二进制序列 。另一个问题可能对应于另一个不同的序列。所有可能的判定问题的集合就是所有可能的无限二进制序列的集合。
使用 Georg Cantor 一个名为对角线论证法的美妙论证，我们可以证明这个集合是不可数无限的。你无法创建一个包含所有这些序列的完整的、编号的列表。如果你尝试这样做，Cantor 展示了如何构造一个保证不在你列表上的新序列。这意味着问题的无穷比程序的无穷是一个“更大”的无穷。
结论是不可避免且惊人的。既然我们有不可数多个问题，但只有可数多个程序来解决它们，那么必然存在没有解决程序的的问题。事实上，绝大多数问题都是不可解的。我们甚至还没有找到一个具体的例子，就已经证明了不可判定问题的存在。
知道存在无法航行的海洋是一回事；在地图上找到第一片这样的海域则是另一回事。最著名的不可判定问题，也是整个领域基石的，是停机问题。这个问题听起来极其简单：
给定任意程序 的代码和任意输入 ，当程序 在输入 上运行时，它最终会停止，还是会永远运行在一个无限循环中？
这并非一个学术上的好奇。每个程序员都曾写过导致程序冻结的错误。一个能解决停机问题的工具将是终极调试器。它可以审查任何代码是否存在这种灾难性的缺陷。
可惜，这样的工具永远无法被制造出来。其证明过程与古老的“说谎者悖论”（“这句话是假的”）如出一辙。逻辑与计算之间的深刻联系，在哥德尔不完备定理中已初见端倪，在此处得到了充分体现。
让我们通过一个思想实验来证明这一点。假设你构建了一个神奇的程序，我们称之为 HaltingOracle(, )，它能解决停机问题。如果程序 在输入 上会停机，它总是返回 true；如果它会永远运行，则返回 false。
现在，利用这个预言机，我们可以构造一个名为 Paradox() 的新的、淘气的程序：
Paradox 接受一个程序 的代码作为其输入。HaltingOracle：HaltingOracle(, )。true（意味着 在输入自身代码时会停机），Paradox 就立即进入一个无限循环。false（意味着 会永远循环），Paradox 就立即停机。现在是最具毁灭性的问题：当我们在 Paradox 上运行它自己的代码时会发生什么？Paradox(Paradox) 的结果是什么？
Paradox(Paradox) 停机，这意味着 HaltingOracle 对于输入 (Paradox, Paradox) 必定返回了 false。但预言机只有在其输入程序永远运行时才返回 false。所以，Paradox(Paradox) 停机，当且仅当它永远运行。矛盾。Paradox(Paradox) 永远运行，这意味着 HaltingOracle 必定返回了 true。但预言机只有在其输入程序停机时才返回 true。所以，Paradox(Paradox) 永远运行，当且仅当它停机。矛盾。这个逻辑就像一条蛇在吞食自己的尾巴。既然构建 Paradox 的每一步都是有效的，那么唯一可能的失败点就是我们最初的假设：一个像 HaltingOracle 这样的程序可以存在。它不能存在。停机问题是不可判定的。
停机问题并非一个孤立的不可能性孤岛。它是计算世界中一种传染病的“零号病人”。这种传染的机制是一种强大的逻辑工具，称为归约。
归约是一种表述方式：“如果我能解决问题A，我就能轻易解决问题B。”想象你不知道怎么做乘法，但你有一个可以计算任何数平方的神奇盒子。你可以通过恒等式 轻易地计算出 和 的乘积。你已经把乘法问题归约到了平方问题。
在可计算性理论中，我们反向使用这个方法。如果我们知道问题B（如停机问题）是不可判定的，并且我们可以将B归约到A，那么问题A也必须是不可判定的。为什么？因为如果A是可判定的，我们就可以利用我们的归约来构建一个B的解决器，而我们知道这是不可能的。
这项技术揭示了一个广阔的不可判定领域。
计算机的复杂性重要吗？只要它足够强大就不重要。即使是一台只有两个计数器和几条指令的极简机器（双计数器机），也可以被编程来模拟任何图灵机。这个特性被称为图灵完备性。因此，如果你能解决这台简单机器的停机问题，你就能解决所有图灵机的停机问题。所以，即使对于这种看似原始的设备，停机问题也是不可判定的。不可判定性是计算能力的属性，而非架构复杂性的属性。
考虑一家软件公司想销售一款名为 EquivalenceEngine 的工具。这个工具可以接收两个程序 和 ，并判断它们在功能上是否等价——也就是说，它们是否对所有可能的输入都产生相同的输出。这听起来对于优化代码或验证正确性非常有用。但这是不可能的。我们可以将停机问题归约到它。要判断程序 是否在输入 上停机，我们可以构造两个新程序。 首先在 上运行 ，如果它停机，就打印 "Hello!"。 是一个只打印 "Hello!" 的简单程序。 和 等价吗？答案是“是”，当且仅当 在 上停机。如果我们的 EquivalenceEngine 存在，我们就能用它来解决停机问题。因此，它不能存在。
同样的归约逻辑证明了大量关于程序行为的看似实际的问题都是不可判定的：这个程序会打印“Hello, World!”吗？它接受空字符串吗？它接受的输入集合是空的，还是恰好包含十个字符串？。一旦你问一个关于程序最终行为的问题，你很可能就踏入了不可判定性的禁区。
至此，你可能会感到一种计算上的绝望。如果我们甚至无法判断一个程序是否会完成，我们还能知道什么呢？幸运的是，可知与不可知之间的界线非常清晰。
关键在于区分程序的文本和它的行为。
语法属性是关于源代码本身，即静态的字符序列。程序在语法上有效吗？它是否包含整数 42？机器的定义是否恰好包含十个状态？这些问题总是可判定的。一个算法可以简单地读取代码并检查。
语义属性是关于程序运行时所体现的意义或行为。它会停机吗？它输出什么？它接受什么样的输入集合？著名的莱斯定理将我们的发现形式化了：程序的任何非平凡的语义属性都是不可判定的。“非平凡”仅指该属性对某些程序为真，对另一些程序为假。
还有另一条关键的分界线：有界问题与无界问题。
“程序 在输入 上是否在1,000,000步之内停机？” 这是完全可判定的。算法很简单：你模拟程序运行1,000,000步。如果到那时它已经停机，答案是“是”。如果没有，答案是“否”。这个判定器本身总是会停机。
“程序 在输入 上最终是否停机？” 这就是停机问题。它是不可判定的，因为没有上限。如果一个程序已经运行了十亿年，你不知道它会在下一步停机，还是会再运行十亿年。“最终”这个词是一个深渊，算法永远无法确定能从中返回。
我们能否通过跳出确定性框架的思维方式来逃离这个逻辑的牢笼？如果我们建造一台包含真正随机性的机器，比如来自放射性衰变的量子涨落，会怎样？。这样的机器能解决停机问题吗？
答案或许令人惊讶，是不能。随机性并不能赋予我们计算不可计算之物的能力。想象一台概率性机器试图解决停机问题。对于给定的输入，它抛一些硬币并遵循一条计算路径。任何单一路径，由特定的随机结果序列（例如，正面、反面、正面...）决定，都只是一次常规的确定性计算。如果没有任何单一的确定性路径可以解决问题，那么在它们之间随机游走也无法解决问题。
即使我们允许一个有界错误算法——一个能以很高的概率给出正确答案的算法——它也行不通。一台确定性机器可以模拟这台概率性机器，通过探索其可能计算的树状结构来计算它回答“是”的概率。一旦这个计算出的概率超过一个阈值（例如，高于0.9），确定性机器就会知道答案。这将再次创造一个停机问题的确定性解决器，导致同样的矛盾。
计算的极限并非我们确定性模型的产物。它们是“算法”这一概念的根本特征。这一发现远非一个令人沮丧的结果，而是20世纪最伟大的智力成就之一。它定义了我们能力所及的边界，并在此过程中，让我们对逻辑推理本身那宏伟而又有限的力量，有了一个更深刻、更诚实的理解。
现在我们已经探讨了不可判定性的原理，并凝视了停机问题的深渊，你可能会倾向于认为这只是理论计算机科学中一个狭隘、深奥的角落。一个有趣的悖论，或许，但与“现实世界”关系不大。然而，事实远非如此。不可判定问题的发现，不是我们机器中一个缺陷的发现，而是我们逻辑宇宙中一条基本定律的发现，其深刻和不可避免性堪比热力学定律。这一原理不仅存在于数学家的黑板上，它的影响渗透到几乎所有依赖逻辑和计算的人类探究领域。现在，让我们来审视这些联系，看看这个“机器中的幽灵”如何塑造我们的世界。
每一位程序员，从写下第一个“Hello, World!”的新手，到大型科技公司的资深工程师，都有一个共同的梦想：编写完美无瑕的代码。他们也共享一个共同的噩梦：导致系统崩溃的意外运行时错误。如果我们能构建终极调试工具呢？一个静态分析器，可以读取任何代码，甚至无需运行它，就能确定地告诉我们它是否会失败——例如，是否会尝试除以零。
可惜，这个梦想被证明是不可能实现的。判断任意程序是否会执行除以零操作的问题，实际上是不可判定的。我们可以通过证明如果你能够构建这样的工具，你就能用它来解决停机问题来表明这一点。论证过程非常简单：取任何你想测试是否停机的程序，在其末尾加上一行代码：print(1/0)。如果你神奇的错误检查器说这个修改后的程序会除以零，你就知道原始程序必须已经停机才能到达那一行。如果它说不会，那么原始程序必定会永远运行。既然我们知道停机问题是无解的，我们神奇的错误检查器就不可能存在。
这不仅仅是关于除以零的问题。同样的逻辑适用于大量的程序属性，这一现实由莱斯定理形式化。一个程序会访问一个禁止的内存位置吗？它会陷入无限循环吗？一个网络服务器会泄露用户的私人数据吗？对于程序行为的任何非平凡属性，都没有通用算法可以对所有可能的程序回答这个问题。这就是为什么软件验证如此困难——不是因为我们不够聪明，而是因为我们面对的是一个根本的限制。
同样的障碍也以更微妙的方式出现。想象一下你正在开发一门复杂的编程语言。经过一年的工作，你发布了2.0版本，带有一个优化的编译器。你如何能确定新的编译器对每一个可能的程序的解释方式都与旧的完全相同？你正在询问由两种不同文法生成（或由两种不同编译器执行）的语言是否相同。这是上下文无关文法的等价性问题，它也是不可判定的。我们可以在一百万个程序上测试它，但仍然无法确定，因为可能性的空间是无限的，没有算法能提供普遍的保证。
让我们从程序转向数据。压缩文件的最佳方法是什么？我们可以将压缩文件看作一个生成原始文件的“程序”。一个数据字符串的终极无损压缩将是生成它作为输出的最短可能程序。这个最短程序的长度被称为该字符串的柯尔莫哥洛夫复杂度。在某种意义上，它是字符串信息含量的最纯粹度量。一个像“10101010...”这样高度模式化的字符串具有非常低的复杂度，而一个真正随机的字符串的最短描述就是它本身——它是不可压缩的。
在这里，我们再次碰壁。人们可能希望构建一个“完美压缩器”，对于任何给定的字符串，都能找到其最短的可能描述。但计算字符串柯尔莫哥洛夫复杂度的函数是不可计算的。一个“完美压缩器”的存在将为我们提供一种解决停机问题的方法，从而导致逻辑矛盾。我们永远无法确定我们是否已经为一段数据找到了绝对最佳的压缩。我们可以发明越来越巧妙的压缩方案，如ZIP或JPEG，但我们永远无法发明一个可以证明对所有输入都是最佳的方案。不可判定性的概念为信息论本身划定了一个基本边界，将计算的极限与随机性的定义紧密地联系在一起。
也许你认为这仍然是一个“计算机”问题。但不可判定性的冲击在于，它出现在那些远在第一个真空管发光之前就已构思出的纯粹数学领域。
在抽象代数中，数学家研究称为群的结构，这些结构由一组生成元和一系列规则（或关系）定义。群的字问题提出了一个简单的问题：给定一个由生成元组成的字符串，根据群的规则，它是否能简化为单位元？对于许多群来说，这很容易解决。但在20世纪50年代，数学家 Pyotr Novikov 和 William Boone 独立证明了存在有限表示群，其字问题是不可判定的。没有通用算法可以处理这样一个群中的任何“字”，并判定它是否等于单位元。计算的障碍不在于我们芯片的硅中；它被编织在抽象数学结构的肌理之中。
同样的现象也出现在几何学和线性代数中。考虑一个名为王氏铺砖问题的简单谜题。你得到一套有限的方块瓷砖，每个瓷砖的边缘都涂有颜色。你能否使用这些瓷砖（不旋转它们）来铺满整个无限平面，使得相邻边缘的颜色总是匹配？这似乎是一个无害的组合游戏。然而，它是不可判定的。原因在于，人们可以巧妙地设计一套瓷砖，它们只有通过模仿图灵机的逐步计算才能铺满平面。一个完整的平面铺砖对应于一个永远运行的图灵机。因此，一个解决铺砖问题的算法可以用来解决停机问题。
这种与物理般排列的联系有一个惊人的启示。王氏铺砖的局部匹配规则类似于物理学中的局部相互作用定律，比如分子间的化学键。铺砖问题的不可判定性表明，理论上物理系统（如晶体生长或分子自组装）可能由局部规则支配，而其全局、长期的行为是根本不可预测的[@problem_tiling_problem:1405451]。
即使是简单的矩阵乘法也隐藏着深意。如果你得到一组 的整数矩阵，你可以用算法判定它们的某个有限乘积是否等于单位矩阵。但如果你转向 的矩阵，这个问题——被称为矩阵半群的单位元问题——突然变得不可判定。判断某个乘积是否能得到零矩阵也是如此。当我们增加维度时，这种从可判定到不可判定的“相变”是一个惊人的例证，说明了复杂性如何从简单的系统中涌现，并跨越一个无法逾越的计算鸿沟。这些数学结果，连同其他结果如波斯特对应问题（），共同支持了丘奇-图灵论题：图灵机极限并非其设计的偶然，而是反映了任何“有效方法”或物理过程所能计算的普遍边界。
当我们考虑将不可判定性应用于复杂的、以人为中心的系统时，其最深远的影响便浮现出来。我们生活在一个大数据和人工智能的时代，越来越相信只要有足够的数据和处理能力，我们就能创造算法来解决我们最紧迫的问题。不可判定性为这种技术乐观主义提供了一个关键而又令人谦卑的修正。
考虑一下“完美人工智能经济学家”的梦想，一个名为 MarketGuard 的算法，它可以分析任何提议的经济政策，并确定地预测它是否能防止所有未来的市场崩溃。一个市场可以被建模为一个巨大的计算系统，其中代理（人、公司）遵循规则（行为、法律）。“崩溃”只是这个系统的某个特定状态。询问一项政策是否能防止所有崩溃，等同于询问这个计算系统，从某个初始状态开始，是否会进入一个“崩溃状态”。由于底层系统足够强大，可以模拟一个通用图灵机，这个问题就变得不可判定了。没有任何算法能够为所有可能的经济体和政策提供永恒稳定的保证。
这并不意味着经济模型是无用的。一般性问题是不可判定的，但具体的、受约束的版本可能完全可解。例如，我们当然可以构建一个算法来检查在有限的时间范围内（比如未来五年内），给定一个简化的模型，是否会发生崩溃。此外，这个问题通常是半可判定的。我们可以运行一个模拟，如果发生崩溃，我们可以停止并报告它。但如果在模拟了万亿年后没有发生崩溃，我们仍然不知道它是否会在万亿零一年发生。我们可以证明灾难的存在，但我们永远无法证明其永恒的缺席。
一个更引人注目的思想实验是 Aegis，一个被提议的通用人工智能法官，它接收所有法律、证据和论点，并输出一个完全公正的“有罪”或“无罪”的判决。这也是一个计算上的不可能。一个法律体系，如果它足够丰富和富有表现力，就可以被用来构建自我指涉的悖论。人们可以写一条法律规定：“被告有罪，当且仅当 Aegis 系统认定其无罪。”无论 Aegis 做出何种判决，都会产生矛盾。这是哥德尔不完备定理在现实世界的回响。任何足够强大到可以谈论自身的正式系统，都会包含它无法证明的真陈述，或者在这种情况下，无法在不产生矛盾的情况下判决的法律案件。
了解到这些限制可能会让人感到沮丧，仿佛一扇宏伟的大门被猛然关上。但这是错误的看法。不可判定性不是一堵墙，而是逻辑宇宙无限丰富的证明。它告诉我们，没有任何单一的算法，无论多么巧妙，能够穷尽数学的所有真理或预测复杂系统的所有行为。它保证了人类的创造力、直觉和独创性将永远有其用武之地。它确保了未来将永远充满惊喜。无法回答的问题的存在，并非失败的标志；它是探索无尽前沿的终极承诺。