算法的故事 / 全书目录0 / 30 章已读

第 30 章 · 第一季终章

算法的极限——1936年，图灵为什么证明，有些问题永远不可能被程序彻底解决？

正在加载交互实验…

第一季 · 人类如何驯服数据 · 全系列最终章
第 30 章配图 1
来源
终章历史主线：1931—2026年 · Gödel、Church、Turing、Cook、Karp、P 与 NP、可计算性与人工智能1936年，英国剑桥大学。一名23岁的年轻数学家正在研究一个奇怪的问题。假设我们拥有一台足够强大的机器。它可以计算。可以保存信息。可以根据规则作出判断。甚至可以读取其他程序的代码，并模拟那些程序的运行。那么，这台机器是不是终有一天能够回答人类提出的所有数学问题？如果它运行得足够快呢？如果它拥有无限大的存储空间呢？如果我们让它运行一百万年呢？年轻数学家 Alan Turing 的研究，最终给出了一个令人震惊的答案。不行。而且，不是因为机器太慢。不是因为内存不够。也不是因为工程师不够聪明。而是有些问题，在通常的算法计算模型中，根本不存在能够对所有输入都给出正确答案并保证停机的通用程序。这项发现，后来成为整个计算机科学的理论基础之一。1936年，Turing 提交了论文：On Computable Numbers, with an Application to the Entscheidungsproblem《论可计算数及其在判定问题上的应用》。论文于1936年5月28日收到，同年分两部分刊出，后来收录在标为1937年的《伦敦数学学会会刊》第42卷，第230—265页。[turing.org.uk][A. M. Turing, 1936]这篇论文不仅为后来所谓的图灵机奠定了基础，还以严格的数学论证表明：算法本身存在边界。现在，作为我们《算法的故事》三十章的最后一章，我希望从这个问题出发，回答三个贯穿整个系列的终极问题：
  • 什么问题能够被算法解决？
  • 什么问题虽然能够解决，却可能需要难以承受的计算资源？
  • 当算法无法保证正确、完整或高效时，我们究竟应该怎样设计现实系统？
我们已经花了二十多章学习如何发明算法、组合算法和让算法运行在大型系统中。最后这一章，我们反过来研究：算法究竟不能做什么。

第一幕：1900年，数学家相信一切都可能被证明吗？

第 30 章配图 2
来源
第 30 章配图 3
来源
第 30 章配图 4
来源
故事要从计算机真正出现之前讲起。1900年，德国数学家 David Hilbert 在巴黎国际数学家大会上发表了著名演讲，提出了一系列影响后世数学发展的重大问题。当时的数学界正在努力建立严格的公理与证明体系。一个理想目标是：如果某个数学命题为真，我们能不能通过一套有限、明确的规则，把它证明出来？如果它为假，能不能找到证明它为假的方法？1928年，Hilbert 与 Wilhelm Ackermann 的著作进一步明确提出了著名的：Entscheidungsproblem，判定问题。其核心可以表述为：是否存在一种通用的机械化方法，能够判断任意给定的一阶逻辑公式是否在逻辑上有效？今天的我们可能会说：“写一个程序，让它自动判断所有逻辑命题不就行了？”但当时连“程序”究竟意味着什么，都还没有得到现代意义上的严格数学定义。

1931年，Gödel 的第一记重击

1931年，年仅25岁的数学家 Kurt Gödel 发表了不完备性定理。在满足一定条件的形式公理系统中，如果系统足够强大、能够表达基本算术，并且符合相应的一致性要求，就会存在系统自身不能证明的算术命题。这改变了数学家对形式系统能力的理解。但要注意：Gödel 的不完备性定理和 Turing 后来对算法不可判定性的证明，不是同一个定理。前者研究形式公理系统能够证明什么。后者研究机械化计算过程能够决定什么。二者具有深刻联系，但不能简单混为一谈。直到1936年，问题才出现了真正的计算机器形式化答案。

第二幕：1936年，Church 与 Turing 从两条不同的道路接近答案

