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

69 0 0

文章摘要

衡量图灵机最大运行步数的海狸数纪录被刷新，一位神秘人突破了第六个海狸数的新下限，其数值大到难以用十进制表示，需用超复杂的五幂运算描述。

海狸数即忙碌海狸数BB(n)，与图灵1936年证明的停机问题相关，寻找该数本质是触碰计算机能解决问题的边界。图灵机在无限长磁带上读取和写入0和1，每台有自己的运行和停止规则，运行状态有有限次停机或无限循环两种。1962年，数学家Tibor Radó发明忙碌海狸游戏，通过寻找特定规则数的图灵机在停机前运行最长时间来定义BB(n)。

从20世纪70年代起，数学家们就开始寻找海狸数。确定BB(1)相对简单，其值为1；BB(2)需考虑超6000个图灵机，值为6；确定BB(3)时，三规则图灵机数量膨胀到数百万，最终确定其值为21；1974年，数学家Allen Brady证明BB(4)=107；直到去年，一个业余数学家团队确定BB(5)=47176870，团队关键贡献来自化名mxdys的神秘人。

20世纪90年代，研究者开始探索BB(6)。2007年，利戈茨基和他父亲找到打破运行时间记录的六规则图灵机；2010年，克罗皮茨找到运行时间更长的机器，其纪录保持了12年；2022年，利戈茨基和克罗皮茨不断竞争突破，运行步数从10↑↑5增长到10↑↑15，促使忙碌海狸数挑战社区成立。该社区最初目的是严格证明BB(5)真实值，并在2024夏天成功，关键贡献仍来自mxdys。之后社区成员继续探索BB(6)，凯特琳・杜塞特发现移位溢出计数器类机器开辟新道路。mxdys于今年6月16日宣布发现新冠军机器，运行步数达10↑↑107，一周后又打破纪录，新数值需用五幂运算2↑↑↑5表示，这只是BB(6)的下限。

随着计算机技术发展和数学理论完善，数学家有望揭开BB(6)的神秘面纱，正如一位海狸数爱好者所说，做数学因有趣而正当，它是艺术。