陶哲轩转赞！40 多年「忙碌海狸」数学难题获突破，4 万行 Coq 代码立大功

luyuanhong

陶哲轩转赞！40 多年「忙碌海狸」数学难题获突破，4 万行 Coq 代码立大功

来源：新智元 新智元 2024 年 07 月 03 日 14:21 北京



【新智元导读】「忙碌海狸」难题困扰了计算机科学家 40 多年。如今，来自全球各地 20+ 业余开发者和数学家们，终于取得了突破性进展。他们抓到了第五只忙碌海狸——用 Coq 辅助证明，得到答案 47176870 。对此陶哲轩激动地表示，这再次体现了证明助手对数学研究协作的重要性。

40 多年的计算机难题——「忙碌海狸」难题，今天获得了重大突破了！

著名数学家陶哲轩转发了这一消息，欣慰地表示：这再一次体现了证明助手对于数学研究的协作是有多么有用。



计算机科学家 Scott Aaronson 为此还写了一篇博文，并称「这个发现是自 1983 年以来『忙碌海狸』函数研究中最重要的进展」。



40 年前，100 多名计算机科学家在西德的多特蒙德市，参加了这样一场奇怪的竞赛，选手需要捕捉一种难以捉摸的目标——忙碌海狸。

这次竞赛难度极大，因为只有四只海狸被成功捕获，第五只忙碌海狸逃脱了。

其实，这些海狸其实是一种看起来简单、运行时间奇长的计算机程序。这些程序异常活跃，对它们的搜索过程，涉及到了一些最著名的数学未解之谜。

甚至可以说，海狸难题直接根植于一个和计算机科学本身一样古老的不可解问题。

虽然我们知道自己无法战胜数学定律，但我们希望赢得一场战斗。——三位参赛者

两年前，一位名叫 Tristan Stérin 的研究生建起一个网站，再次向全世界发起忙碌海狸挑战赛。

今天，有团队宣布——他们成功捕捉到了「第五只忙碌海狸」！这是由 20 多位来自世界各地业余爱好者组成的团队。



答案是 47176870

具体来说，他们验证了一个名为 BB(5) 的数字的真值，这个数字量化了第五只海狸的忙碌程度。

获得这个结果的过程中，团队使用一个名为 Coq 的证明助手软件，后者可以确保数学证明没有错误。



圣塔菲研究所的计算机科学家 Cristopher Moore 这样评价：「他们为了达到目标所进行的社会学和数学工程，实在令人印象深刻」

「我惊讶于他们完成得如此之快，」爱尔兰梅努斯大学的计算机科学家、Stérin 的导师 Damien Woods 说。「这简直达到了 Usain Bolt 的水平。」

可以说，寻找忙碌海狸最终是一场为了荣誉的狩猎。

因为，BB(5) 的具体数值在计算机科学的其他领域并没有任何用处。

但对于捕捉忙碌海狸的猎人来说，战胜数学不可能性后取得的胜利，本身就是回报。



停机，还是不停机

牵动广大忙碌海狸猎人的程序，不是用普通编程语言编写的，而是为图灵机编写的指令。

计算机科学家艾伦·图灵在 1936 年设计了图灵机，从而以数学方式为计算过程建模。



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

每台图灵机都有一套独特的规则。

每条规则规定了读写头在进入一个新的单元格时应该做什么，取决于它遇到的是 0 还是 1 。

这意味着，图灵机的指令可以用一个表格来总结，每条规则占一行，两列分别对应读写头遇到 0 和遇到 1 的情况。

一条规则可能是：「如果读到 0 ，将其替换为 1 ，向右移动一步，并参照规则 C 」，这是第一列。

「如果读到 1 ，保持不变，向左移动一步，并参照规则 A 」，这是第二列。

所有规则都如此，除非某个特殊规则告诉机器何时停止运行。



不过，虽然图灵机有停机的方法，但并不意味着它会停。

在最简单的情况下，它可能会陷入一个无限循环中，不断循环几个状态。

是否存在这样一种方法，可以判断具有特定规则集的图灵机是会停机，还是会永远运行下去呢？

这，就是著名的停机问题的本质，也是使得海狸难题如此迷人的原因。