第 30 章配图 5
来源
Alonzo Church1903—1995年，美国数学逻辑学家。通过 λ 演算与递归函数等形式化方法研究有效可计算性。
在 Turing 的研究前后，美国数学家 Alonzo Church 也在独立探索相同的基础问题。1936年，Church 发表了关于不可解数论问题以及判定问题的研究，证明不存在满足要求的通用判定过程。他采用的形式化工具主要与 λ 演算、递归函数有关。[斯坦福哲学百科全书]而 Turing 选择了一条截然不同的道路。他没有首先从复杂的逻辑公式入手。他设想：如果一个人严格按照纸面规则进行计算，他究竟需要什么能力？人能够读一个符号。能够写一个符号。能够记住自己当前处于什么步骤。能够在纸上向左、向右移动。能够按照规则重复操作。于是，Turing 把这种过程抽象成一台极其简单的机器。这台机器后来被称为：Turing Machine，图灵机。它不需要显示器。不需要 GPU。不需要数据库。甚至不需要我们今天熟悉的 CPU 指令集。只需要有限的控制规则，以及在数学模型中可以按需扩展的一条符号纸带。令人惊讶的是：这样一台看起来极其简陋的抽象机器，却足以刻画极其广泛的算法计算过程。这就是为什么图灵机不只是某种古老计算设备的设计图。它首先是关于“什么叫计算”的数学模型。

第三幕：图灵机究竟怎样工作？

一台经典图灵机可以包含四类基本元素。
  • 一条由格子组成的纸带，每个格子保存一个符号。
  • 一个能够读取、修改当前格子的读写头。
  • 一组有限的内部状态。
  • 一套根据当前状态与当前符号决定下一步操作的规则。
例如，我们定义一台非常简单的图灵机。纸带上有几个连续的 1。机器需要在这些 1 的末尾再添加一个 1。假设初始纸带是：
text
1 1 1 □ □ □
其中 □ 表示空格。机器从最左边开始。规则如下：当读到 1，向右移动。当读到 □，写入 1，然后停止。最终得到：
text
1 1 1 1 □ □
这个过程非常简单。但它已经具有算法最基本的特征：确定的状态。确定的输入。确定的转换规则。以及可以识别的停止条件。

实验一：运行一台微型图灵机

微型图灵机实验室

SEARCH
机器向右寻找第一个空格，写入 1，然后进入停机状态。
1▲
1
1
□
□
□
□
□
当前位置是第 1 个格子。读到1，下一步向右移动。
你可能会想：“这台机器也太简单了，怎么可能计算复杂问题？”Turing 的另一项突破就是：程序本身也可以被编码成数据，交给另一台机器读取和执行。这就是 Universal Turing Machine（通用图灵机）的思想。一台适当设计的通用机器，可以读取另一台图灵机的描述与输入，再模拟它的计算过程。这个思想非常重要。因为现代计算机也是如此。同一台电脑可以执行：排序程序。数据库。编译器。视频编码器。神经网络推理程序。它不必为每一种任务重新制造一套硬件。只需要装载不同的程序。于是，“计算机”开始从专门解决某一种问题的机器，转变为能够解释和运行不同算法的通用计算设备。

第四幕：一个看起来完全合理的梦想——能不能写出“万能程序检测器”？

现在我们终于来到全章最重要的问题。假设我们想开发一个程序：
python
halts(program, input_data)
它可以读取任意程序及其输入。然后判断：这个程序最终会不会停止运行？如果会停止，返回：
python
True
如果永远不会停止，返回：
python
False
最重要的是：这个检测器自己必须在有限时间内给出正确答案。对于下面的程序，判断似乎很容易：
python
def example():
    print("Hello")
    return
显然会停止。下面这个程序：
python
def example():
    while True:
        pass
也很容易看出不会停止。那么，是否只要我们的检测器足够聪明，就可以判断所有程序？例如：
python
def example(n):
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
这里的循环行为涉及著名的 Collatz 猜想。对于某个具体输入，我们当然可以运行程序观察。但如果要求证明它对所有正整数输入都能停止，就涉及尚未解决的数学问题。不过，即使我们未来解决了 Collatz 猜想，也不意味着万能停机检测器就会存在。因为更深刻的障碍不是某个具体数学问题太困难。而是：我们可以从“万能检测器存在”这一假设，直接推导出逻辑矛盾。这就是计算理论中经典的：Halting Problem，停机问题。

一个重要的历史考证

严格来说，Turing 1936年的原始论文并没有直接以今天教科书常见的形式提出并证明“任意程序是否停机”的定理。他在原论文中证明了包括特定“无循环机器”判定问题、打印符号判定问题以及一阶逻辑判定问题在内的不可判定性结果。其中，Turing 当时的 circle-free 概念，指机器能持续产生无限的规定输出序列，并不能直接等同于现代教科书中的“程序永远不停机”。2026年发表于 Journal of Logic and Computation 的专门历史论文也强调了这个区别，同时指出 Turing 的符号打印问题与现代停机问题可以有效地相互归约。[Oxford Academic][Oxford Academic]因此，我们下面采用的是现代教材常用的停机问题对角化证明，而不是声称它逐字出现于 Turing 的1936年论文。这一区别不影响其核心数学结论。

第五幕：假设我们真的发明了万能检测器

