How Amateurs Solved a Major Computer Science Puzzle
24:40 Share

你知道有一位古人类学家在冲突地区寻找化石吗？这只是我们在《Going Wild》中分享的精彩故事之一，这是一个由PBS自然频道制作的获奖播客，由我——野生动物生态学家Rae Winn-Grant博士主持。

在《Going Wild》全新一季中，我们将重点介绍一些最酷的自然保护者，例如TikTok上的黑人觅食者Alexis Nicole Nelson和普利策奖获奖科学记者Ed Yong，探索是什么促使他们在自身和自然界中创造改变。获得灵感。在您最喜爱的播客应用程序上关注Rae Wyn Grant博士的《Going Wild》。

我喜欢谜题，至少是某些类型的谜题。我有时间就会做《纽约时报》周日填字游戏。我从数独转向其他逻辑谜题，来自这家名为Nikoli的日本谜题杂志。

我的家人每年节日期间都会玩拼图游戏。我不是数学家或计算机科学家，但我欣赏某些数学证明中类似谜题的求解和结构。我怀疑解决这些问题的人可能会从中获得更大的满足感，尤其是那些需要几十年甚至几代人才能解开的谜题。

欢迎收听《Quanta播客》，我们将探索基础科学和数学的前沿领域。我是Samir Patel，Quanta杂志的主编。本周是解决一个不同寻常的智力谜题的解决方案发现一周年纪念日，我们的计算机科学撰稿人Ben Brubaker在去年它发生时就写过一篇关于它的文章，名为“有了第五个忙碌的海狸，研究人员接近了计算的极限”。

Ben今天和我们一起深入探讨难以捉摸而奇特的忙碌的海狸游戏以及最新解决方案的意外来源。欢迎回来，Ben。谢谢。很高兴回来。这是我最喜欢的主题之一。让我们从大方向开始吧？我们今天的谈话要谈些什么？忙碌的海狸游戏是一个关于简单的计算机程序可以做的最奇怪、最不可预测的事情的数学谜题。

我喜欢它的一点是，它吸引了许多并非数学或计算机科学专业研究人员的人。他们只是出于对游戏的热爱。你提到的去年取得的重大突破来自一群在网上合作的人，开放合作。任何人都可以加入。事实证明，这是一个非常有趣的人的故事，也是关于一些令人惊叹的数学和计算机科学的故事。你是一个喜欢谜题的人吗？

我以为你永远不会问，Smear。是的，我喜欢谜题。我喜欢填字游戏和许多其他文字游戏。有一段时间，我痴迷于玩一款名为Redactyl的每日益智游戏，它类似于Wordle，只不过你不是试图猜测一个隐藏的单词，而是试图猜测一个隐藏的维基百科文章的主题。但我有点太痴迷了，所以我不得不停下来。

好的，在我们开始讨论你报道的这个具有里程碑意义的谜题解决方案之前，我认为我们需要先说明一下这个游戏的规则。是的。因此，忙碌的海狸游戏发明于1962年。它是数学家Tibor Rado发明的，他有着一段我在这里没有时间详细介绍的精彩人生，但请阅读这篇文章。是的。所以基本上——

目标是找到运行时间过长但不会永远运行的简单计算机程序。它们最终会停止运行。那些将这种行为发挥到极致的程序被称为忙碌的海狸。Rado之所以这样称呼它们，是因为海狸以勤劳而闻名。

那么，为什么要搜索一个运行时间很长的计算机程序呢？是的，这听起来有点倒退。通常，你想要运行时间短、速度快的计算机程序。这些长时间运行的计算机程序之所以有趣，是因为尝试找到它们的这个过程迫使你努力解决计算机科学中最大的问题之一，这基本上就像，如果我给你一些任意计算机程序的代码，你能否判断它是否会永远运行或停止运行？好的，我们知道……

有很多不同的计算机语言，有很多方法可以编写计算机程序。我假设为了使这个游戏具有相关性，我们必须转向某种一致的计算

