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

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

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

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

△图源：QuantaMagazine

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

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

海狸数，专业点说叫忙碌海狸数 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。

△图源：QuantaMagazine

团队关键贡献来自一个化名为 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，而这也促使忙碌海狸数挑战社区成立。

△图源：QuantaMagazine

忙碌海狸数挑战社区，最初目的是严格证明 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/

一键三连「点赞」「转发」「小心心」

欢迎在评论区留下你的想法！

—  完  —

专属 AI 产品从业者的实名社群，只聊 AI 产品最落地的真问题   扫码添加小助手，发送「姓名 + 公司 + 职位」申请入群～

进群后，你将直接获得：

  最新最专业的 AI 产品信息及分析  

   不定期发放的热门产品内测码

   内部专属内容与专业讨论

点亮星标

科技前沿进展每日见