图灵证明了停机问题没有普遍的解决方案——我们永远无法确定，对一台机器有效的方法是否对另一台机器也同样有效。

好在，停机问题并不总是对特定的机器来说很难。

有些机器会相对较快地停机。

这台三规则图灵机在 11 步后停机。

而有的机器却很快陷入了无限循环。

这台三规则图灵机很快陷入了无限循环。

我们总会遇到一些难以轻易分类的图灵机——它的运行会很快结束，还是会在磁带上永远徘徊？

是的，除非它运行足够长的时间，否则我们根本不知道，它会做什么。

忙碌海狸，在不可知边缘探索

忙碌海狸的故事，始于数学家 Tibor Radó 。


1895 年出生于匈牙利，大学学习的是土木工程。一战爆发后，在西伯利亚战俘营的同伴指导下开始学习数学

后来他重返校园，在俄亥俄州立大学任教 35 年。

关于停机问题，他对图灵的证明并不满意。

为了将这个问题的本质提炼得更简单，Radó 希望根据图灵机的规则数量进行分类——所有一规则图灵机为一组，所有二规则图灵机为另一组，依此类推。

如此一来，虽然会因图灵机可以有任意数量的规则而被分成无限多的组，但由于规则的组合是有限的，所以每组中的不同机器数量也是有限的。

这样推理，就比考虑所有的机器容易多了。

在 1962 年的一篇论文中，Radó 基于此提出了「忙碌海狸游戏」。



要进行这个游戏，首先需要选择一个组——也就是你机器的规则数量。

给组中的每台机器提供一条每个单元格都是 0 的磁带后，有些机器会一直运行下去，其余的最终会停机。

其中有些会很快停机，有些会花更长时间，而有一台会是最后一个停机的。每个组都会有一个运行时间最长的成员，这些特别勤奋的机器，就被称为「忙碌海狸」。

在拥有 n 条规则的组中，忙碌海狸机器在停机前所需的步数，就是相应的忙碌海狸数 BB(n) 。而游戏的目标，是确定这些数字的确切值。



仔细一想就知道，解决「忙碌海狸」需要考虑众多问题。

要成功的话，你必须确定每台停机机器的运行时间，看看哪台花费的时间最长。你还必须证明所有其他的机器永远不会停机。

测量运行时间当然很简单，因为在普通计算机上模拟图灵机很容易。

但是，想要证明一台机器永远运行下去，相当于为它解决停机问题的具体版本——在最一般形式下，这几乎是不可能完成的任务。

「我们在不可知的边缘进行探索，」软件工程师、海狸难题的贡献者 Shawn Ligocki 这样说。

但不可知性究竟从哪里开始？

只有几个规则的图灵机看起来非常简单。理解一个可以放在索引卡上的程序有多难？

数学研究生的海狸团队

单一规则的情况很简单，因为实际上只有两种可能性。

如果规则告诉图灵机在看到 0 时停机，它会在第一步就停止。任何其他规则都会导致机器永远在磁带上前进，因为它会在每个单元格中遇到 0 。这意味着 BB(1) = 1 。

除了这个小海狸，一个只用铅笔和纸装备的猎人很快就会遇到问题。对于两规则的情况，已经有超过 6000 个不同的图灵机需要考虑；这个数字在三规则时膨胀到数百万，在四规则时膨胀到数十亿。

手工处理所有这些情况是不可能的。「显然，你不可能做到这一点，」 Ligocki 说。「即使你能做到，也没有人会相信你。」

这意味着，这个根植于计算基础的问题只能在计算机的帮助下解决。

是的，一个相当简单的程序足以证明 BB(2) = 6 ，但从 BB(3) 起，就开始变得困难多了。



而 Radó 介绍这个游戏后不久，一小部分研究人员开始了这场狩猎。

Oregon State University 的数学研究生 Allen Brady 很快就意识到，取得进展的关键，就是忽略图灵机之间不重要的差异。

例如，考虑一个有许多规则的图灵机，其中第一个规则告诉它如果读取到 0 就停机。

「其余那些转换中的内容并不重要，因为它会立即停机，」 Ligocki 说。就忙碌海狸游戏而言，这些机器大多数是多余的，因此可以直接一次性排除它们。



研究生 Brady 将这个过程，整合到一个用于模拟图灵机的计算机程序中。