环境。是的，没错。当这个领域的人谈论计算机程序时，他们说的不是你在计算机上熟悉的普通程序。他们说的是所谓的图灵机，这是计算机程序的理论数学模型。这些模型是100年前发明的。你永远无法真正制造出一台图灵机，但原则上它可以做任何其他计算机程序可以做的任何事情。因此，你可以用它来数学地推理计算。

这可以追溯到提出这个想法的计算先驱艾伦·图灵。让我们快速谈谈什么是图灵机。图灵机有三个部分。第一部分是一条磁带，就像一维条带。你可以把它想象成胶片条或类似的东西。它被分成单元格。每个单元格中可以包含一个1或一个0，并且它无限长。这就是你无法制造图灵机的第一个原因。

第二个组件称为磁头，它能够读取和写入磁带上的这些单元格。我喜欢我们优秀的艺术部门选择将其描绘成索伦之眼类型的东西。非常酷。因此，磁头基本上可以查看磁带，它可以看到0或1，并且可以选择更改它或不更改它。然后它可以沿着磁带移动或一次将磁带移动一个方格到左边或右边。

然后第三个组件是，它如何决定对磁带做什么？这是一个规则列表。它就像关于图灵机现在应该做什么的指令。

例如，规则A可能说，如果你当前读取的符号是0，则将其替换为1，向左移动一步，当你到达那里时查看规则B。但是如果你读取的是1，则执行其他操作。因此，磁头可以读取0或1，这告诉它在单元格中写入什么，在磁带上移动哪个方向以及接下来遵循哪个规则。这个一般的规则结构只有一个例外，那就是当它发出停止或结束程序的指令而不是转到另一个规则时。

这就是图灵机。我们回到Rado。我们要编写一个程序，也就是图灵机的规则序列，使其尽可能长时间运行。

但仍然会停止。没错。因此，你首先要做的是选择一个特定的规则数量。例如，假设有两个规则。这些规则具有这种非常具体的形式。写一个0或1，向左或向右移动一个单元格，然后转到另一个规则。对于两个规则或任何特定数量的规则，只有有限数量的机器。因此，它们都属于两类，一些由于某种原因而永远运行，一些则到达告诉程序停止的规则。

因此，如果你想找到运行时间最长然后肯定停止的那个，首先你必须将可能的机器分成这两类。但是弄清楚图灵机是否真的停止了，这被称为停机问题，它是计算机科学中的核心问题之一。是的，让我们谈谈停机问题。你可以编写一个旨在给你一些答案然后停止的计算机程序。可能导致计算机程序无法停止的一些问题是什么？

你可以很容易地编写一个不会停止的计算机程序。例如，只需打印数字1，然后加1，然后打印下一个数字，并不断循环并加1。所以这并不是……它只是继续下去。它只是越来越大，永远持续下去。所以对。除非你手动中断这个东西，否则它不会停止。

但是，计算机程序还可能做各种其他疯狂的事情，例如可能存在某种条件，例如如果你到达这一点，就停止。但它可能永远不会到达那里，因为它正在磁带上进行某种疯狂的0和1写入模式，并且它在这个指令列表中来回跳动，但它永远不会到达想要停止的情况。它最终会陷入循环，对吧？所以它永远不会到达停机状态。对，是的。所以你可能有一个陷入无限循环的程序，但由于磁带是无限的，它可能永远不会开始做完全相同的事情，但仍然会永远运行。好的。

因此，Rado定义了这个问题，他说，让我们使用一台图灵机，以便每个人都在功能上使用相同的谜题环境。让我们确定对于给定的图灵机规则数量，运行时间最长且最终停止的最长程序是什么。是的。所以我们从一个规则开始。是的。图灵机的一个规则是什么样的？所以当游戏开始时，磁带中的每个单元格都被设置为0。