现在假设有人宣布：“我已经发明了一个万能停机检测程序！”它叫作：
python
HALTS(program, input_data)
能够对任意程序与任意输入给出完全正确的判断，并且自身一定终止。那么我们可以写出一个十分奇怪的新程序。它接收一段程序的代码作为输入。然后先询问万能检测器：“如果这段程序以它自己为输入，会不会停止？”接着故意反着来。

反向程序 D

python
def D(program):
    if HALTS(program, program):
        while True:
            pass
    else:
        return "停止"
请理解它的逻辑。如果检测器预测：“这个程序会停止。”D 就故意进入无限循环。如果检测器预测：“这个程序不会停止。”D 就立刻结束。目前还没有出现矛盾。因为 D 只是根据检测器的结果，采取相反行为。但接下来，我们执行最关键的一步：把 D 自己的代码交给 D。也就是：
python
D(D)
现在会发生什么？

情况一：HALTS 预测 D(D) 会停止

如果：
python
HALTS(D, D) == True
那么 D 根据自己的规则：进入无限循环。也就是说：检测器说会停止。但程序实际上不会停止。检测器错了。

情况二：HALTS 预测 D(D) 不会停止

如果：
python
HALTS(D, D) == False
那么 D 根据规则：直接返回。也就是说：检测器说不会停止。但程序实际上停止了。检测器又错了。我们得到：

万能停机检测器的自我矛盾

检测器预测：会停止D 故意无限循环预测错误
检测器预测：不会停止D 立即返回预测错误
无论检测器给出什么答案，它都会与真实执行结果矛盾。因此，我们最初的假设必定有问题。结论是：不存在能对所有程序和输入都正确、且总能终止的停机判定算法。\boxed{\text{不存在能对所有程序和输入都正确、且总能终止的停机判定算法。}}这就是停机问题不可判定性的经典证明。

为什么这种证明如此强大？

因为它没有讨论某款 CPU 速度够不够快。没有讨论内存究竟有多少。没有讨论程序有多长。它甚至没有要求我们真的找到某个普通程序，并花上一千年运行它。我们只需要假设万能检测器存在，就能构造一个让它必然出错的程序。这是一种：Proof by Contradiction，反证法。其中“让程序分析自己，再反着行动”的构造，还体现了：Diagonalization，对角化。这个思想与 Gödel 的自指编码研究存在深刻联系。

第六幕：为什么运行一万亿步仍未结束，不等于永远不会停止？

现在假设我们放弃万能检测器，采用一种更朴素的方法。把程序运行一段时间。如果它停止，就宣布：“已经确认会停机。”如果它没停止，就宣布：“不会停机。”第二步为什么不可靠？因为程序可能在下一步停止。例如：
python
def slow_program():
    for _ in range(1_000_000_000):
        pass

    return "结束"
它可能非常慢。但仍然会结束。如果检测器只愿意等待一百万步，就可能把它误判为永不终止。因此，有限的执行观察可以确认：程序已经停机。但仅仅因为到目前为止没有停机，不能直接推断：程序永远不会停机。

实验二：运行时间预算并不能解决停机问题

有限步模拟实验室

最多执行100步
允许执行的步数

10

尚未观察到停机
执行了 10 步，程序仍未停止。仅凭这次有限的运行观察，还不能得出它永远不会停止的结论。
程序 C 在本例中是根据程序结构预先定义为无限循环的；但模拟器本身只做有限步观察，并不声称已经解决任意程序的停机判定问题。
这个实验告诉我们一个很重要的区别。“没有找到答案”不等于“证明答案不存在”。例如，我们尝试求解某个复杂数学问题。计算机运行了一天。没有找到反例。这不代表反例不存在。同样，程序运行了很多步。没有停机。也不能自动推断它永不停止。

这意味着程序分析工具毫无价值吗？

当然不是。静态分析器。编译器。形式化验证工具。终止性检查器。它们都可以对大量实际程序进行非常有价值的分析。但这些工具通常需要限制程序语言、限定输入范围、依赖某些可证明的循环不变量，或者允许回答：“无法确定。”只要不要求它们对全部可能的程序都给出正确且终止的二元答案，就不会与停机问题的不可判定性定理矛盾。理论上的不可能性，并不否定特定问题和受限场景中的巨大工程价值。

第七幕：1971年，Stephen Cook 发现了算法的第二道边界

