忙碌海狸游戏是什么？一个增长快到无法计算的数学问题

忙碌海狸游戏（Busy Beaver Game）是理论计算机科学中一个著名的问题，由匈牙利裔数学家 Tibor Radó 在 1962 年提出。它关注一种特殊的图灵机：在所有给定数量状态的图灵机中，那些最终会停下来的机器里，哪一台在纸带上写下的“1”最多，或者运行的步数最多。这台“最勤劳”的机器被称为忙碌海狸。

游戏规则

图灵机是一种理论上的计算模型：一条无限长的纸带被分成一个个格子，每个格子上写着 0 或 1；一个读写头在纸带上移动，读取当前格子的内容，根据自己当前所处的“状态”和读到的符号，决定写下什么、往左还是往右移动一格、接下来进入哪个状态；直到进入“停机”状态为止。

忙碌海狸游戏的规则是：给定一个正整数 n，考虑所有具有 n 个状态、使用两种符号的图灵机，它们都从一条全是 0 的纸带开始运行。在其中所有最终会停机的机器里，找出停机时纸带上 1 最多的那台，这个最多的数量记为 Σ(n)；或者找出运行步数最多的那台，步数记为 S(n)。不会停机、永远运行下去的机器不算数。

增长快得惊人

对于很小的 n，可以算出确切的值：1 个状态时最多写 1 个 1；2 个状态时是 4 个；3 个状态时是 6 个；4 个状态时是 13 个，运行 107 步。到了 5 个状态，问题变得极其困难，直到 2024 年，一个名为 bbchallenge 的国际协作项目才借助计算机辅助证明，最终确认 5 个状态的忙碌海狸会运行 47176870 步后停机。而 6 个状态的忙碌海狸，已知的下界是一个大到无法用普通方式书写的天文数字。

为什么它不可计算

Radó 证明了：忙碌海狸函数是不可计算的，它的增长速度超过任何可计算的函数。这和停机问题密切相关：要确定忙碌海狸的值，就得判断每一台候选的图灵机最终会不会停，而停机问题已经被证明在一般情况下是不可判定的。反过来，如果能算出忙碌海狸的值，就能解决停机问题：只要让一台机器运行超过 S(n) 步，如果它还没停，就说明它永远不会停。研究者还发现，某些状态数不大的图灵机的行为，等价于一些著名的未解数学猜想，所以确定更大的忙碌海狸值，可能需要先解决这些数学难题。忙碌海狸因此成为探索计算和数学极限的一扇窗口。