60年追猎「忙碌海狸」，数字大到宇宙都装不下，数学圈集体破防！

新智元报道

编辑：元宇

【新智元导读】1936年，艾伦·图灵提出了著名的「停机问题」。1962年，数学家Tibor Radó用「忙碌的海狸游戏」来探索这一问题。60多年来，无数专业与业余数学家都加入了这一场史诗级的追猎之中，新纪录不断诞生，最近找到的数字，足以撑爆宇宙，让数学圈集体破防。

在大约60多年前，有一位数学家，发明了一个后来风靡全球数学圈的游戏：寻找忙碌海狸。

这个游戏，就是要在固定状态数n的前提下，找到那只在停机前跑得最久的图灵机，它就像忙碌的海狸一样，不停地折腾。

所以，这个游戏就正式定名——忙碌的海狸。

当状态数n很小时，步数就比较容易搞清。

即便是这样，当第4只海狸BB(4)在1983年被确认时，这个游戏已经持续了20年。

随后的第五只海狸，即BB(5)，一直到去年，才被最终确定下来。

距离第4只海狸的确认，又过去了42年。

由于在「捕获」BB（5）的过程中，Coq证明助手发挥了重要作用。

所以，当找到第五只海狸时，著名的数学家陶哲轩还特意表示：这再一次体现了数学工具对于数学研究的作用多么重要。

BB（1）=1

BB（2）=6

BB（3）=21

BB（4）=107

BB（5）=47176870

BB（6）=？

直到现在，仍旧没人知道BB(6)有多大。

一直到2022年，「忙碌的海狸数」挑战者们确定，BB(6)的数值，至少大到从物理上，已不可能用标准的十进制表示法写出。

假如你可以使用原子计数，就算你把所有原子都用完了，BB(6)仍是遥不可及。

若要描述BB（6）以及之后的冠军机，可能要用「一页纸宇宙」来形容。

区区一页纸规则，就能推演「宇宙级」的数字，轻松碾压大多数著名巨数（费舍尔数、Ackermann 等）。

「它远远超出了我们所能想象或企及的任何事物」，德克萨斯大学奥斯汀分校的计算机科学家Scott Aaronson说。

这种极小演绎出极大的爆炸性张力，正是「忙碌海狸」的魅力所在。

这也是它在过去60多年间，能吸引全球无数专业及业余数学家狂热追随的原因所在。

海狸陷阱

「忙碌的海狸数」，与理论计算机科学中一个最「臭名昭著」的难题紧密相连。

这个难题，就是计算机科学中的一个经典问题——「停机问题」(halting problem)：

给定一个计算机程序的代码，你能否判断它最终会停止，还是会永远运行下去？

1936年，艾伦·图灵提出并证明了「停机问题」的不可解性，即不存在一个通用的算法或程序能回答这个问题。

艾伦·图灵

艾伦·图灵通过发明一种形式化的计算数学模型，证明了这一开创性成果，其中的程序由一种假设性的设备来表示，如今被称为「图灵机」。

每台图灵机，就好比一个「照规则办事的小机器人」，它有一张「规则清单」来指导行动。

规则越少，图灵机的行为就越简单，很容易就能判断它会不会停机。

随着规则变多，预测图灵机行为结果的难度就会急剧上升，甚至变得不可判定。

1962年，数学家Tibor Radó用「忙碌的海狸游戏」来探索这个问题。

他的玩法是：首先选择一个特定的规则数量，称之为n。你的目标是找到一台拥有n条规则、且在最终停机前运行时间最长的图灵机。

这台机器就被称为「忙碌的海狸」，而相应的「忙碌的海狸数」BB(n)，就是它运行的步数。

原则上，要找到任何给定n的「忙碌的海狸」，你只需做几件事：

• 首先，列出所有可能的n规则图灵机。

• 接着，用一个计算机程序模拟运行每一台机器。寻找机器永不停机的迹象——例如，许多机器会陷入无限循环。

• 然后，剔除所有永不停机的机器。

• 最后，记录下其他每一台机器在停机前运行了多少步。

