上一篇：（三）怎么证明它是对的——讲怎么确认程序是对的。 这一篇：讲有些事，程序根本做不了。

耗时：读完约 45 分钟，动手约 1.5 小时。

开头：先给你一个"不可能"的任务

写一个程序，它读入任意另一个程序，然后回答：

这个程序会停下来吗？

这个任务有个名字，叫停机问题（Halting Problem）。

直觉上你觉得它能做——“我跑一遍不就知道了吗？“但如果那个程序是：

while True:
    pass

你跑它，它不停。可是你等了 10 分钟，它还在跑——你怎么知道它是"永远不会停”，还是"再等 1 分钟就停”？

你永远无法确定。 因为可能有个程序要跑 10¹⁰⁰ 步才停。你把等待上限设成多少都没用。

这一篇要做的，是把"我觉得做不了"变成"数学上证明做不了"。而且这个证明会一路推出一个惊人的结论：

能计算的函数，在数学上存在的所有函数里，占比是 0。

也就是说，绝大多数数学上定义清楚的问题，根本没有任何程序能解决。

这不是算力不够，不是程序员不行，不是 AI 还不够强。这是数学上的不可能，跟"2 是偶数还是奇数"一样确定。

一、先建立直觉：两个无穷，“一样大"吗

要理解停机问题，得先理解一件事：无穷和无穷不一样大。

这反直觉。你会觉得"无穷就是无穷”。但康托尔（Cantor）证明了：有些无穷，比别的无穷严格更大。

可数：能排成一列的无穷

自然数 0, 1, 2, 3, ... 是最小的一种无穷，叫可数无穷。

关键判断标准：能不能把全体元素排成一列（编号 0, 1, 2, 3, …），一个不漏。

整数和自然数一样多

看起来整数比自然数多一倍（多了负数），其实一样多。配对：

自然数 n整数
00
1−1
21
3−2
42
5−3
……
n 是偶数 → n/2
n 是奇数 → −(n+1)/2

每一个自然数，恰好对应一个整数，一个不重、一个不漏。 所以两者"一样多"。

（实测：n=0..11 配对到 0, −1, 1, −2, 2, −3, 3, −4, 4, −5, 5, −6，回代无误。）

有理数也和自然数一样多

有理数是"两个整数之比"。它稠密——任意两个有理数之间还有无穷多个有理数。你会觉得它"更多"。

但它也可数。方法叫康托尔配对（Cantor pairing）：把分数 (分子, 分母) 排成对角线：

0/0 → 0
0/1 → 2    1/0 → 1
0/2 → 5    1/1 → 4    2/0 → 3
0/3 → 9    1/2 → 8    2/1 → 7    3/0 → 6
...

每个正有理数都能拿到一个唯一的自然数编号。 所以有理数也可数。

到这里，你可能会以为"无穷就是无穷，都一样"。别急，下一个就翻了。

二、康托尔的对角线：实数不可数

现在问：实数（0 到 1 之间的所有小数）可数吗？

康托尔说：不可数。 他用了一个漂亮到惊人的方法——对角线法。

证明（反证法）：假设 0 到 1 之间的实数可以排成一列，编号 0, 1, 2, …。把它每个写成无限小数，摆成一个表：

第 0 个: 0.a₀₀ a₀₁ a₀₂ ...
第 1 个: 0.a₁₀ a₁₁ a₁₂ ...
第 2 个: 0.a₂₀ a₂₁ a₂₂ ...
...

现在取对角线上的数字 a₀₀, a₁₁, a₂₂, ...，把每一个都改一下（比如 0 改 1，非 0 改 0），得到一个新数：

0.(改a₀₀)(改a₁₁)(改a₂₂)...

这个新数不在表里。 因为它跟第 0 个数在第 0 位不同，跟第 1 个数在第 1 位不同，跟第 n 个数在第 n 位不同……

它跟表里的每一个数都不一样。 所以这个"列出了所有实数"的表，漏掉了至少一个。

矛盾。 所以实数不可数。

我用 0/1 序列实测了一遍（原理相同，数字换成 0/1）：

第 0条: 1101000011...  对角线第0位=1 翻转=0  ← 第0位不同
第 1条: 0011000011...  对角线第1位=0 翻转=1  ← 第1位不同
第 2条: 0010110111...  对角线第2位=1 翻转=0  ← 第2位不同
...
翻转后的序列: 0100001111

它跟第 0 条不同、跟第 1 条不同、跟每一条都不同。

康托尔对角线法一句话：给定任何"声称列全了"的列表，我都能造出一个不在列表里的东西。

这个"我都能造出一个"的技巧，接下来要再出场两次——它是整个"不可能"系列的核心武器。

