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

问题简介

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