BB(10) 超越葛立恒数：忙碌海狸问题的里程碑

计算机科学中有一个著名的函数——忙碌海狸函数 BB(n)，它描述的是 n 状态图灵机在停机前能写下的最大 1 的数量。这个函数增长极快，远超任何可计算函数。最近 Hacker News 上热议的话题「BB(10) > Graham's Number」指出，10 状态的忙碌海狸数已经超过了葛立恒数。

什么是忙碌海狸函数

忙碌海狸函数 BB(n) 定义为一台 n 状态、双符号图灵机在最终停机时，纸带上最多能写下的 1 的个数。它是不可计算的——不存在通用算法对任意 n 求出 BB(n)。

正因为不可计算，BB(n) 的增长速度远超所有可计算函数，包括阿克曼函数、甚至快速增长的康威链式箭头。前几项已知值很小（BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13），但从第 5 项起就急速飙升。BB(5) 直到近年来才被确定为 47176870，而 BB(6) 已经大到无法用常规符号完整写出。

双符号图灵机是一类被大幅限制的图灵机模型：纸带字母表只有 {0, 1} 两个符号（外加一个隐式的空白符，通常也视作 0），读写头每一步只能左移或右移一格，状态数固定为 n。所谓「写下 1 的数量」通常指停机时纸带上的非空白格数量，两种计数方式在文献中都被使用，只差常数因子，不影响增长量级的讨论。

这类机器的行为完全由一张有限的状态转移表决定：对每个「状态 × 当前符号」的组合，规定下一步写什么、往哪走、切换到哪个状态。转移表的数量是有限的，因此 n 状态图灵机只有有限多种，理论上可以逐一枚举、模拟。问题恰恰出在这里——其中一部分机器永远不会停机，而判定某台机器是否停机正是停机问题，不可判定。所以尽管 BB(n) 有确切定义、每个 n 都对应一个确定的自然数，却不存在能对任意 n 算出它的算法。

可计算函数指存在一台图灵机、在有限步内对任意输入给出输出并停机的函数。阿克曼函数和康威链式箭头记号虽然增长极快，但仍属可计算之列——它们都能被写成有限的算法。忙碌海狸函数的不同之处在于：如果能算出 BB(n)，就能用它判定所有 n 状态机器是否停机，从而解决停机问题。既然停机问题不可判定，BB(n) 就必然不可计算。

这带来一个直接推论：BB(n) 是不可计算但良定义为自然数的函数，且对任意可计算函数 f，都存在某个 n 使 BB(n) > f(n)。换言之，无论你构造出多么疯狂的可计算大数函数，忙碌海狸最终都会在某个状态数处把它甩在身后。这正是 BB(10) 能超过葛立恒数的根本原因。

葛立恒数是什么

葛立恒数曾长期作为「数学证明中出现过的最大的数」被收入吉尼斯纪录。它来自拉姆齐理论中关于超立方体顶点着色的一个上界问题，用高德纳箭号表示法递归定义，其规模之大，连它的位数本身都无法用普通指数塔写出来。

在很长一段时间里，葛立恒数被视为「大到不可思议」的代名词。但忙碌海狸函数的存在，让这种「不可思议」显得相当克制。

高德纳箭号表示法用一个上箭头表示幂运算的迭代，两个上箭头表示幂塔的迭代（即四级运算），三个箭头则迭代两个箭头的过程，以此类推，箭头越多增长越快。葛立恒数的定义正依赖于这种递归的箭头堆叠：先定义 g₁ = 3↑↑↑↑3（四个箭头），再令 g₂ = 3 与 g₁ 个箭头的一层，依此定义 g₆₄，葛立恒数就是 g₆₄。

这种构造的特点在于：它每一步都把上一步所用的箭头数量作为新的箭头数量，形成层层嵌套的爆炸式增长。即便如此，整个定义仍是有限、机械、可逐步展开的——只要你愿意写下天文数字量级的符号。这种「巨大的但完全可计算」的性质，与忙碌海狸函数的不可计算性形成了鲜明对照。

为什么 BB(10) 能超越葛立恒数

关键在于增长速率的量级差异。葛立恒数虽然巨大，但它仍然是可计算的——存在一个有限算法能把它写出来（只是所需时间和空间荒谬）。忙碌海狸函数则位于可计算性层级的另一端：它不可计算，其增长快于任何递归可计算函数。

一个直观的理解是：给定任意可计算函数 f，总能找到某个 n 使得 BB(n) > f(n)。葛立恒数对应某个具体的可计算构造，因此必然存在一个不太大的 n 让 BB(n) 超过它。社区讨论中给出的结论是，这个 n 落在 10 附近——即 BB(10) 已经确定大于葛立恒数。

这意味着，要描述一台 10 状态图灵机能写下的最大 1 的数量，葛立恒数甚至不够用。

这意味着什么

这一事实本身并不令人意外，它是忙碌海狸函数定义的直接推论。但它的教育意义在于：

• 「大」是相对的。人类凭直觉构造的所谓「最大数」，在不可计算函数面前不值一提。
• 10 个状态已经足够。图灵机的极简模型用很少的状态就能编码极其复杂的计算过程，BB(10) 的具体值永远无法被人类算出——因为算出它就等于解决了停机问题的一个实例。
• 不可计算性的直观展示。相比抽象的不可判定证明，BB(n) 超越葛立恒数是一个能讲给非专业人士听的例子，说明「存在无法计算的函数」到底意味着多大的鸿沟。

HN 讨论区（news.ycombinator.com/item?id=50070741）的评论大多聚焦于这一结论的推导细节，以及它是否已被严格证明。核心共识是：这属于忙碌海狸函数标准性质的推论，而非新的未解难题。

小结

BB(10) > Graham's Number 是一个漂亮的思想实验式结论。它提醒我们，图灵机这个看似简单的模型，蕴含着远超人类直觉想象的复杂度。葛立恒数曾经是「大数」的巅峰象征，如今它成了忙碌海狸函数面前的一个坐标点。