基于机器初始行为的相似性，这个程序为具有相同规则数量的机器构建了一个类似家族树的结构。

只有当机器之间的差异变得相关时，程序才会将树分成多个分支，并删除在模拟中停机或进入无限循环的整个分支。

程序是编出来了，但找到能运行它的计算机，在 1964 年时并不容易。

终于，Brady 获得了 90 英里外一个灵长类研究实验室计算机的使用权。



没想到，工作进行到一半，Brady 发现自己被半路截胡了：Radó 的研究生 Shen Lin 已经证明了第三个忙碌海狸数 BB(3) = 21 。



Brady 并未气馁，不仅确认了 Lin 的结果，而且在 BB(4) 上取得了部分突破——此前，Radó 认为 BB(4) 「完全无望」解决。

BB(4) 之所以难解，不仅是因为问题数量庞大，更因为四条规则的机器能够表现出的行为，实在是太丰富了！

所有不停机的两规则机器，都会陷入容易检测的无限循环。

在三规则的情况下，有几十台机器会永远运行而不进入循环，而证明这些机器永不停机，需要不同的方法。

对于四规则的机器，则有成千上万台这种非循环机器。



毕业后，Brady 识别出了一些新的非停机图灵机种类，并给它们起了「影树」和「尾食龙」之类的奇幻名字。

1966 年，他发现了一台四规则机器，在停机前运行了 107 步，他猜测：这就是难以捉摸的第四个忙碌海狸。

他的猜想是对的，但直到 1974 年，他才证明没有其他停机机器能运行得更久。

他在一份内部技术报告中写下了证明，但直到九年后，报告才在学术期刊上发表。

这是人类在超过 40 年里，所知道的最后一个忙碌海狸数。

第五只忙碌海狸诞生！

Brady 发表证明的那一年，也是多特蒙德比赛——第一次寻找第 5 个忙碌海狸的大型竞赛的那一年。

对于五规则机器，可能的图灵机数量接近 17 万亿。即使以每毫秒一个的速度列出所有这些机器，也需要超过 500 年。

用 Brady 家谱方法来缩小搜索空间仍然必不可少，但程序必须运行得非常快，才有希望成功。

参赛者们各自开发了自己的程序，并且找到了运行时间最长的五规则图灵机——最忙的那台，在超过 100,000 步后停机。

《科学美国人》 1984 年对比赛报道后，不久后就有一位研究者打破了多特蒙德的纪录：一台机器在超过 200 万步后才停机。

柏林的研究生 Heiner Marxen 和 Jürgen Buntrock ，也开始利用业余时间研究这个问题。



几年后，在 1989 年 Marxen 成为了程序员，在公司中获得了一台强大的计算机。

竟然凭自己的程序找到了一台惊人的机器，在 47176870 步后才停机。

起初，他认为代码中肯定有错误。

但调试了几个小时后，他开始有一种奇怪的感觉：自己捕获到了忙碌海狸。

Buntrock 很快复现了这一结果，两人发表了论文。

虽然 Marxen 捕获了忙碌海狸，但证明所有剩余的机器都不会停机，则花了超过 30 年。

在 2000 年初，一位名叫 Georgi Ivanov Georgiev 的保加利亚计算机科学家几乎成功了。



当时，他在一家国有电信公司担任系统管理员。他痴迷于 BB(5) 的研究，花了两年时间，每天花数小时改进一个可以识别新型非停机机器的程序。

最终的程序有 6000 行密集且没有注释的代码，运行时间超过一周。它留下了大约 100 台未决的图灵机。

手工分析这些机器后，他将名单缩减到 43 台。

2003 年，Georgiev 在网上发布了成果。

Marxen 鼓励 Georgiev 继续努力，但两年的高强度工作已经让他筋疲力尽。

「这段时间结束时，我无法再产生任何新想法，我非常疲惫。」

这也是忙碌海狸研究者所共同面临的困境。

几十年来，他们或独自或成对地辛勤工作，却没有得到广泛学术界的太多认可。但是要完成这项工作，显然需要集体的努力。

luyuanhong

召集所有猎手

召集所有猎手的努力，始于 Tristan Stérin 。

