有这样一个奇特的数列：1、6、21、107和47176870中国股票网。你能猜到这个数列的下一个是什么吗？
其实，现在世界上还没人知道下一个数字是什么。这个数列是衡量图灵机最大运行步数的“忙碌的海狸函数（Busy Beaver Number）”，简写为BB（n）。60多年来，数学家、计算机科学家、业余数学家一直在努力寻找最新的海狸数。
这个数列中第五个“BB(5)=47176870”是2024年7月2日由Busy Beaver Challenge团队证明的。
现在，人们仍然不知道BB(6)有多大，不过一个神秘人宣布他把BB(6)的下限提高了一大截，这个新下限数值大得无法想象——如果用十进制表示，这个数字已经大于宇宙中全部原子的总数了，只能用五级运算2↑↑↑5来表示。
01
图灵的停机问题
忙碌的海狸函数与一个理论计算机科学中的著名难题“停机问题”息息相关。
停机问题：一个给定的计算机代码，能判定这段代码最终会停止还是永远运行？
海狸陷阱
1936年，人工智能之父艾伦·图灵 （Alan Turing）发明出名为“图灵机”的计算机模型。
图灵机的计算方式是在无限长的纸带上读取或写入1和0，纸带上分成很多格子，一个读写头一次可以操作一个单元格。每台图灵机都有自己的操作规则，规定进入新单元格时，遇到0或1分别该进行什么操作。此外还有一个特殊规则告诉图灵机可以停止工作。
这样图灵机在执行过程中会出现有限次就停机或者无限循环运行两种状态。而图灵机的规则数越多，就越难以预测图灵机的最终状态。
图灵从数学层面证明了“停机问题”无通解：你永远没法用通用程序判断一台图灵机到底是运行有限步骤后就停机，还是会一直无限运行下去。
图灵证明停机问题，本质上是从数学层面上第一次告诉世人“没有一个能解决停机问题的万能算法”。同时图灵也指出了计算机的能力边界，对于有些问题来说，只要计算机还是图灵机模型就无法获得答案。
1962年，数学家Tibor Radó在“停机问题”的基础上发明了“忙碌海狸游戏”：对特定规则数n的图灵机来说，他将海狸数定义为找到在停机前能运行的最长步数。
例如，若规则数n=5，目标就是在所有有5条规则的图灵机中找到那个运行步数最长才停机的那个，它在停机前执行的步数，就是BB(5)。
那么找到这个海狸数要几步呢，第一步列出所有可能的n规则图灵机；第二步让计算机模拟运行每个图灵机，把陷入无限循环的丢弃。最后，记录每台机器在停止前走了多少步。
问题是在实践中，增加一条规则图灵机的数量会大幅膨胀；而且有的图灵机运行起来你根本看不出它是不是会停下来。
因此寻找最新的海狸数光靠蛮力是没有用的，需要算力和数论两方面的突破。能找到最新的海狸数也值得获得巨大的声誉。从20世纪70年代起，数学家们就踏上了寻找海狸数的漫漫长路。
BB(1)，最简单，要么第一步就停机，要么一直运行下去，所以BB(1)=1。
BB(2)，当2条规则时，就有超过6000种不同的图灵机！还好用个简单程序就能算出来BB(2)=6。
BB(3)，三规则的图灵机数量膨胀到了上千万个（16777216个），1965年，研究人员通过枚举找出BB(3)=21。
1974年，数学家Allen Brady证明了BB(4)=107。
2、3、4忙碌海狸在纸带上运动轨迹图
找到BB(5)
寻找海狸数不是一件简单的事，确定前四个海狸数就耗费了几十年时间，而BB(5)更是直到去年，才被一个业余的数学家团队成功攻克，确定BB(5)=47176870。
对于五规则图灵机，数量可能接近17万亿个。单单是以每毫秒一个的速度列出所有这些规则的组合，也需要500多年。
1989年，程序员Marxen利用公司超算的空余时间，找到一个能在47176870步后才停机5规则图灵机，并发表了论文。但是证明这就是耐力最好的5规则图灵机则让数学家们花了35年。
2022年，20多个业余的数学家汇聚在数学研究生Tristan Stérin建立的网上社区。在这个名为“忙碌海狸挑战（Busy Beaver Challenge）”的社区中大家共同努力像完美证明BB(5)努力。
最后网名mxdys的神秘人踢出了“临门一脚”，他在团队成果的基础上，在名为Coq的交互式定理证明辅助工具中用一个40000行程序证明了那台在4700万步后停止运转的图灵机，确实是第五个忙碌海狸数。
Coq工具能帮助数学证明的过程不会出现错误。有人曾用它证明了四色定理和法伊特—汤普森定理
BB(6)是个超级大数
在证明BB(5)之后，团队中部分成员开始冲击下一个忙碌海狸数。这次的新纪录就来自mxdys，最近他宣布BB(6)的新下限是2↑↑↑5。
这个数字的写法很特殊，因为用普通十进制记法根本不可能写出来——只拿出一小部分数字就够给宇宙中每个原子都编上号。因此需要用指数、套指数、再套指数……的五级运算来描述这个数字：2↑↑↑5。
如何理解这个数呢？
在加法和乘法之后，三级运算是乘方运算（exponentiation），用xn表示n个x相乘，这也叫指数运算。
之后四级运算是超乘方（Tetration）运算，用X↑↑n来表示将X自乘n次。如2↑↑4=2^(2^(2^2))=65536。
之后继续扩展成五级运算的五则超幂（pentation）运算，用X↑↑↑n表示：
X↑↑↑n = X↑↑(X↑↑(…↑↑X)) 共n个X。
如2↑↑↑4 = 2↑↑(2↑↑65536)，这已经很庞大的数字了。
对普通人来说，能理解五级运算已经很好了，而寻找忙碌的海狸函数仅对少数数学家和计算机科学家有意义，而且寻找BB(6)在短期内不可能获得结果，这不仅需要计算机硬件的突破，也需要计算机软件和数学理论上的突破。
欢迎通过邮局渠道订阅2025年《电脑报》
邮发代号：77-19
单价：8元，年价：400元
编辑｜张毅
主编｜黎坤
总编辑｜吴新
爆料联系：cpcfan1874（微信）
壹零社：用图文、视频记录科技互联网新鲜事、电商生活、云计算、ICT领域、消费电子，商业故事。《中国知网》每周全文收录；中国科技报刊100强；2021年微博百万粉丝俱乐部成员；2022年抖音优质科技内容创作者
盈胜优配提示：文章来自网络，不代表本站观点。
热点资讯
