忙碌的 the beaver：计算复杂性极限的探寻之旅

图灵机（Turing machine）的“忙碌的 the beaver”游戏，旨在寻找特定规则数下运行时间最长的图灵机，其运行步数即为“忙碌的 the beaver”数 BB(n)。这一过程在实践中极具挑战性，因为随着规则数 n 的增加，可能的图灵机数量呈指数级增长，且识别非停止机器（陷入无限循环）和模拟长运行机器的复杂性随之提升。即使是技术进步，也难以完全克服模拟这些巨量步数的计算瓶颈。

在 BB(6) 的研究领域，自20世纪90年代以来，研究者们（包括 Shawn Ligocki 及其父亲 Terry Ligocki）一直在不断刷新记录。2007年，一个六规则的图灵机记录了近3000位数的运行步数。随后，Pavel Kropitz 和 Shawn Ligocki 之间的竞争将记录推向了新的高度，最终发现的机器运行时间甚至超过了宇宙中的原子数量。为了描述如此庞大的数字，数学上引入了迭代指数运算（tetration），例如 $10  ext{↑↑} 4$ 的位数已远超宇宙物质总量，标志着计算复杂性进入了新的维度，传统模拟方法已无法企及。

Busy Beaver Hunters Reach Numbers That Overwhelm Ordinary Math | Quanta Magazine

The quest to find the longest-running simple computer program has identified a new champion. It’s physically impossible to write out the numbers involved using standard mathematical notation.

Quanta MagazineBen Brubaker