2000 年代末，他最初通过 IM 结识了一位编程竞赛爱好者，从而早早精通了计算机编程。

但他很快意识到编程竞赛的文化，并不适合自己。


2022 年，Tristan Stérin 发起了忙碌海狸挑战赛，这是一项在线合作，旨在最终确定第五个忙碌海狸数量的价值

他表示，「我不是一个喜欢竞争的人。我喜欢看到一个问题，然后花 3 个月时间思考它，而不是只花 30 分钟」。

在好奇心的驱使下，Stérin 决定从法国来到爱尔兰攻读研究生，在那里他与 Woods 一起研究 DNA 计算，即如何使用 DNA 链实现算法。

2020 年夏天，Woods 给他发了一篇关于「忙碌海狸」的综述论文，作者是计算机科学家 Scott Aaronson 。

Stérin 立即被这篇文章吸引了。


论文地址：https://dl.acm.org/doi/10.1145/3427361.3427369

在与 Woods 合作撰写了一篇关于大型图灵机能力的论文后，他转向研究 BB(5) 问题，并下定决心要最终证明—— Marxen 和 Buntrock 的 4700 万步机器，确实是第五个「忙碌海狸」。

Stérin 说，「我有强烈的直觉，自己做不到。但我也有一种直觉，这件事是可以做到的」。


论文地址：https://arxiv.org/pdf/2107.12475

从一开始，Stérin 就知道，要有结论性的证明，必须有良好的文档记录和可重复性，因为任何微小的软件错误都会对整个研究造成致命打击。

Georgiev 的程序极其复杂，但其他研究人员发现它难以解析。

参与「忙碌海狸」挑战赛的软件开发人员 Justin Blanchard 表示，「当你回头试图审查代码时，你会马上放弃。任何新的方法实际上都得从头开始」。他曾是一名数学专业的研究生。

Stérin 决定在传统方法的基础上进行一些改进。

他首先使用 Brady 的家族树（Brady's family-tree）方法，来消除冗余的图灵机，并识别出哪些机器在 4700 万步内停机。



但与 Brady 或其后继者不同的是，Stérin 没有包含任何用于剔除永远运行的机器的代码。

相反，他计划使用独立的程序来解决这些问题，每种方法对应一个程序，证明图灵机永远不会停机。

这样分块处理任务，将使合作伙伴更容易独立地完成每个部分，并交叉检查结果。

2021 年底，Stérin 编写了第一步的计算机程序。

它生成了大约 1.2 亿台图灵机的列表，这些图灵机足以确定 BB(5) 的值——其余的都是冗余的。

在这 1.2 亿台图灵机中，大约 1/4 在 Marxen 和 Buntrock 的机器之前就停机了，剩下的 8800 万台仍在考虑范围内。

为了帮助分析这些图灵机，Stérin 构建了一个在线界面，用于在「时空图」上可视化它们的行为，时空图是由代表 0 和 1 的黑白方格组成的二维网格。

图中的每一行记录了图灵机演化过程中的一步。

第一行代表第一步后的纸带状态，第二行显示第二步后的纸带状态，依此类推。

以这种方式查看，Stérin 收集的图灵机仿佛活了过来，展示出令人眼花缭乱的各种不同模式。

要证明 Marxen 和 Buntrock 确实找到了第五个忙碌海狸，就意味着要证明这些机器中的每一个都会永远运行下去。



Stérin 知道，自己无法单独完成这项任务。

2022 年春天，Stérin 和一些早期加入者在独立平台 Discord 上，创建了一个论坛和一个单独的聊天服务器。

然后，是时候寻找贡献者了。

「忙碌海狸」的魅力

Shawn Ligocki 很快加入了团队。



也许这是命运：他 1985 年出生在 Beaverton ，虽然他第一次听说「忙碌海狸」是在 2004 年，当时在他大学第一学期结束时。

寒假期间，他和他的父亲 Terry 一起开始研究海狸搜索算法，Terry 是劳伦斯伯克利国家实验室的一名应用数学家。

一个月后，当 Ligocki 回到大学忙于课程时，他的父亲兴奋地打电话给他。

他决定在 Brady 发明的原始忙碌海狸游戏的一个变体上，测试他们的一个算法，并发现了一台打破 Brady 记录的图灵机。