第 30 章配图 6
来源
Stephen A. Cook1939年出生，加拿大多伦多大学计算机科学家，1982年度图灵奖获得者。其研究为计算复杂性理论奠定了重要基础。
现在我们把时间推进到1971年。Turing 已经告诉我们：有些问题不存在通用判定算法。但计算机科学家还面临另一种完全不同的困难。有些问题明明能够通过算法解决，为什么计算机依然可能需要运行数百万年？1971年5月，Stephen Cook 在第三届 ACM 计算理论研讨会（STOC）发表：The Complexity of Theorem-Proving Procedures《定理证明过程的复杂性》。论文发表于第151—158页。[数字对象标识符]这项研究与后来的 Cook–Levin 定理、NP 完全性理论紧密相关。其核心发现改变了人们研究算法困难程度的方式。

两种根本不同的困难

第一种：不存在能够解决全部输入的通用算法。这就是停机问题代表的不可判定性。第二种：存在解决算法，但我们不知道怎样在合理的计算时间内处理所有输入。这就是复杂性理论关心的很多问题。例如：我们知道可以通过枚举所有可能的旅行路线，找到最短路线。但城市数量越多，路线数量增长得越快。如果有10个城市，可能还容易尝试。如果有100个城市，完全枚举就可能非常不现实。这不是因为旅行商问题不存在有限算法。而是因为其朴素求解成本增长得极其迅速。所以，我们必须区分：能否计算？\boxed{\text{能否计算？}}与：计算需要多少资源？\boxed{\text{计算需要多少资源？}}前者是可计算性问题。后者是计算复杂性问题。

第八幕：为什么“验证一个答案”可能比“找到答案”容易得多？

假设学校准备安排一场大型课程考试。有200门课程。某些课程的学生存在重叠。因此，这些课程不能安排在同一个时间段。我们想知道：能不能把全部课程安排进有限的几个考试时段，而且没有冲突？如果某人交给你一张排好的课表，你可以逐项检查：每门课程是否安排了时间。有冲突的两门课程是否安排在不同时间。所有安排是否满足约束。检查的过程可能很快。但如果让你从零开始找到一张完全符合要求的课表，就未必容易。因为有大量可能的组合。这就引出了复杂性理论中两个重要的类别。

P：可以在多项式时间内求解

粗略理解，存在一种确定性算法，其最坏情况下的运行时间能够被输入长度的某个固定次数多项式所界定。例如：O(n)O(n)O(nlog⁡n)O(n\log n)O(n2)O(n^2)这些通常被看作有效算法分析中的重要复杂度类型。严格定义中，P 是判定问题的复杂度类，讨论输入编码长度以及确定性计算模型。

NP：给定正确证书，可以在多项式时间内验证

例如：我们问：“是否存在一套符合全部约束的排课方案？”如果有人给出一张候选课表，我们可以在多项式时间内检查其是否有效。那么，这类“存在某个可有效验证的解”的判定问题，就体现了 NP 的基本含义。这里必须特别纠正一个常见误解：NP 不是 Non-Polynomial（非多项式时间）的缩写。它来自：Nondeterministic Polynomial Time，非确定性多项式时间。对经典 NP 判定问题，我们可以等价地把它理解为：如果答案为“是”，存在长度受多项式约束的证书，可以在多项式时间内验证。并且：P⊆NP\boxed{P\subseteq NP}因为一个能够高效求解的问题，其“是”答案当然也能够高效验证。真正尚未解决的问题是：P=?NP\boxed{P\overset{?}=NP}即：所有能够高效验证正确答案的 NP 判定问题，是不是也都能够高效找到答案？截至2026年10月，Clay Mathematics Institute 仍然将 P vs NP 列为未解决的千禧年数学难题。[Clay Mathematics Institute]

第九幕：一个只有三个变量的问题，为什么能够连接整个计算复杂性理论？

我们先不研究200门课程。使用一个更小的逻辑问题。假设有三个布尔变量：A,B,C∈{True,False}A,B,C\in\{True,False\}我们希望找到一种赋值，使下面的逻辑公式成立：F=(A∨B∨C)F=(A\lor B\lor C)∧(¬A∨B∨¬C)\land(\neg A\lor B\lor\neg C)∧(A∨¬B∨C)\land(A\lor\neg B\lor C)其中：∨\lor 表示“或”。∧\land 表示“且”。¬\neg 表示“非”。我们可以写一个简单程序，枚举三个变量的所有组合。共有：23=82^3=8种可能。只要找到一个使公式为真的组合，就证明：这个公式是可满足的。这种问题叫作：SAT，Boolean Satisfiability，布尔可满足性问题。

实验三：你来寻找一个满足条件的赋值

SAT 可满足性实验室

