忙碌的河狸

“忙碌的河狸”（Busy Beaver）是理论计算机科学中的一个著名难题：在所有规则数有限、最终会停机的图灵机中，哪台机器能在停机前运行最多步数？

问题简介

• 1962年，数学家拉多提出“忙碌的河狸”问题，旨在寻找运行时间最长的停机程序。
• 忙碌的河狸数 BB(n) 表示 n 条规则下，图灵机在停机前能运行的最大步数。
• 随着规则数增加，图灵机数量呈爆炸式增长，BB(n) 也极其巨大且不可计算。
• 例如，BB(1)=1，BB(2)=6，BB(3)=21，BB(4)=107，BB(5) 已知下界超过4700万。

图灵机与停机问题

• 图灵机是一种理想化的计算模型，由阿兰·图灵提出。
• 停机问题指的是：是否存在算法能判断任意图灵机是否会停机？图灵证明不存在通用算法。
• 忙碌的河狸问题本质上是停机问题的极限版本。

数学与不可知

• 忙碌的河狸与停机问题、哥德巴赫猜想、黎曼猜想等数学难题有深刻联系。
• 某些图灵机的停机与著名猜想的真假直接相关。例如，存在“当且仅当哥德巴赫猜想不成立时停机”的图灵机。
• 忙碌的河狸为“不可知”的数学命题提供了具体的界限。BB(n) 的不可计算性揭示了数学世界的边界。

研究意义

• 通过研究 BB(n)，可以衡量数学问题的复杂度和可知性。
• 忙碌的河狸问题揭示了计算与数学证明的极限。
• 相关研究推动了对不可判定性、复杂性和数理逻辑的理解。

趣味与启示

• 忙碌的河狸问题虽源自娱乐，却成为严肃的科学研究对象。
• 它让我们直观地看到，计算与知识的边界究竟在哪里。
• 也提醒我们，简单规则下也能孕育出极其复杂和深刻的现象。

应用示例

1. 正例：可解问题

假设我们要判断一个简单的数学命题：

“存在一个偶数大于2，不能表示为两个质数之和。”

我们可以构造一台图灵机：

• 依次枚举偶数 n，从4开始。
• 对每个 n，遍历所有小于 n 的质数对，判断是否有 p+q=n。
• 如果找不到，则停机（说明命题为真）；如果一直能找到，则继续。

如果这台图灵机最终停机，说明命题为真（存在反例）；如果永远不停止，则命题为假（哥德巴赫猜想成立）。

但由于停机问题不可判定，我们无法预知这台机器是否会停机。

2. 反例：不可解问题

考虑如下命题：

“所有图灵机最终都会停机。”

我们可以为每台图灵机构造一台“监控机”，让它模拟原图灵机的运行。

• 如果原图灵机停机，则监控机停机。
• 如果原图灵机不停止，监控机也不停止。

由于停机问题本身不可判定，忙碌的河狸问题也无法解决所有这类命题。

3. BB(n) 的具体构造

以 BB(2) 为例：

• 只允许2条规则的图灵机。
• 穷举所有可能的规则组合，找到在停机前能运行最多步数的那台。
• 结果是 BB(2)=6。

图灵机构造示意：

状态	读	写	移动	下一个状态
A	0	1	右	B
B	0	1	左	A
A	1	1	右	停机
B	1	1	左	停机

这台机器在停机前最多能写6个1。

---

参考：

• 知乎专栏：忙碌的河狸