他们联系了已经退休的 Brady ，Brady 很高兴并在他的网站上公布了这个结果。



随之，Shawn Ligocki 很快与世界各地的「忙碌海狸」研究人员通过电子邮件进行交流。

有一次难忘的经历发生在 Ligocki 大二暑假访问德国期间，他顺道去了柏林与 Marxen 见面。



忙碌海狸的魅力，伴随着 Ligocki 整个大学期间，但毕业找到工作后，生活琐事让他分心。

他偶尔会重新投入忙碌海狸的研究，但从未持续太久。

2022 年初，他建立了一个在线讨论组，帮助研究人员保持联系。5 月时，Stérin 发现了这个邮件列表，并发出加入忙碌海狸挑战的邀请。Ligocki 毫不犹豫地接受了邀请。

他对项目的首次贡献之一，是复兴了 Marxen 发明的一种技术，这是他们 16 年前在柏林酒吧讨论过的技术。

这种技术被称为「封闭磁带语言」（the closed tape language）方法。这是一种新方法，用于识别图灵机磁带上永不停止的模式。

这是识别循环程序和许多其他图灵机不停机的基本策略，但「封闭磁带语言」方法有潜力通过统一的数学框架识别更广泛的模式类别。

Ligocki 写了一篇博客文章，向他的新合作者介绍了这项技术，但尽管理论上的想法非常通用，他并不知道如何编写一个涵盖所有情况的程序。



Justin Blanchard 在秋天加入项目后不久，就找到了方法，但他的程序相对较慢。然后另外两位贡献者找到了让它运行更快的方法。

在几个月内，「封闭磁带语言」技术从一个有前途的想法变成了他们最强大的工具之一。

它甚至可以处理 Georgiev 的 43 个未解决问题中的 10 个，为纪念他而被称为「Skelet 图灵机」。



怪物「图灵机」来袭

随着时间的推移，新的贡献者们发现了「忙碌海狸」挑战，并开始逐步解决问题的不同部分。

但许多图灵机仍未解决，其中有两台图灵机尤其声名狼藉。

第一台是 Skelet #1 ，它在可预测和混乱的行为之间不断交替。



在 2023 年 3 月，Ligocki 和 Pavel Kropitz ——一位不会说英语的斯洛伐克贡献者，通过谷歌翻译与团队其他成员交流——提出了一系列想法，终于破解了它。

使用 Marxen 和 Buntrock 30 年前的加速模拟技术的升级版，他们发现秩序与混乱之间的拉锯战确实结束了，但只有在超过一万亿亿步之后。

然后它最终进入了一个异常长的重复循环周期。

实际上，几乎所有的无限循环在 1000 步内就会开始重复；而 Skelet #1 的循环超过了 80 亿步之长。



这台图灵机的行为非常诡异，证明过程融合了许多不同的想法，以至于 Ligocki 在近 5 个月内都无法确定结果。

不过，这一不确定重复周期，被一位新贡献者打破了——一位 21 岁的自学成才的程序员，名叫 Maja Kadziolka ，多数情况在她只用一个字 mei 。

mei 在波兰长大，并在 2021 年秋季在华沙大学学习了一个学期后辍学。

随后，她在一家软件公司工作了一年多，但越来越觉得工作令人筋疲力尽，开始寻找更具智力挑战的工作。

偶然的机会，她在软件 Coq 中找到了这种兴趣，这是一款设计用于编码和验证数学证明有效性的软件。

当时，忙碌海狸挑战的贡献者们已经在证明中使用计算机程序，但就像纸笔证明一样，计算机程序也容易出错。

而在 Coq 证明中，代码只有在每一行逻辑上都能从前一行推导出来时才能运行，这使得错误几乎不可能发生。

对 mei 来说，弄清楚如何制作这些证明开始变得像一场游戏。

在学习了 Coq 之后，mei 开始寻找一个开放的问题来测试它。就在那时，她发现了忙碌海狸挑战。

几周后，她将团队的几项证明用 Coq 重新编写，包括 Ligocki 和 Kropitz 关于 Skelet #1 永不停止的证明—— Ligocki 终于可以确定这一点了。

突然间，比 Stérin 强调的可重复性更高的严格标准，似乎成为可能。


项目地址：https://github.com/meithecatte/busycoq