2/3 条子句成立
改变 A、B、C 的真假，寻找一个能让全部三条子句同时成立的组合。
A
B
C
A ∨ B ∨ C
False
¬A ∨ B ∨ ¬C
True
A ∨ ¬B ∨ C
True
目前还有 1 条子句不成立。当前赋值不能作为“可满足”的证书，但这不意味着整个公式不可满足。
对于三个变量，只有8种组合。枚举并不困难。但如果变成30个变量：230=1,073,741,8242^{30}=1,073,741,824超过十亿种赋值。如果变成100个变量：21002^{100}就已经是一个极其庞大的数字。当然，这并不意味着所有100变量的 SAT 实例都需要枚举完整的 21002^{100} 种组合。实际求解器利用约束传播、冲突学习、启发式搜索等方法，经常可以高效处理规模远大于100变量的具体实例。但是，对于一般 SAT 问题，我们仍然不知道是否存在一个能够对所有输入都在多项式时间内给出答案的算法。

为什么 SAT 的地位如此特殊？

Cook 1971年的论文建立了复杂性归约理论的重要基础。在现代标准表述下，Cook–Levin 定理证明 SAT 是 NP 完全问题。严格的历史表述还应指出，Cook 的原论文采用了当时的可约性框架，并以逻辑重言式等形式组织论证；现代教材常将其转换为 SAT 的多项式归约表述。[数字对象标识符][Stanford University]NP 完全问题最重要的性质是：如果找到一个多项式时间算法来解决其中任意一个 NP 完全问题，那么可以通过多项式归约解决所有 NP 问题。于是就会得到：P=NPP=NP这就是 NP 完全性理论惊人的力量。它不是证明这些问题永远没有高效算法。而是说明：许多表面完全不同的问题，在最坏情况的计算难度上具有深刻联系。

第十幕：1972年，Richard Karp 把21个不同领域的问题联系到了一起

第 30 章配图 7
来源
Richard M. Karp1935年出生，美国计算机科学家，1985年度图灵奖获得者。其1972年的研究极大推动了 NP 完全性理论的发展。
1972年，Richard Karp 发表：Reducibility Among Combinatorial Problems《组合问题之间的可归约性》。论文收录于 Complexity of Computer Computations，第85—103页。[dblp]在这篇研究中，Karp 通过一系列多项式归约，展示了21个经典组合判定问题的 NP 完全性。这些问题来自完全不同的领域。图着色。哈密顿回路。集合覆盖。背包。任务安排。整数规划。它们在现实中的表现可能非常不同。一个是在图中寻找路径。另一个是在预算范围内选择项目。还有一个是在不同约束下安排任务。但 Karp 发现：可以把一个问题的实例有效转换为另一个问题的实例，使它们的“是或否”答案对应。这就叫作：Reduction，归约。

为什么归约如此重要？

假设我们已经知道问题 A 很难。现在想判断问题 B 是否也很难。如果能证明：A≤pBA\leq_p B即存在一种多项式时间转换，把 A 的每个实例转成 B 的实例，并保持答案对应。那么，如果我们未来拥有一个高效算法解决 B，也就能够高效解决 A。这里的方向很重要。A 归约到 B，意味着 B 至少在这种复杂性意义上有能力解决 A。所以，要证明 B 是 NP-hard，常见做法是从一个已知 NP-hard 问题归约到 B，而不是反过来。

这与我们之前学过的算法有什么关系？

你可能还记得：第九章的贪心算法。第十章的回溯。第二十章的数据库事务与约束。以及后来讨论的任务调度、资源分配和图结构。其中很多问题都存在组合搜索空间。但我们不能仅凭“用了回溯”就断定它是 NP 完全问题。也不能因为“看起来像背包”就忽略具体限制。例如，某些问题在一般情形下很难，但在树结构、固定维度、小整数范围等受限情形下，可能存在非常有效的算法。因此，理解复杂性类别之后，我们反而应该更加谨慎：算法的复杂性不仅取决于问题的名字，还取决于它的精确定义、输入编码方式和允许的约束。

第十一幕：计算机为什么会遇到“组合爆炸”？

我们现在把抽象的 NP 完全性，转成非常直观的数字。假设你面对一个有 nn 个二元选择的问题。每个选择只有：是。否。两种可能。那么总组合数就是：2n2^n当：n=10n=10只有：210=10242^{10}=1024种组合。当：n=20n=20就变成：220=1,048,5762^{20}=1,048,576当：n=40n=40则达到：240=1,099,511,627,7762^{40}=1,099,511,627,776超过一万亿。这就是：Combinatorial Explosion，组合爆炸。

实验四：指数增长到底有多可怕？

组合爆炸实验室

输入规模 n = 20
多项式工作量n3n^3

8,000

指数工作量2n2^n

1,048,576