而只有一个规则的图灵机非常简单，因为它可以说，如果你读取0，则停止，或者它可以说，如果你读取0，则执行其他操作，例如可能写入另一个0并向右移动。但它只会遇到另一个0，并且没有其他规则可查看。因此，除非它立即停止，否则它必须继续永远重复相同的操作。

所以考虑一下这一点，你会发现在一个规则的情况下，它可以运行的最长时间并确保停止是一步。否则，它将永远运行。对，好的。所以用忙碌的海狸猎人的说法，这样说就是BB of 1等于1。忙碌的海狸游戏是关于寻找这些忙碌的海狸数，BB of 1、BB of 2、BB of 3等等，它们代表特定规则数量的最长运行时间。你添加的规则越多，就越难。

好的。所以现在我们来看两个规则。两个规则。有多少不同的图灵机有两个规则？这是一个很好的问题，因为随着你增加规则的数量，将会发生的一件事是可能性数量将会增加。在这种情况下，对于两个规则，将会有大约6000台图灵机。

这听起来很疯狂。但是例如，其中一些可能类似于，哦，这个与另一个看起来相同，除了所有左右都被交换了。所以这种差异无关紧要。或者其中一些会立即停止，但它们在这个表的其他所有单元格中都有不同的条目。我们不必担心这些，因为它们都会立即停止。所以有一些方法可以减少这个数字。但我们从6000开始。是的。我们的益智游戏然后是确定这6000个中哪个运行时间最长并结束。是的。好的。好的。

所以我想对于两个和6000，他们相对较快地找到了答案。是的。所以这也不难，因为对于2来说，很长一段时间实际上是6步。这是最大步数。所以BB2等于6。好的。BB3呢？

BB-2可能需要几个小时，几天。我不知道。BB-3是Rado的博士生Shen Lin的博士论文。所以，你知道，这已经很难了。事实证明答案是21。所以这花了几年时间才弄清楚。有多少台机器有三个规则？在这种情况下，大约有几百万台机器。几百万台机器。好的。所以这花了几年时间和一篇博士论文。BB-4呢？

所以BB-4是一个人长期努力的结果。有数十亿台图灵机。另一件事是，当你添加更多规则时，不仅有更多图灵机，而且它们所做的事情也会变得更加复杂和难以理解。所以这花了他大约10年时间。最终，他发现BB-4是107。所以任何使用四个规则运行超过107步的东西，都会永远运行。是谁做了这项工作？他的名字是Alan Brady，他是一位计算机科学家。

对。所以你的故事所讲述的谜题是BB-5。没错。所以让我们为BB-5奠定基础。有多少个五规则图灵机？大约有17万亿个五规则图灵机。这是一个非常大的数字。好的。17万亿个五规则图灵机。我们需要找到运行时间最长且会停止的那个。是的。那么，从策略上讲，如何才能弄清楚……

答案是什么。首先，你不可能在人类的一生中评估17万亿个任何东西。因此，你需要找到这种自动减少数量的方法。然后，你想要编写一个计算机程序，该程序尽可能识别出停止的机器。然后你可以关注那些运行时间很长的机器，并尝试弄清楚它们是否真的会永远运行。你想要通过寻找模式来做到这一点。

例如，一种类型的模式可能只是一个循环，啊，这个图灵机回到了它之前所处的完全相同的配置。由于没有随机性，没有机会，没有自由意志，它只会永远做同样的事情。但是，还有其他更微妙的方法可以使事情永远运行。这些也可能有特征。所以你会寻找某种模式。这个程序会说，要么我找到了这种模式，因此我知道这会永远运行。或者它会说，我不知道，这不是我的问题。其他程序必须通过寻找其他模式来弄清楚这一点。

所以我们有一些人在研究这个问题，我假设将这个数字从17万亿减少到更易于管理的数字。是的，是的。早期研究这个问题的人拥有这些在一个程序中完成所有事情的程序。所以他们开始并减少可能性数量。与此同时，他们说，好吧，这个停止了，所以我将忽略它。而这个，我发现它进入了无限循环，所以我将忽略它。但他们并没有真正以一种非常系统的方式这样做。

