忙碌海狸——一个具体的不可计算函数

上级：famous-machines

Radó（1962）提出：在所有从空白纸带出发、最终会停机的 n 状态、2 符号图灵机里，一台机器最长能跑多久？

忙碌海狸

S(n) = 任何一台在空白纸带上会停机的 n 状态、2 符号机器所能达到的最大步数（孪生函数 Σ(n) 统计的是停机时纸带上留下的 1 的个数）。

它是不可计算的——为什么

Theorem

S(n) 的增长速度快于任何可计算函数；S 本身不可计算。

Proof

如果 S 可计算，停机问题就会变成可判定的：要检验某个 n 状态机 M 在空白纸带上是否停机，只需运行它 S(n)+1 步——如果到那时还没停机，同等规模的停机机器都跑不了那么久，所以 M 永不停机。这就判定了停机问题（history）——矛盾。而且 S 支配着任何可计算函数 f，否则 f 本身就能给出这样一个上界。∎

数值（一堵墙很快出现）

S(1)=1、S(2)=6、S(3)=21、S(4)=107，而S(5) = 47,176,870——五状态的情形直到2024 年才被解决（bbchallenge 协作项目）。S(6) 已经大到近乎天文数字（已知下界是指数塔），至今仍是开放问题。n 每加一，就跃出了可证明的边界。

小规模情形是怎么手算出来的

S(n) 是靠穷举搜索找到的：枚举所有 n 状态、2 符号的机器（数量有限），逐一在空白纸带上模拟，留下会停机的那些，取其中步数的最大值。真正难的部分在于证明那些不停机的机器确实永不停机——这正是 S(5) 拖到 2024 年才解决的原因。对 n = 1, 2 而言，规模很小：

S(1) = 1。 只有一个工作状态 A（外加停机态 H）。唯一能停机的方式是第一次读取就停：A,0 → 1,R,H——写下一个 1，停机。1 步，一个 1。（任何留在 A 里的规则都会永远循环下去。）所以 S(1)=1，Σ(1)=1。

S(2) = 6。 冠军机器（状态 A、B，停机态 H）：

        read 0      read 1
  A:    1,R,B       1,L,B
  B:    1,L,A       1,R,H

从全空白纸带开始追踪（起始状态 A，读写头位于第 0 格）：

步数	状态	读到	应用的规则	动作
1	A	0	`A,0 = 1,R,B`	写 1，右移，→ B
2	B	0	`B,0 = 1,L,A`	写 1，左移，→ A
3	A	1	`A,1 = 1,L,B`	写 1，左移，→ B
4	B	0	`B,0 = 1,L,A`	写 1，左移，→ A
5	A	0	`A,0 = 1,R,B`	写 1，右移，→ B
6	B	1	`B,1 = 1,R,H`	写 1，右移，停机

六步之后，纸带上留下四个 1 → S(2)=6，Σ(2)=4。（这台机器正是那个最大化者；其他任何能停机的两状态机器都会更早停下。）

为什么它重要

忙碌海狸是不可计算视界的具体化身："等得足够久就会知道它会不会停机"这句话是对的，但要等多久，也就是 S(n)，是不可计算的——你无法知道多久才算够久。它还钉住了可证明性的边界：知道足够大的 n 对应的 S(n)，就能一并解决一批著名的开放问题（可以构造一台机器，使它停机当且仅当，比如说，哥德巴赫猜想不成立），所以超过某个点之后，S(n) 在 ZFC 公理系统里是不可证明的。