假设每秒执行一亿个基本操作
多项式计算耗时不足1毫秒
指数计算耗时10.49 毫秒
这是固定每秒一亿次操作、分别需要 n³ 和 2ⁿ 次操作的纯数学演示。不同算法与硬件具有不同成本，且指数枚举不是所有 NP 问题实例都必须采用的方法。
你会发现：当 nn 较小时，指数算法似乎并没有那么可怕。但输入规模增长后，运行时间很快就会变得不可接受。这就是为什么算法设计中如此重视：降低指数。减少搜索分支。提前剪枝。利用动态规划复用子问题。寻找特殊结构。采用近似或启发式算法。我们以前学习过的所有这些技巧，现在都有了一个更大的背景。它们不是为了让代码看起来更聪明。而是为了在不断增长的搜索空间中，找到一条实际可行的计算道路。

第十二幕：如果一个问题太困难，为什么不允许算法“差不多正确”？

这是算法工程最重要的转变之一。假设你是一名物流调度工程师。每天需要安排几十辆车，为数百个客户配送货物。你想找到运输成本绝对最低的方案。如果精确求解需要数月，业务根本无法接受。于是，你改变问题：我不一定要求绝对最优，但需要一个在有限时间内足够好的方案。这就引出了几种不同的算法策略。

近似算法（Approximation Algorithms）

有些优化问题可以设计具有数学性能保证的近似算法。例如，对某些满足三角不等式的旅行商问题，可以给出最优成本的固定倍数上界。这种算法不一定找到真正最优解。但能够保证结果不会比最优解差得超过某个理论比例。

启发式算法（Heuristics）

另一些方法会利用经验或问题结构，尝试快速找到高质量解。例如：局部搜索。模拟退火。遗传算法。贪心初始化后进行改进。这些方法可能表现很好，但不能因为一次实验效果不错，就宣称它们对全部输入都具有同样的最优性保证。

随机化算法（Randomized Algorithms）

随机化可以帮助算法避开某些固定输入结构，或者以概率方式改善性能。我们在第十八章见过跳表。节点高度通过随机抽样决定。其搜索、插入和删除具有良好的期望复杂度。但跳表并不会因此获得与严格平衡树完全相同的最坏情况保证。

在线算法（Online Algorithms）

某些问题的未来输入根本无法提前知道。例如：缓存替换。任务调度。网络流量分配。这时，算法只能根据目前已经观察到的信息作出决策。第十九章的 LRU、FIFO 和 Clock，就属于这类工程问题的重要实例。我们不能要求一个不知道未来的缓存算法，在每一段访问序列上都与知道全部未来的 OPT 算法一样好。这些策略之间的区别告诉我们：在无法同时得到完美解、低成本和强保证时，算法设计必须明确选择自己愿意承担哪种代价。

第十三幕：1950年，Turing 提出了另一个问题——机器能思考吗？

第 30 章配图 8
来源
1936年，Turing 研究的是：“什么能够被机械化计算？”十四年后，他把目光投向了一个更加令人困惑的问题。1950年10月，Turing 在哲学期刊 Mind 发表：Computing Machinery and Intelligence《计算机器与智能》。在这篇论文中，他讨论了机器智能，并提出后来广为人知的模仿游戏（Imitation Game）。论文发表于第59卷第236期，第433—460页。[Oxford Academic]这篇论文与1936年的可计算性研究有一个很有意思的联系。1936年，Turing 证明：通用算法的能力存在严格的数学边界。1950年，他又认真研究：在这些边界之内，机器究竟能够展现什么样的智能行为？这不是矛盾。因为：一个系统不可能解决所有数学问题，不代表它不能在许多复杂任务上表现得极其出色。

那么，今天的 AI 能否绕过停机问题？

如果一个 AI 系统本身仍由通常意义上的算法计算过程构成，那么仅仅因为它使用了神经网络、大模型或智能体工作流，就不会推翻可计算性理论。AI 可以：发现代码中的许多错误。寻找程序终止性的证明。自动生成测试。为复杂优化问题寻找较好的解。提出数学猜想与证明思路。但它不能被保证对所有可能的程序，都给出绝对正确且有限时间终止的停机判断。它有时也会预测错误。如果我们要求它：“必须对每个可能的输入给出确定、完整而正确的结论。”那么原来的不可判定性问题仍然存在。更强大的求解能力，并不等于消除了所有理论限制。同样，P 与 NP 的问题也没有因为大模型出现就自动解决。现代 AI 可能在许多具体 SAT、规划和程序合成问题上发挥作用。但在没有严格数学证明之前，不能把某个模型在测试集上的优异表现，直接提升为一个复杂性类别已经被证明相等或不相等的结论。