方式。此时，大多数人可能是专业的计算机科学家，但同样，他们只是在业余时间这样做。尤其是在1989年，取得了第一次真正重大的突破，那就是Heinrich Marxson和Jürgen Buntrock，他们住在柏林，他们在几年前做过一些忙碌的海狸狩猎，而且并没有走得太远。

然后Markson在他的工作中得到了一台新电脑，他心想，好吧，让我测试一下我的旧程序，看看这台速度更快的新电脑，我能否让它运行更长时间，看看会发生什么。他在周末运行它。他回来后，它发现了一台运行时间超过4700万步的图灵机，然后它停止了。所以此时，我们知道BB5这个数字至少是4700万。但他没有一个全面的证明，证明其他所有东西都运行得更长。事实上，没有真正的方法知道。它可能长得多得多。

我假设此时，许多五规则机器已被排除在外。也许只剩下几个了，对吧？是的。所以，但由于每个人都在运行自己的程序来查找这些图灵机，因此没有像这些已解决而这些未解决的系统数据库。这只是计算机科学家和感兴趣的人在工作。

出于乐趣。是的，他们只是出于乐趣。大约10年后，保加利亚计算机科学家Georgiev Georgiev，他拥有博士学位，但他当时在电信公司担任系统管理员。所以他有一份他觉得非常无聊的工作。所以他正在寻找一些有趣的事情。他偶然发现了这个忙碌的海狸的事情，并且他全身心地投入其中。除了这件事之外，他什么也没做，大约几年时间。他编写了自己的程序，

最终证明了除最初开始的17万亿台机器中的43台机器外，所有机器都会永远运行或在一定时间内停止。所以到了21世纪初，我们有40多台机器需要证明是结束还是不结束。是的。

我假设随着互联网和各种聊天板的出现，有更多感兴趣的、聪明的、也许略微痴迷的人发现了忙碌的海狸游戏。所以是的，Georgiev和Markson以及所有其他人都通过邮件列表等方式相互联系，形成一个松散的网络。但很长时间以来，并没有真正进行系统的努力。所以故事在2022年真正开始加速，当时这位法国研究生Tristan Sterrin，

发现了忙碌的海狸游戏，他决定他想做一些类似于众包、分布式、有良好注释的、集中式系统来尝试解决这个问题。他想为这种混乱带来一些秩序，以便人们能够真正合作解决这个问题。是的。所以他基本上决定将其分解成几个部分。第一部分是缩小列表范围，并识别所有在4700万步内停止的机器。

然后每个单独的部分都类似于，寻找无限循环的机器。寻找具有这种其他永远运行特征的机器。因此，将程序分解成多个部分允许人们独立地处理不同的部分，并为解决这个问题提供一些整体结构。他创建了一个Discord服务器。它就像一个在线聊天板。许多人只是通过口碑开始慢慢加入。所以这个群体随着时间的推移慢慢壮大。他们都在处理这个问题的不同方面。

所以我想在一年或两年内，他们开始淘汰一些剩余的43个程序。是的。他们取得了多大的进展？

大约一年左右的时间里，他们已经将其减少到少数几个。他们已经用计算机程序证明了那些真正长时间运行的程序确实会永远运行。对。所以他们已经用计算机程序证明了这一点。并且仍然存在的问题是，计算机程序中可能存在错误。人们在做自己的事情。那么，你能对这些证明有多确定呢？但他们至少对几乎所有这些都有了一些了解。到2023年这个时候，他们只剩下几只“怪物”了。你所说的“怪物”是什么意思？

这些是你查看其行为后会感到震惊的图灵机，天哪，这是什么？我该如何理解呢？