三、程序是可数的，函数是不可数的

现在把刚才的结论用到计算机上。

程序：可数

一个程序，本质是有限长的字符串（一堆字符）。字符串可以唯一编码成自然数：

"while True: pass" → 158720268612639616323219323269696025459（39 位）

这叫哥德尔编号。所以：

所有程序可以排成一列：程序₀, 程序₁, 程序₂, … 程序的数量 = 可数无穷。

（有限长字符串按"长度 + 字典序"枚举，长度 0 有 1 个，长度 1 有 2 个，长度 2 有 4 个……全部有限长字符串 = 可数。）

函数 N→N：不可数

一个"函数"，是把每个自然数映射到一个自然数的规则。这种规则有多少？

用对角线法：假设所有函数 f₀, f₁, f₂, ... 排成一列。构造：

g(x) = fₓ(x) + 1

g 跟 f₀ 在点 0 不同，跟 f₁ 在点 1 不同……跟每一个 fᵢ 至少在一个点上不同。

所以 g 不在列表里。函数不可数。

（实测：g(3) = f₃(3)+1 = 13，而 f₃(3) = 12，确实不同。）

两边一拼，结论出来了

程序的数量 = 可数
函数的数量 = 不可数

所以：函数远比程序多。

绝大多数函数，没有任何程序能计算它。 能算的东西，在数学上存在的东西里，占比是 0（用测度的语言说）。

这不是"还没发明出算法"，是"不可能存在算法"。 因为程序根本不够用——函数有不可数多个，程序只有可数多个，你怎么排都不可能一一对应上。

四、停机问题：正式证明

现在可以证明开头那个问题了。

要证明的

不存在一个程序 H(P, x)，能对任意程序 P 和输入 x，正确回答"P 在 x 上是否停机"。

证明（反证法 + 对角线）

假设存在这样的 H。

用 H 构造一个新程序 G：

G(x):
    if H(G, x) == "会停":
        while True: pass    # 偏不停
    else:
        return 0            # 偏停

现在问一个致命的问题：G(G) 会停吗？

  • 如果 H(G, G) 说"会停"，那么 G(G) 进入 while True，不停。→ H 错了。
  • 如果 H(G, G) 说"不停"，那么 G(G) 直接 return，停了。→ H 又错了。

两种情况下，H 都错。

所以假设"存在完美的 H"推出矛盾。结论：H 不存在。

这一步为什么这么强

注意这个证明的结构：它没有说"H 很难写"，它说的是"H 在逻辑上不可能存在"。

因为它用了一个"自指"——让程序 G 去问 H"我会怎么样"，然后反着做。

这个"自指 + 反着做"的技巧，就是康托尔对角线的程序版。

康托尔造一个"不在列表里的数"，图灵造一个"让 H 无法判断的程序"。同一个武器，两个战场。

为什么"跑一遍"不行

你可能会说：“我可以设个超时，跑 10 秒没停就算它不停。”

问题：10 秒只是你选的任意上限。

  • 有些程序 10 秒内停，你能正确判断"停"
  • 有些程序 10 秒内没停，但 11 秒时停 → 你误判了
  • 有些程序永远不停，你永远等不到

“步数上限"这个方法，永远只能回答"上限内停了"或"上限内没停”，它永远无法区分"上限内没停"和"永远不会停"。

我实测了一个天真的判断器：

程序1（有限求和）: 3 秒内停了 → 判断"会停" ✅
程序2（while True）: 3 秒内没停 → 判断"不停机（上限内没停）"  ← 它其实没说"永远不会停"

看到区别了吗：它只能诚实地说"上限内没停"，不能真的证明"永远不停"。 你把上限加到 10 年，问题原样存在，只是推迟了。

五、这跟 AI 有什么关系

这是这篇最想说的一句话：

停机问题的不可判定性，对任何"智能"都成立。AI 也不例外。

因为证明里没用任何关于"人类"“程序"“图灵机"的特殊性质。它只说了一件事：

只要你的判断器能用程序表达（能输入、能输出、按规则运行），就能用"自指"构造出让它自相矛盾的问题。

AI 再强，它也是一个程序（或者等价于程序的东西）。所以同样存在 AI 永远回答不了的问题。

这不是说 AI 没用。这是说：“无所不能的 AI"在数学上是不存在的。 跟"永动机在物理上不存在"一样，是硬约束，不是暂时的技术瓶颈。

理解这一条，你就不会再被"AI 会不会取代一切"这种问题带偏。 会取代的是"能算的那部分”。不能算的那部分，从数学上就没人能取代，包括人自己。

六、Rice 定理：不是停机问题一个，是一整片

停机问题只是开头。Rice 定理把它推广成一个通用结论：