而这一切都是由一个没有正式训练的人——一个业余数学家做出来的。

突破性进展

大约在同一时间，一位名叫 Chris Xu 的研究生，在第二台怪物图灵机—— Skelet #17 上取得了突破。

通常，即使是复杂的五规则图灵机（five-rule Turing machines），一旦理解了其工作原理，总结其行为也不难。

通过研究 Skelet #17 磁带上的模式来理解它，就像解密四层加密的秘密信息一样：破解一个代码只是揭示了另一个完全不相关的代码，并且下面还有两个。

Xu 必须解密所有这些代码，才能最终证明这台机器从未停止。



Xu 的证明非常出色，但它涉及一些无人知道，如何用 Coq 所要求的精确术语形式化的数学直觉。

而且，忙碌海狸挑战的工作还远未完成：虽然 Skelet #1 和 #17 是看起来最难对付的两台图灵机，但还有其他一些图灵机需要解决，还有一些只使用低效程序解决的图灵机。

这不足以说服世界。

在接下来的几个月里，社区慢慢拼凑出剩余图灵机的证明，但大多数还没有被翻译成 Coq 。

然后在四月，一个神秘的新贡献者出现了，他用化名 mxdys 来完成这项工作。



团队中没有人知道 mxdys 的所在地或其他个人信息。在一次 Discord 私信交流中，他提到对数学游戏有长期兴趣，但拒绝提供更多关于他背景的信息。

5 月 10 日，mxdys 在 Discord 服务器上发布了一条简短的消息：「BB(5) 的 Coq 证明已经完成」。

一分钟后，Stérin 回复了一串七个感叹号。

在几周内，mxdys 完善了社区的技术，并将他们的结果综合成一个 40,000 行的 Coq 证明。

法国国家研究院 Inria 的 Coq 专家 Yannick Forster 在审查证明后表示，「这不是一件容易形式化的事，我仍对此感到惊讶」。

Marxen 和 Buntrock 在 30 多年前发现的那台在 4700 万步后停止运转的图灵机，确实是第五个忙碌海狸。

「这个消息对我来说非常令人兴奋，」Georgiev 在一封电子邮件中写道。「我从未想到这个问题会在我有生之年得到解决。」

但对另一位忙碌海狸挑战的开创者来说，这个消息来得太晚了。

Allen Brady 于 4 月 21 日去世，距离证明完成不到一个月，享年 90 岁。



贡献人员名单

以下是所有参与这次证明 BB(5) = 47176870 的贡献人员名单。





下一步探索

忙碌海狸挑战的参与者们已经开始起草一篇正式的学术论文，描述他们的成果，并用更易理解的证明来补充 mxdys 的 Coq 证明。

这将需要一些时间：大多数图灵机通过多种方法被证明不会停止，团队需要决定如何最佳地将这些结果组合成一个完整的证明。



与此同时，部分团队成员已经开始研究下一个忙碌海狸。

然而就在四天前，mxdys 和另一位名为 Racheline 的贡献者发现了 BB(6) 的一个似乎无法逾越的障碍：一个六规则图灵机，其停机问题类似于一个著名的数学难题—— Collatz 猜想。

图灵机与 Collatz 猜想之间的联系，可以追溯到 1993 年数学家 Pascal Michel 的一篇论文。

但新发现的图灵机，被称为「Antihydra」，是迄今为止最小的一个，似乎在没有数学上的概念性突破的情况下无法解决。


论文地址：https://link.springer.com/article/10.1007/BF01409968

显然，可以想象的到，BB(5) 将是我们所知道的最后一个忙碌海狸的数字。



忙碌海狸问题有许多不同的变种，一些忙碌海狸挑战的参与者计划继续研究这些变种。但并不是所有人都打算继续这项工作。

他们各自因为不同的原因参与到这个项目中，现在他们的研究道路开始分道扬镳。

Stérin 希望开发软件工具，以促进其他数学领域的在线协作。

他表示，「忙碌海狸挑战带给我的是一种非常深刻的信念，它是一种非常有效的研究方式」。

参考资料：

https://www.quantamagazine.org/a ... g-machine-20240702/

https://mathstodon.xyz/@TaliaRinger/112719444060361451

新智元报道