所以我会告诉你一个例子。这被称为“骷髅一号”。这个名字来自Georgiev。他的在线用户名是Skelet。所以他们用他的名字命名了这43台机器。而Skelet在保加利亚语中是骷髅的意思吗？Skelet在保加利亚语中是骷髅的意思。明白了。因为他很瘦。这是他告诉我的。好的。所以“骷髅一号”是一种炮塔机，它在一段时间内会做一些相对有序的事情。你会想，哦，我想我知道这是如何运作的。然后它会爆炸成混乱的行为。然后它会回到某种有序的状态，然后爆炸成混乱的行为。所以……

它不断地违背你的直觉。事实证明，他们能够证明它至少在数万亿步内会在这两种有序和混乱之间交替出现，也许更多，比如数万亿万亿步。然后在所有这些之后，它会陷入无限循环。而这个无限循环长达80亿步，这也有些奇怪。一个80亿步的无限循环。是的。好的。而这是来自一台简单的图灵机。是的。

磁带上有单元格，有1和0，有五个规则。五个规则。你可以把它写在索引卡上。太神奇了。但他们最终确实发现它会陷入这个循环，对吧？接下来会发生什么？

此时，他们已经找到了所有这些机器的证明。所以下一个问题是，你是否有铁证证明这些机器会永远运行？此时，一些参与这个项目的人开始使用这种名为COQ的特殊编程语言。这是C-O-Q。这是一种用于保证数学证明有效性的编程语言。

所以他们开始将这些证明翻译成这种语言COQ。然后在2024年4月，一个新人出现在服务器上。用户名是MXDYS。没有人知道这是什么意思，也不知道是谁。只是一个匿名人士，就像，嘿，我对做这个COQ证明很感兴趣，这是我所做的。就像几周之内，就完成了这件事。神秘的用户潜伏者不知从哪里冒出来出现在Discord上。对。

并且基本上完成了它。是的，收集其他人已经完成的一些COQ证明，并使一些方法形式化，简化并提出一些新方法。但这基本上只是一个计算机程序。就像，运行这个程序，它将从第一性原理数学地证明所有这些机器都会永远运行。

所以这个新用户证明了那个4700万多，确切数字是多少？47,176,870。这个人证明了之前在周末运行的机器是BB-5的实际解决方案。没错。这就是第五个忙碌的海狸。我这里有两个问题。一个是……

除了对它从107到4700万的快速扩展感到惊奇之外，了解这个相对深奥而奇怪的谜题的解决方案是否具有内在价值？你可以肯定地说，在计算机科学中不会有实际应用，你会说，谢天谢地，我知道第五个忙碌的海狸数是47,176,870。

但是忙碌的海狸游戏确实有智力上的应用，不是吗？对。从某种意义上说，随着这些忙碌的海狸数变得越来越大，你可以将它们与数学中这些未解决的问题联系起来。然后你可以用它们来对这些未解决问题的难度进行分类，例如，这个问题与找到这个忙碌的海狸数一样难。而另一个问题与找到另一个忙碌的海狸数一样难。

所以自然而然的问题是，既然我们有了忙碌的海狸5的解决方案，忙碌的海狸6是怎么回事？

情况变得更糟了。我可以想象它会变得更糟。我想知道它会糟糕到什么程度？所以忙碌的海狸6之所以困难，主要有两个原因。一个原因是，正在研究这个问题的人已经知道一些运行时间非常长的图灵机。比宇宙中原子数量多得多是一种懒惰的比较，但比这多得多，以至于这几乎毫无意义。他们显然不是通过逐步运行它们来知道的，而是通过间接证明这一点。

然后它们停止了。但是还有许多其他机器可能运行更长时间然后停止。所以它至少是一个令人难以置信的比宇宙中原子数量多得多的数字。没错。好的。然后第二个问题是，他们发现了一个特殊的图灵机。他们称之为反九头蛇。