程序行为的任何"非平凡"性质，都不可判定。

“非平凡” = 有的程序有这个性质，有的程序没有。

这意味着下面这些问题全部不可判定（不存在任何算法）：

你想问的可判定吗
这个程序会停吗？❌ 停机问题
这个程序会不会打印出 “hello”？❌
这个程序会不会崩溃？❌
这个程序有没有 bug？❌
这个程序是不是永远返回正数？❌
两个程序是不是干同一件事？❌
这段代码里有没有死代码？❌

注意"这个程序有没有 bug"也在里面。 这是最扎心的一条——它意味着：不存在一个能检查所有 bug 的完美工具。

（这不是说静态分析、测试、lint 没用。它们是"可判定的子集"上做近似——它们能查出一部分问题，但永远查不出全部，而且这个"查不全"是数学保证的，不是工具不够好。）

对照：哪些是可判定的

不是所有问题都不可判定。下面是可判定的（有确定答案的算法）：

问题可判定吗
一个数是不是素数✅
两个正则表达式是否等价✅
一个命题逻辑公式是否可满足（SAT）✅（虽然可能很慢）
图灵机在 n 步内会不会停✅（有限模拟 n 步）

看出规律了吗：

  • 加一个"有限"限制，往往就可判定了。（“n 步内"就是有限）
  • 去掉"有限”、问"任意"情况，往往就不可判定了。（“任意输入"“任意步数”）

这是整个计算理论的一条暗线：有限的世界可判定，无限的世界常常不可判定。 这跟第二篇的"离散 vs 连续"是同一个思想在更高一层的回声。

七、忙海狸：一个"定义明确但算不出来"的数

停机问题还有一个惊人的副产品，叫忙海狸函数（Busy Beaver）。

定义：BB(n) = 一个 n 状态的图灵机，在停机之前，最多能走多少步。

定义完全清楚，没有任何模糊。但它的值：

BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) ≥ 47,176,870
BB(6) ≥ 10^36534

BB(6) 已经比宇宙里的原子总数（约 10⁸⁰）还大得多。

关键性质：

BB(n) 增长得比任何可计算函数都快。

为什么？因为如果 BB(n) 可计算，你就能用它解停机问题（模拟 n 状态图灵机 BB(n) 步，停了就是会停，没停就是永不）。而停机问题不可解。所以 BB(n) 不可计算。

BB(n) 是"存在、明确、但永远算不出来"的完美例子。

它帮你理解一个深刻的区分：

  • 可计算 ≠ 被定义
  • 一个东西可以定义得清清楚楚，但没有程序能算出它

八、三层"不可能”，回顾整个专题

到这里，四篇讲完了一条完整的线。把它们叠起来看：

篇讲的是结论
（一）一个数数是格点，会溢出、会漂
（二）一堆东西离散化有确定规律，可算可防
（三）对错测试覆盖有限，证明覆盖全部
（四）能不能算有些东西根本没有程序能算

注意第三篇和第四篇的关系，这是一个漂亮的递进：

  • 第三篇说：测试覆盖不了所有情况——但至少，程序存在，你可以证明它对。
  • 第四篇说：有些函数，程序根本不存在，你想证也没东西可证。

第三篇是"难”，第四篇是"不可能”。这是两个量级。

所以整个"计算机数学"的骨架，可以收成一句话：

先搞清楚"能不能算"（第四篇），再搞清楚"算得多快"（下一篇），然后才谈得上"算得对不对"（第三篇）。 顺序反了，就是白忙。

九、动手：五个实验

实验 1：对角线造一个"不在列表里"的数

import random
random.seed(5)

seqs = [[random.randint(0,1) for _ in range(20)] for _ in range(8)]

翻转 = [1 - seqs[i][i] for i in range(8)]
print("8 条 0/1 序列，对角线翻转后：")
print("".join(map(str, 翻转)))
for i in range(8):
    same = seqs[i][i] == 翻转[i]
    print(f"  第 {i} 条的第 {i} 位 = {seqs[i][i]}, 翻转后 = {翻转[i]} → {'相同' if same else '不同'}")
print("→ 它跟每一条都在对角线位置不同，所以不在列表里")

亲手看到"造出来的那个不在列表里"，你就理解了康托尔。

实验 2：自然数 ↔ 整数 配对

def 自然数转整数(n):
    return n//2 if n % 2 == 0 else -(n+1)//2

for n in range(12):
    print(f"自然数 {n:2d} ↔ 整数 {自然数转整数(n):3d}")

看到负数也被一一配到了自然数，你就理解"可数"了。

实验 3：程序可数、函数不可数

