和图灵机相关的这个数字，已经大到整个宇宙原子都容不下了

闻乐 发自 凹非寺
量子位 | 公众号 QbitAI

衡量图灵机最大运行步数的海狸数（busy beaver number）纪录，被刷新了！

一位神秘人突破了第六个海狸数的新下限，而且数值大到超乎想象——

假如将宇宙里的每个原子都刻上数字，也无法完全容纳它。

也就是说，用咱平时熟悉的十进制根本没办法完全表示，得用超复杂的五幂运算来描述：指数套指数再套指数

这到底是个什么样的神秘数字呢？

研究图灵机极限能力的数字

海狸数，专业点说叫忙碌海狸数BB(n)。它背后藏着图灵在1936年就证明的停机问题：

你永远没法用通用程序判断一台图灵机到底是运行有限步骤后就停机，还是会一直无限运行下去。

所以找这个数，本质是在触碰计算机能解决问题的边界

图灵机的计算方式是在无限长的磁带上读取和写入0和1，磁带划分为很多个单元格，一个读写头一次可以操作一个单元格。

每台图灵机都有自己的规则，规则规定读写头在进入新的单元格时，遇到0或1分别该进行什么操作。

除此之外还有一个特殊的规则告诉图灵机要停止运行。

于是图灵机在运行过程中会出现运行有限次就停机或者无限循环运行两种状态。

1962年，数学家Tibor Radó发明了忙碌海狸游戏，通过寻找特定规则数的图灵机在停机前运行最长时间来定义忙碌海狸数BB(n)。

例如，若选择规则数n=5，目标就是找到有5条规则的图灵机中运行时间最长才停机的那个，它在停机前执行的步数，就是BB(5)。

这就好比一群运动员在跑步，看谁坚持的时间最长，这个最长时间就是海狸数。

从20世纪70年代起，数学家们就踏上了寻找海狸数的漫漫长路。

对于BB(1)，情况相对简单，因为单一规则的图灵机实际上只有两种可能性，要么第一步就停机，要么一直运行下去，所以很容易就确定了BB(1)=1

到了BB(2)，难度稍有提升。此时，需要考虑超过6000个不同的图灵机。但一个相对简单的程序足以证明BB(2)=6

而确定 BB(3) 时，挑战大幅增加。因为三规则的图灵机数量膨胀到数百万。1965年，研究人员经过大量的研究和推算，在16777216个图灵机中，找出了最多可以执行21个计算步骤的图灵机，即BB(3)=21

1974年，数学家Allen Brady证明了BB(4)=107

确定前四个海狸数就耗费了几十年时间，而BB(5)更是直到去年，才被一个业余的数学家团队成功攻克，确定BB(5)=47176870

团队关键贡献来自一个化名为mxdys的神秘人

这次BB(6)的新纪录也出自他手。

BB(6)的突破

20世纪90年代，研究者开始认真探索BB(6) 。

利戈茨基和他的父亲特里在2007年找到了打破运行时间记录的六规则图灵机，其停机步数近3000位。

2010年，克罗皮茨找到运行时间更长的机器，步数超30000位。克罗皮茨的BB(6)纪录保持了12年。

2022年，利戈茨基借助新硬件打破记录，引发了与克罗皮茨的竞争，利戈茨基两次宣布新纪录，克罗皮茨都能在三天内刷新这个纪录。

而庞大的数值也来到了四次幂运算。将一个数字乘n次，是指数运算，而现在的结果需要反复对一个数字进行指数运算。例如，10↑↑1只是10，但10↑↑2是10的10次方。

二人不断突破，运行步数从10↑↑5增长到10↑↑15，而这也促使忙碌海狸数挑战社区成立。

忙碌海狸数挑战社区，最初目的是严格证明 BB(5)的真实值，并在2024夏天成功，关键贡献来自化名mxdys的神秘人。

之后社区成员继续探索BB(6)，凯特琳・杜塞特发现移位溢出计数器类机器，为研究者们开辟了一条崭新的道路。

mxdys于今年6月16日宣布发现新的冠军机器，它的运行步数达到令人咋舌的10↑↑107

这次克罗皮茨也大方地表示失去了冠军头衔：

“不幸的是，这次我不会表演我的三天技巧了。”

然而在仅仅一周后，mxdys又打破纪录，新数值需用五幂运算2↑↑↑5表示，这还只是 BB(6)的下限。

什么概念呢？首先，在普通十进制记法中根本不可能写出来。

更夸张的是，即使设法将宇宙中每个原子都刻上数字，也会在取得任何可测量的进展之前耗尽这些原子。

我们只能期待，随着计算机技术的不断发展和数学理论的日益完善，数学家们逐渐揭开BB(6)的神秘面纱。

正如一位海狸数爱好者Racheline所说：

“对我来说，做数学最正当的理由就是因为它有趣。它是艺术。”

[1]https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/

— 完 —