AI 更重要的贡献可能在哪里？

在现实工程中，AI 可以帮助我们构建一个更好的求解过程。例如：先识别问题类型。选择合适的算法。生成候选解。使用确定性程序验证约束。发现错误后重新搜索。把结果与证据一同交给用户。这种设计把两种能力结合起来：模型负责提出可能有价值的候选方案。形式化规则、测试或确定性求解器负责验证可验证的部分。这比单纯依赖模型说“我认为答案正确”，更有工程价值。因为对于许多问题：寻找答案可以采用启发式方法，而验证答案可以采用严格的方法。但也要区分：有些问题即使给出候选答案，也不能靠一个简单的有限检查证明其所有相关性质。停机问题正是提醒我们，验证系统本身也有适用边界。

第十四幕：三十章以后，我们终于可以重新定义“好算法”

现在回顾整个系列。第一章，我们研究数组与链表。当时的问题是：怎样保存数据，才能更快地访问和修改？后来，我们研究哈希表和树。问题变成：怎样组织数据，才能避免反复搜索？在排序、动态规划、贪心、回溯等章节中，我们开始关心：怎样利用问题结构，减少不必要的计算？再后来，我们进入分布式系统。研究一致性哈希、Paxos、Raft、数据库事务、死锁、CRDT、向量时钟和分布式快照。问题变得更加复杂：怎样让多台机器在可能故障、网络延迟、时钟不一致的情况下，仍然保持足够可靠的行为？然后，我们研究 MapReduce 和 PageRank。开始理解：怎样把大量简单操作组合起来，构成处理庞大数据集的系统？现在，这些问题终于汇聚到同一个地方。什么才叫一个好算法？它不是必须最快。不是代码必须最短。也不是一定要使用最新的 AI 模型。更准确地说，一个好算法需要首先回答：它究竟提供了什么保证？
正确性对于规定的输入与前提，算法是否产生满足要求的结果？这种保证来自严格证明、概率界限，还是只是经验观察？
复杂度输入增长后，时间、内存和通信成本怎样增长？是最坏情况、平均情况，还是期望性能？
故障模型程序停止、机器断电、消息重复、网络分区或者输入不合法时，算法仍然承诺什么？
现实约束是否允许近似答案？是否能够接受短暂不一致？是否必须满足确定的截止时间？为换取性能愿意使用多少额外资源？
从这个角度看，前面二十九个章节中出现的各种技术，实际上是在解决不同的限制。Bloom Filter 允许一定概率的假阳性，以节省空间。跳表通过随机化，换取简洁的有序索引维护。LRU 根据过去的访问历史猜测未来。数据库事务通过日志和并发控制维持状态转换。CRDT 利用代数性质降低某些分布式更新的协调需求。MapReduce 通过任务重试，降低单台机器故障的影响。PageRank 通过随机游走与幂迭代，在循环依赖中寻找稳定分布。而 Turing 和 Cook 的研究则从最深层提醒我们：并不是所有限制都可以单靠更好的硬件消除。有些是数学上的不可能性。有些是尚未解决的复杂性难题。还有些则是可以由工程师在性能、可靠性和成本之间作出选择的权衡。这三种情况必须分清。

终章最终挑战：你已经能够判断算法问题的边界了吗？

现在给出四个问题。它们看起来都属于“让计算机解决问题”。但它们的理论性质完全不同。

算法边界诊断器

最终测验
把100万个整数按照从小到大排序。
这里最值得记住的是第四个问题。虽然“判断任意程序是否停机”不可判定，但“判断程序是否在前1000步内停止”却是可判定的。我们只是增加了一个限制条件。一个不可判定的问题，在加入适当的边界后，就可能变成一个可以直接计算的问题。同样，一个一般情形下非常困难的优化问题，在输入规模、图结构、数值范围或允许误差受到限制后，也可能得到高效解决。这正是优秀算法工程师最重要的能力之一：不只寻找答案，还懂得重新定义一个真正可以解决的问题。

全系列最后一幕：从一条链表，到人类对计算能力的理解