其中运行时间最长的那台，就是你要找的「忙碌的海狸」。

但在实践中，这通常会变得异常棘手。

首先，随着每条新规则的增加，可能的机器数量将爆炸式增长。逐一分析它们是毫无希望的，这时你需要编写一个定制的计算机程序来分类并筛选机器。

有些机器很容易分类，因为它们要么很快停机，要么陷入易于识别的无限循环，但另一些机器却很难识别，它们会运行很长时间，却不显示任何明显的模式。

「停机问题」的「恐怖」之名，在这些擅长「隐藏」的机器身上得到了淋漓尽致的体现。

有些机器在停机前运行的时间之长，让逐步模拟它们已无可能，这时需要运用巧妙的数学技巧来估量它们的运行时间。

但也只能帮到这里了。

一个时代的终结

上世纪90年代到21世纪初，就在对BB(5)的搜寻陷入僵局时，「忙碌的海狸数」追随者们，又开始远征BB(6)。

Shawn Ligocki和他的父亲Terry，就是这些挑战者中的一员。

Shawn Ligocki博客主页

Terry是一位应用数学家，他利用劳伦斯伯克利国家实验室强大计算机的闲暇时间，来运行他们的搜索程序。

2007年，他们发现了一台拥有六条规则的图灵机，打破了当时的最长运行时间记录，它在停机前运行的步数接近3000位。

如果用12号字体，这3000个数字大约能写满一页纸。

三年后，一个名为Pavel Kropitz的斯洛伐克计算机科学本科生，决定将搜寻BB(6)作为他的毕业设计项目。

他编写了自己的搜索程序，并将其设置在一个大学实验室的30台计算机网络上在后台运行。

一个月后，他发现了一台打破Shawn Ligocki父子记录的图灵机，用「忙碌的海狸追寻者」的行话来说，这是一位新的「冠军」。

仅仅一个月后，这位幸运的猎手，便用一台运行时间超过30000位数的机器打破了自己的记录——这个数字足以写满大约10页纸。

Kropitz保持了BB(6)记录长达12年。

当然，Shawn Ligocki也不甘示弱。

他在2022年5月开始了一份新工作，这让他有条件接触到强大的计算机集群，果然又捕获到新的「冠军」，打破了Kropitz的记录。

2022年，Shawn Ligocki发现了一台六规则图灵机，其运行时间的位数超过了宇宙中的原子总数。

两周之内，Ligocki又接连两次两次宣布了新的冠军。

有意思的是，每当Ligocki宣布新的冠军，Kropitz都会在三天内将记录刷新。

Ligocki和Kropitz发现的最后两台机器，其运行时间已达到了一个全新的量级。

如此庞大的数字，要借助「迭代幂次」(tetration)来计算。

如果将n个相同的数相加，就是乘以n；如果将n个相同的数相乘，就是幂运算。

如果对幂运算进一步拓展，它表示对一个数进行多次幂运算，也就是「迭代幂次」(tetration)，用两个向上的箭头(↑↑)表示。

10↑↑1就是普通的10。

但10↑↑2是10的10次方，即100亿。

而10↑↑3则是10的100亿次方：一个1后面跟着100亿个零。

要写下这个数字，需要一叠高达一千英尺的纸，大约100层楼那么高。

到了10↑↑4，你就跨越了一个象征性的门槛，问题不再是纸够不够用——这个数字的位数已经远远超过了宇宙中的原子总数。

一幅描绘大数如何表示的图表

当Ligocki第二次打破Kropitz的记录时，他所用的是一台六规则图灵机，其运行步数超过了10↑↑5。

Kropitz则用一台运行步数为10↑↑15的机器予以回击——这是一个由10构成的、高达15层的「幂塔」。

这已经远远超越了我们熟悉的数字世界。

「一个时代就此终结」，Kropitz叹道。

疯狂的新境界

在那之后，「忙碌的海狸游戏」开始从单打独斗变成了联合作战——「忙碌海狸挑战」社区成立，开启了一个协作的新时代。