它是否停止的问题等同于一个与长期存在的未解决问题——科拉茨猜想非常相似的数学问题。因此，如果你能够解决这个问题，这几乎与科拉茨猜想相同，那么你就可以确定这台机器是否停止，反之亦然。人们长期以来一直在试图解决科拉茨猜想。如果你不能做到这一点，那么你可能也无法解决这台机器的停机问题，因此你无法确定BB6。太神奇了。我只是喜欢它被称为反九头蛇。是的，这是一个很棒的名字。好的。好的。

所以我们有了忙碌的海狸5，而且你在网站上写了一篇一年前解释整个传奇故事的精彩文章，所以每个人都应该查看一下。我相信如果忙碌的海狸6有任何进展，你都会写出来。我很乐意写出来。我很高兴阅读它们。所以感谢你今天加入我们，Ben。感谢你的邀请。Ben，我们喜欢在每一集的结尾都推荐一些东西，所以本周有什么东西让你兴奋不已吗？

我已经设法在主要的播客中偷偷推荐了一个谜题。我将再给你推荐一个谜题。这是一个电脑游戏。它叫做《巴巴是你》。你控制着这只小小的像素绵羊。你正在四处走动。你试图解决谜题，并找到旗帜。

诀窍是，游戏的规则就像这个世界上你可以操纵的对象。所以你可以改变这些规则，也许可以使它不再是触摸旗帜就能获胜，而是必须触摸墙壁才能获胜等等。一个电脑益智游戏，你可以在游戏中改变规则。没错。听起来很棒。我会去看看的。

忙碌的海狸挑战赛，一个2022年启动的开放式在线合作项目，旨在最终解决理论计算机科学中的一个重大问题。随着时间的推移，这个在线社区发展壮大，汇集了来自世界各地20多位贡献者，其中大多数人没有传统的学术背景。2024年7月，该小组宣布他们最终解决了这个难题，为持续40多年的努力画上了句号。在本周的《量子播客》节目中，计算机科学撰稿人本·布鲁贝克解释了令人着迷的忙碌的海狸难题，他去年在“第五个忙碌的海狸，研究人员接近计算的极限”一文中对此进行了深入报道。每周在《量子播客》节目中，《量子杂志》主编萨米尔·帕特尔都会与获得该杂志奖项的幕后人员交谈，探讨科学和数学领域一些最重要和最令人兴奋的问题。</context> <raw_text>0 本周在Quanta上，你还可以阅读关于一种特殊的四面体，它总是翻转到同一面，你也可以看到它的实际操作。你还可以查看一篇关于新理论的文章，该理论与人工智能如何进行创造性活动有关，或者至少与不在其原始训练数据中的活动有关。

今天我们将用Lucy Moonlight的音乐来结束节目。Lucy是一位Busy Beaver挑战赛贡献者的朋友，这位贡献者的用户名是Rachelin，目前正在研究Busy Beaver 6。Rachelin将一些图灵机的数 据进行了声化处理，然后Lucy用这些数据创作了这首名为《城市正在倒塌》的作品。它采用了复古的真实方法，一切都非常简单。

《量子播客》是由《量子杂志》制作的播客，《量子杂志》是一家由西蒙斯基金会支持的编辑独立出版物。我是《量子杂志》的主编萨米尔·帕特尔。

西蒙斯基金会的资金决定不会影响本播客或《量子杂志》中主题、嘉宾或其他编辑决定的选择。《量子播客》是与PRX Productions合作制作的。制作团队包括Ali Budner、Deborah J. Balthazar、Genevieve Sponsler和Tommy Bazarian。PRX Productions的执行制片人是Jocelyn Gonzalez。

来自《量子杂志》的Simon France和我本人在Matt Karlstrom、Samuel Velasco、Simone Barr和Michael Kenyongolo的支持下提供编辑指导。我们的主题音乐来自APM Music。如果您对我们有任何疑问或意见，请发送电子邮件至[email protected]。感谢收听。来自PR。 </raw_text>