1936年，Turing 还没有见过今天的个人计算机。没有互联网。没有云计算。没有 GPU 集群。没有深度学习大模型。但他研究的问题，却贯穿了此后九十年的计算机科学。如果我们回看整个系列，会发现一条非常清晰的历史路线。
《算法的故事》：从数据结构到计算的边界
  • 学会组织数据数组、链表、栈、队列、哈希表、树与图。最初的问题，是让数据能够被正确而高效地保存和访问。
  • 学会组织计算排序、动态规划、贪心、回溯与字符串匹配。我们开始寻找减少重复劳动、利用问题结构的方法。
  • 学会接受权衡压缩、密码学、布隆过滤器、跳表和缓存算法。我们开始使用概率、额外空间、随机化与近似，换取所需要的性能。
  • 学会让系统可靠地合作一致性哈希、分布式共识、数据库事务、死锁、CRDT、向量时钟与分布式快照。我们发现，多个局部正确的程序并不必然组成一个全局正确的系统。
  • 学会处理大规模信息MapReduce、PageRank与搜索索引。我们把数据、图、概率和并行计算结合起来，让大型信息系统成为可能。
  • 最终认识计算的边界Turing 的可计算性、Cook 与 Karp 的复杂性研究，以及至今未解决的 P 与 NP 问题。我们终于知道：不是所有问题都能够被保证求解，也不是所有可以求解的问题都能高效求解。
这条路线，实际上也是计算机科学从理论走向工程、再由工程反过来推动理论的过程。算法的发展并不是不断抛弃旧知识。恰恰相反。今天的大型 AI 系统，仍然需要数组、哈希表和图。仍然需要排序、搜索、并行计算。仍然需要缓存管理。仍然需要数据库事务。仍然需要分布式一致性协议。仍然需要故障恢复。而且，不管模型的参数有多少，不管计算集群有多少块 GPU，它仍然需要遵守算法与计算模型的基本规律。

终章结语：算法的力量，来自对边界的理解

我想用一个思想，为这三十章画上句号。假设我们有两名程序员。第一名程序员相信：“只要计算机足够强大，就一定能够解决任何问题。”第二名程序员知道：有些问题不可判定。有些问题已知可高效解决。有些问题是否存在高效算法，至今尚未得到证明。还有些问题虽然无法获得理想的精确解，但可以利用约束、近似、随机化或者人机协作，得到满足实际需求的结果。你会发现：第二名程序员反而可能构建出更可靠的系统。因为他知道，什么时候应该追求数学上的严格正确。什么时候可以接受概率性的性能保证。什么时候应该限制输入或调整问题定义。什么时候可以采用近似方法。什么时候必须承认：“根据现有信息，还无法确定。”这种认识并不是对算法能力的否定。而是让算法从一种单纯的计算技巧，变成一种严谨的问题解决方法。算法最伟大的地方，不是承诺解决一切。而是让我们能够准确区分：什么可以解决，什么值得计算，什么需要权衡，以及什么必须承认存在边界。1936年，Turing 并没有给人类制造一台能够回答所有问题的机器。相反，他证明了这样的万能计算梦想存在根本限制。但正是这种对计算能力的严格定义，帮助奠定了后来通用计算机、程序语言、算法理论与计算复杂性研究的基础。这也是整个《算法的故事》最值得留下的一句话：
真正理解算法的人，不仅知道怎样让计算机工作，还知道应该要求计算机证明什么、计算什么，以及什么时候不能假装自己已经得到了答案。

第三十章知识总结

概念最重要的结论
可计算性研究什么能够由算法计算
图灵机形式化的通用计算模型
通用图灵机程序可以被编码为数据并被模拟
Church–Turing Thesis关于有效可计算方法与图灵可计算性的论题，不是普通形式系统内部的已证定理
停机问题任意程序是否停机，不存在通用总判定算法
不可判定性理论上不存在符合要求的通用判定算法
对角化通过自指构造揭示通用判定假设的矛盾
P可以在确定性多项式时间内判定的问题类
NP“是”答案具有多项式时间可验证证书的判定问题类
NP-CompleteNP 中能够承载全部 NP 问题多项式归约难度的问题
P vs NP截至2026年仍未解决的重大数学问题
组合爆炸搜索空间可能随输入规模指数增长
近似与启发式在计算资源有限时寻找实用解
正确性保证必须明确适用条件、错误范围与故障假设

终章原始论文与权威研究资料

Alan Turing（1936）：《On Computable Numbers, with an Application to the Entscheidungsproblem》Stanford Encyclopedia of Philosophy：Alonzo Church 与可计算性研究《Journal of Logic and Computation》（2026）：Turing 1936年论文与现代停机问题的历史辨析Stephen Cook（1971）：《The Complexity of Theorem-Proving Procedures》Richard Karp（1972）：《Reducibility Among Combinatorial Problems》Clay Mathematics Institute：P vs NP 官方问题说明与研究状态Alan Turing（1950）：《Computing Machinery and Intelligence》Stanford Encyclopedia of Philosophy：Church–Turing 论题及其准确含义

《算法的故事》

第一季 · 人类如何驯服数据

第三十章 · 全系列完

从一条链表开始，以计算的边界结束。