# 程序可数：有限长字符串能编号
s = "while True: pass"
print(f"'{s}' → {int.from_bytes(s.encode(), 'big')}")
# 一个 39 位的数 —— 每个程序都有一个编号

# 函数不可数：对角线
fs = [lambda x, i=i: i*x + i for i in range(20)]
g = lambda x: fs[x](x) + 1
print(f"g(3) = {g(3)}, 但 f_3(3) = {fs[3](3)} → 不同")
print("g 跟每个 f_i 至少一点不同 → 函数不可数")

实验 4：自指程序打败任何判断器

# 停机问题的核心：自指 + 反着做
# 假设有一个判断器 H(程序, 输入)，返回"会停"或"不停"
# 构造 G：如果 H 说我会停，我就死循环；否则我停
# 则 H(G, G) 无论怎么答都错。

# 用文字形式走一遍逻辑：
print("G(G) 停机 ⟺ H(G,G) 说'不停' ⟺ G(G) 不停机  ← 自相矛盾")
print("所以 H 不存在")

实验 5：忙海狸为什么不可计算

# BB(n) 增长比任何可计算函数都快
print("BB(1..6) ≈ 1, 6, 21, 107, ≥4.7×10^7, ≥10^36534")
print("宇宙原子数 ≈ 10^80")
print("BB(6) = 10^36534 >> 10^80")
print("如果 BB 可计算 → 能解停机问题 → 矛盾 → 所以不可计算")

十、带走的东西

一句话：

能算的东西是少数——程序只有可数无穷个，函数有不可数无穷个，所以绝大多数问题没有程序能解，而且这是数学保证的，不是技术不够。

三句话：

  1. 无穷分大小：自然数、整数、有理数都可数（一样多），实数不可数（严格更多）。判断标准是"能不能排成一列"。
  2. 停机问题不可判定：用"自指 + 反着做"（康托尔对角线的程序版）可以证明，不存在能判断所有程序是否停机的程序。
  3. Rice 定理是通用版：程序行为的任何非平凡性质都不可判定——包括"有没有 bug"。所以不存在完美 bug 检查器，这不是工具不行，是数学不行。

一条关于 AI 的结论（这篇最想让你记住的）

“无所不能的 AI"在数学上不存在。 停机问题对任何"能用程序表达的判断器"都成立，AI 也不例外。 会取代的是"能算的那部分”；不能算的那部分，人取代不了，AI 也取代不了。

下一篇

（五）算得多快——这一篇其实在 /cs/analysis/ 已经讲过一部分（大 O 和复杂度），所以这里不重复。

我会写的是它没覆盖的那块：P vs NP、为什么"验证一个解"和"找到一个解"是两件完全不同的事、以及为什么这个问题值 100 万美元。

想先看哪条线，你定：直接写（六）概率，还是补一篇（五）的 P/NP 深度版？

深水区

  • 计算理论主干：Michael Sipser《Introduction to the Theory of Computation》——停机问题、可判定性、复杂度全在里面，是标准教材。
  • 停机问题原始论文：Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem（1936）。这一篇奠定了整个计算机科学，值得知道它存在，哪怕不读原文。
  • 康托尔对角线：Georg Cantor 1891 年那篇关于实数不可数的短文。是"对角线法"的起点。
  • Rice 定理：Henry Gordon Rice 1953 年的论文，一句话把停机问题推广成一大片不可判定性。

这些我不做页码引用——不同版本页码不同，写了就是骗你。按书名和章节找。

附：本篇所有数字的来源

全部本机跑出来：Ubuntu / Python 3.8 / x86-64。

  • 康托尔对角线：8 条随机 0/1 序列，翻转后跟每一条都在对角线位置不同（构造成功）
  • 自然数↔整数配对：n=0..11 ↔ 0,−1,1,−2,2,−3,3,−4,4,−5,5,−6（回代无误）
  • 康托尔配对函数：(a,b) → (a+b)(a+b+1)/2 + b，把正有理数一一编号
  • 函数对角线：g(x)=fₓ(x)+1，g(3)=13 vs f₃(3)=12，确实不同
  • 程序哥德尔编号："while True: pass" → 158720268612639616323219323269696025459（39 位）
  • 停机判断器演示：有限求和程序 3 秒内停；while True 3 秒内没停（只能回答"上限内没停"，无法证明"永不"）
  • 忙海狸：BB(1..6) = 1, 6, 21, 107, ≥47,176,870, ≥10^36534；宇宙原子数 ≈ 10⁸⁰

数字中忙海狸的已知值来自公开文献（BB(1)–BB(4) 已严格确定，BB(5) 于 2024 年确定为 47,176,870，BB(6) 是下界）。 其余是实测。

你自己机器上跑出来的数字会略有不同。差一点不影响结论——结论是结构性的。