这个社区，是一位名叫Tristan Stérin的研究生，在2022年发起的一个名叫「忙碌海狸挑战」的在线协作项目，聚合了来自全球各地的数学「发烧友」，他们中的大多数都没有传统的学术资格。

「忙碌海狸挑战」社区发起者Tristan Stérin

「忙碌海狸挑战」社区地址https://bbchallenge.org/

「忙碌海狸挑战」社区的明确目标，是严格证明BB(5)的真实值。

去年7月，这个社区的志愿者们利用Coq证明助手确认了BB（5）。

今年6月，一位来自该社区中最神秘大神证明了BB(6)的一个新下限，并在短短九天后再次刷新了纪录。

数学家们一次次被震惊。

马里兰大学的计算机科学家William Gasarch惊呼：

「BB(6)正把我们带入庞大数字的平流层。」

2024年夏天，一位化名「mxdys」的神秘新人做出了关键贡献，吸引了弗吉尼亚理工大学的计算机科学本科生Katelyn Doucette。

她很快也加入了「忙碌的海狸挑战」社区，从此也成了搜寻BB(6)的活跃分子。

她在mxdys分类的几千台BB(6)「顽固」机器列表中，发现了一个「异类」，它的运行时间仅次于Kropitz的卫冕冠军。

它一个的重要特别之处在于：它属于一类被称为「移位溢出计数器」(shift overflow counters)的机器。

采用与Kropitz卫冕冠军截然不同的机制来实现超长运行时间。

「移位溢出计数器」的出现并非孤例，这让Shawn Ligocki兴奋不已，他推测此类机器的数量要远超他们的想象。

于是，「移位溢出计数器」很快成了研究者们的「新宠」。

mxdys抢先一步，在6月16日，他宣布发现了一位新的冠军，它在10↑↑107步后停机。

也就是说，其运行时间是一个由10构成、高达1000万层的「幂塔」。

当我们谈论「10构成的幂塔」时，它实际上指的是多次将10作为底数进行指数运算。

要把这个数字，写成一长串数字已绝无可能，即使将它写成一个幂塔也变得非常困难：如果用12号字体，这一行10的连乘将延伸约25英里（40公里），接近洛杉矶到好莱坞的距离。

这一消息，直接将Kropitz拉下王座，他坦然接受了冠军头衔的失落，并表示自己将无法再表演「三天反杀」的绝技了。

超越「最大之大」

但不出意外，这项新纪录并未持续多久。

一周后，mxdys用另一台机器再次刷新了它，而这台机器的运行时间，再一次有了质的突破。

如果要以最简洁的形式写下它，需要引入一个近乎「荒谬」的数学运算——「五级运算」(pentation)，它是重复的迭代幂次，要用三个向上的箭头(↑↑↑)表示。

它与迭代幂次的关系，就如同迭代幂次与幂运算的关系。

mxdys的新冠军在停机前运行的总步数超过了2↑↑↑5，即2↑↑(2↑↑(2↑↑(2↑↑2)))。

要展开这个表达式，你需要从最内层的括号向外计算：2↑↑2是4，而2↑↑4略超65,000。这样你就剩下2↑↑(2↑↑65,000)，使得最终那个由2构成的堆栈的高度，本身就是一个大到无法想象的数字。

不要说写一个延伸数英里或数百万秒差距的幂塔了，就连这种更紧凑的表示法，也已无法容纳于宇宙之中。

这是一个要撑爆宇宙的数字了！

一幅描绘一台最近发现的图灵机所遵循的六条规则的图表

这个新结果，仍然只是BB(6)的一个下限——真实值可能还要高得多。

「忙碌的海狸数」追寻者们，预计短期内不会有确切答案。

如果想要取得新的突破，可能就需要在纯数学领域取得概念性的突破。

但这并不意味着这些「忙碌的海狸数」的追随者们，就无事可做了。仍有数千台六规则图灵机等待被探索，每一台都展现着其独特的丰富行为。

Racheline说，「做数学最正当的理由就是它很有趣，它是一门艺术。」

只要有了兴趣，你就永远都会有新的事情可做。

参考资料：

https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/%20%20

https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/