下载客户端

为什么“忙碌海狸”猎人害怕“反九头蛇”——忙碌海狸游戏与科拉茨猜想的联系

2025-10-30 12:15

来源：澎湃新闻·澎湃号·湃客

最近《量子杂志》计算机科学专栏作家Ben Brubaker撰文探讨了忙碌海狸游戏与数学中一个著名的开放性问题——科拉茨猜想（Collatz猜想，即3n+1猜想）之间的联系。

一只勇敢忙碌的海狸，正与可怕的反九头蛇正面交锋。插画由才华横溢的Nico Roper绘制。

作者：Ben Brubaker（量子杂志计算机科学专栏作家）2025-10-22

译者：zzllrr小乐（数学科普公众号）2025-10-28

2024年夏天，我报道了一个在线社区 https://bbchallenge.org ，该社区确定了一个名为 BB(5) 的数字的精确值 https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ ——这是50年来在理论计算机科学领域一个古老问题（被称为“忙碌海狸游戏”）上取得的首个重大突破。BB(5)，现在已知为 47176870，是所谓的“忙碌海狸数”中的第五个，该数衡量的是简单计算机程序能够完成的最复杂计算的复杂度。（该团队最近发表了一篇论文，详细描述了他们的研究结果 http://arxiv.org/abs/2509.12337 。）

这项独特的研究工作的下一步是确定第六个忙碌海狸数 BB(6)，目前已经取得了一些显著进展——几个月前我写了一篇后续文章 https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/ 。但忙碌海狸研究人员并不指望能很快确定 BB(6) 的真正值。这是因为要做到这一点，他们需要理解一个名为“Antihydra”（反九头蛇）的程序的行为，这个程序类似于数学中一个长期悬而未决的问题——科拉茨（Collatz）猜想（即3n+1猜想）。（请不要将反九头蛇与假九头蛇 https://goblinpunch.blogspot.com/2014/09/false-hydra.html 混淆，后者是 D&D 博主 Arnold Kemp 构思的一种非常酷且非常可怕的怪物。）

一位分享了我第一个忙碌海狸故事的 Twitter 用户更简洁地总结了这种情况：

需要注意的是：“编码 Collatz 猜想”并不完全正确，我们稍后会看到。

我的两篇故事都只是非常简短地提到了“反九头蛇”屏障。在这篇博文中，我将更详细地探讨它：反九头蛇究竟是什么？什么是“科拉茨猜想”？它们之间有何关联？以及它们为何如此令人望而生畏？

忙碌海狸的基础知识

如果你还没读过我写的两篇《量子杂志》上关于“忙碌海狸”游戏的故事，建议你先读读，因为这两篇故事都很有趣！接下来我会回顾一下“忙碌海狸”游戏的玩法，以便大家能够理解。

我上面写道，忙碌海狸数“衡量的是简单计算机程序所能完成的最疯狂计算的复杂性”。为了更准确地定义它们，我们首先需要一个数学框架来衡量计算机程序本身的复杂性，以确定哪些程序是“简单的”。然后，我们需要一种方法来量化计算的复杂性——计算机程序所做的事情——这样我们才能识别出最疯狂的程序。

在“忙碌海狸”游戏中，计算机程序由一种名为图灵机的假想设备来表示，这些设备通过在被划分为多个单元的无限磁带上读写 0 和 1，以离散的步骤进行计算。每台图灵机的行为都受一套独特的规则控制。任何你能用普通计算机程序完成的事情，原则上都能用一套合适的图灵机规则来完成。（在忙碌海狸文献中，这些规则被称为“状态”。） “原则上”在这句话中承担了大量工作——即使你设法获得了必要的无限磁带，用图灵机进行计算也会极其低效。但从理论上讲，图灵机比更实用的编程语言更容易分析。

让我们更详细地解析一下图灵机的工作原理。在每一步中，图灵机都会参考其中一条规则并编辑磁带上的一个单元格。每条规则有两种情况：如果当前单元格包含 0 该怎么办？如果当前单元格包含 1 该怎么办？“该怎么办”在这里指的是在当前单元格中写入什么、下一步要朝哪个方向移动以及下一步要参考哪条规则。其中一条规则的一种情况打破了这种模式：它告诉图灵机“停止”，即停止运行。但这条指令本身的存在并不能保证图灵机会停止——机器可能永远不会停止。

量子杂志的视觉设计师 Kristina Armitage 将所有这些内容封装在一张精美的信息图中。（在我的第一篇忙碌海狸故事中，你还会看到图灵机运行的动画。 https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ ）

图源： Kristina Armitage / Quanta Magazine 的“忙碌的海狸猎人得出的数字超越了普通数学”

图灵机所拥有的规则数量将作为我们衡量程序复杂度的标准。这种选择让我们能够将关于简单计算机程序能够完成的最复杂任务的模糊问题，替换为一系列关于不同复杂程度的具体问题，这些问题对应不同的忙碌海狸数。你可以通过回答“单规则图灵机能够完成的最复杂计算是什么？”这个问题来了解 BB(1)的值。同样，BB(2)衡量双规则图灵机能够完成的最复杂计算，依此类推。

要回答这些问题，我们需要一个精确的定义，来解释是什么使得一个计算比另一个计算更复杂。一个自然的衡量标准是图灵机完成计算需要多少步。“完成”很重要——每台永不停止的图灵机都会运行无限多步，但这实际上不是一个公平的比较。图灵机在停止之前（以及它是否停止）所执行的步数可能取决于磁带上 0 和 1 的初始模式。对于忙碌海狸游戏，我们总是从所谓的“空白磁带”开始，磁带的每个单元都是 0。

现在，我们已经掌握了正式定义忙碌海狸数的所有必要信息。我们以 BB(6) 为例：它是所有六规则图灵机中，从空白磁带启动时最长的有限运行时间。原则上，找到这个数字很简单。首先，列出所有可能的六规则图灵机。接下来，将它们分为两类：一类是最终会在空白磁带上运行时停止的机器，另一类是永远运行的机器。剔除所有不停机的机器。最后，测量每台停机机器在停止前需要执行多少步。最大的数字是 BB(6)。

该计划的问题在于第二步，即根据图灵机是否停止，将其分成两组。事实证明，判断一台图灵机是否会停止，这可以说是一个极其困难的问题。如果你无法判断一台给定的机器是否会停止，那么你就无法确定你的停止图灵机列表是否完整，也就无法确定是否找到了运行时间最长的机器！截至本文撰写时，研究人员已将绝大多数六规则机器分为停止型或非停止型。但仍有 1618 台“未停止”机器的命运未知。

反九头蛇（Antihydra）就是这些“顽固分子”之一。为了确定 BB(6)的值，研究人员必须首先确定反九头蛇是否会停止运行，而这似乎超出了任何已知数学方法的范畴。为了理解其中的原因，我们需要退一步思考：“这些图灵机到底在做什么？”

进阶

你可能会反对这一点，认为我们已经确切地知道这些图灵机在做什么：每台图灵机只是遵循特定的规则序列，在磁带上边走边写 0 和 1。但这种“低级”描述有点像说“当我按下这些按钮时，我的袖珍计算器会按照特定的模式打开和关闭晶体管”。这很可能是真的，但像“当我按下这些按钮时，我的袖珍计算器会将 3 和 4 相乘”这样的“高级”描述通常更有用。

无法保证任何给定的图灵机的行为都能接受这种简单的高级描述。（此外，在很多情况下，低级描述就足够了。例如，证明图灵机停止运行最简单的方法就是逐步模拟它，直到它停止运行。当这种情况发生时，你不需要深入了解它停止的原因：只需记录它的运行时间，然后继续下一步即可。）但请记住，图灵机可以执行所有可能的计算 - 这意味着至少有一些图灵机必须执行具有人类可以理解的高级描述的程序。

实际上，迄今为止，忙碌海狸的研究人员研究过的最著名的五规则和六规则图灵机都具有相对简单的高级描述 - 其中包括最终停止的运行时间最长的五规则和六规则机器、最复杂的非停止五规则机器，以及像 Antihydra（反九头蛇）这样的顽固分子。（这是一个经验观察，而非不证自明的真理。事实上，一些研究人员曾预计，运行时间最长的图灵机将是缺乏任何高级描述的“意大利面条式代码”机器！ https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html ）

让我们看一个具体的例子。第五个忙碌海狸在停止前运行了 47176870 步，遵循以下低级规则：

图源：忙碌海狸大挑战。“—”表示“停止”。 https://bbchallenge.org/story

1993年，数学家帕斯卡·米歇尔（Pascal Michel）证明这些规则等同于一个简单的高级程序 http://link.springer.com/10.1007/BF01409968 ：

设 x=0 。

将 x 除以 3 并检查余数。

如果余数为 0，则计算 (5x+18)/3 。结果就是新的x值。

如果余数为 1，则计算 (5x+22)/3 。结果就是新的x值。

如果余数为 2，则停止。

如果尚未停止，请返回步骤 2 并插入新的x值。

一旦你有了这样的高级描述，你就可以使用它来确定机器是否会停止 - 如果会，那么它到底需要多少步。（像这样的高级程序中的每一步都对应着许多独立的图灵机步骤。每当你证明高级描述和低级描述之间的等价性时，你都会得到一些公式，可以用来计算每个高级步骤需要多长时间。我不会谈论如何实际证明这些等价性。）在这种情况下，高级程序只是重复插入新的 x 值，直到找到一个除以 3 余 2 的值。三分之一的数字具有该性质，因此你可能会猜测程序将需要或多或少三次尝试才能找到一个。如果从随机值 x 开始，你会发现三次迭代确实是典型的。但事实证明，如果从 x=0 开始，该程序将重复第二步 15 次，才能找到余数为 2 的数字！忙碌海狸研究人员经常喜欢将他们研究的图灵机拟人化，想象这些机器正在积极地尝试尽可能长时间地运行。采用这种观点，我们可以说这台图灵机非常幸运。

第五只忙碌的海狸只是“Collatz 类”图灵机家族的一员，其高级行为具有以下一般形式：

将 x 设置为某个起始值（可能是 0 也可能不是）。

用 x 除以一个固定数 N 。余数告诉你该用什么公式来得到新的值 x 。

检查是否满足特定的停止条件。

如果没有，则返回步骤 2，并使用新值 x 。

（正如我们在上面的例子中看到的，停止条件可以简单到“余数具有特定值”。下面我们将看到一些具有不同停止条件的例子。）

类 Collatz 图灵机家族包括停机机和非停机机。它的名字来源于数学家 Lothar Collatz（洛塔尔·科拉茨，1910 - 1990）于1937年设计的一种生成数字序列的程序：

为 x 选择一个起始值。

检查 x 是偶数还是奇数。

如果是偶数，则计算 x/2 。结果就是新的 x 值。

如果是奇数，则计算 3x+1 。结果就是新的 x 值。

检查是否满足 x=1 。如果不是，则返回步骤 2。

这看起来与我们对 Collatz 类机器高级行为的一般描述非常相似，以 x=1 作为停止条件。（“检查 x 是偶数还是奇数”其实就是“用 x 除以 2 并检查余数”的另一种说法。严格来说，我们不必指定序列在 x=1 时停止。但如果在 x=1 之后继续应用规则，序列就会进入无限循环：1 > 4 > 2 > 1，依此类推。）

尝试从任意初始整数值 x 迭代这些规则 https://collatz-graph.vercel.app ——我愿意打赌，无论你选多少数字，你最终都会得到 1。Collatz猜想 https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/ 断言，对于每个正整数，无论多大，都会发生这种情况。人们已经对所有至少 20亿万亿（！）以内的整数进行了实证检验，没有发现任何反例，这有力地暗示该猜想是正确的。但没有人知道如何严格证明它。

神秘动物学

让我们退一步来看。在这篇文章的开头，我指出了科拉茨猜想和“反九头蛇”之间的联系：没有人知道如何证明科拉茨猜想，这就是为什么研究人员不知道如何最终确定“反九头蛇”是否会停止运行。但现在，我把科拉茨猜想与第五个“忙碌海狸”联系起来，后者是一台已被证明会停止运行的机器。这到底是怎么回事？

这个看似难题的解决方案是：对于忙碌海狸游戏，我们只关心图灵机从特定磁带配置（即空白磁带）开始运行时是否会停止。这意味着我们只关心相应的类 Collatz 序列是否会因单个输入而停止。而 Collatz猜想则询问是否最终对每个输入都命中 x=1 。很容易证明 Collatz 序列最终对任何一个输入都命中 x=1 ，就像很容易证明第五个忙碌海狸会停止一样（一旦你建立了其低级规则和高级类 Collatz 程序之间的等价关系）。事实上，忙碌海狸猎人海纳·马克森 (Heiner Marxen) 和尤尔根·邦特罗克 (Jürgen Buntrock) 率先通过直接模拟证明了第五只忙碌海狸会停止行动（尽管他们使用了一些技巧来加快速度）。米歇尔只是在事后才识别出它的高级行为。

我们可以轻松构建 Collatz 问题的变体，即使对于单个输入，它也很难解决。我们需要做的就是将奇数的 3x+1 规则更改为 5x+1 。在这种情况下，从某些输入（例如 x=7 ）开始的轨迹看起来会发散，永远不会达到 1，也不会陷入循环。但研究人员还无法证明这些轨迹中的任何一个会发散。这里面存在着内在的不对称性。如果你想证明一个序列最终会在某个地方结束，你总是可以使用蛮力，至少在原则上是这样。但如果你想证明一个序列永不终止，即使是单个输入也可能很难。

现在，我们终于准备好对抗恐怖的“反九头蛇”（Antihydra https://wiki.bbchallenge.org/wiki/Antihydra ）了。它遵循以下高级规则：

设置 x=8 。

（这看起来似乎有点奇怪，因为在“忙碌海狸”游戏中，我们应该从空白磁带开始。但在这里仍然如此——只是 Antihydra（反九头蛇）在开始迭代这个序列之前，花了一段时间在磁带上进行操作，而所有这些操作的最终效果是将起始值设置为 8。）

检查 x 是偶数还是奇数。

如果是偶数，计算 3x/2 。结果就是新的 x 值。将你应用此偶数规则的次数加一。

如果是奇数，计算 (3x−1)/2 。结果就是新的 x 值。将你应用此奇数规则的次数加一。

检查“奇数”计数是否是“偶数”计数的两倍以上。

如果是，则停止。

如果不是，则返回步骤 2。

这是一组非常奇特的规则。公式 3x/2 和 (3x−1)/2 似乎并没有系统地偏向奇数或偶数，所以你可能会认为，反复迭代它们就像反复抛硬币并记录正面和反面出现的次数一样。在抛硬币的初期，正面出现的次数很可能是反面出现的次数的两倍以上。但如果这种情况没有立即发生，那么随着抛硬币时间的延长，这种可能性就会越来越小。

研究人员现在已经模拟了 Antihydra 的行为超过 2700 亿步，正如预期的那样，“偶数”和“奇数”的计数非常接近相等——远没有达到停机条件所要求的极端不平衡程度。因此，Antihydra 永不停机的可能性似乎非常大。但没有人知道如何证明这一点！数学家约翰·康威 (John Conway，1937 - 2020) 为这种情况创造了一个令人愉快的术语“probviously”（（probabilistic + obvious + ly）——在这种情况下，感兴趣的具体问题很难解决，但对类似问题的“典型”行为进行概率推理使得答案变得显而易见。

反九头蛇的行为在性质上与 Collatz 猜想的 5x+1 版本相似，我们尚不清楚如何证明任何单一轨迹都会发散。我想强调的是，就研究人员所知，这两个问题之间并没有更精确的数学联系：解决了其中一个问题，并不会自动解决另一个问题。但这两个问题看似困难，原因却非常相似。如果有人真的成功证明 Collatz 猜想，那么证明中使用的数学技巧很可能对解决反九头蛇问题大有裨益（反之亦然）。

实际上，Antihydra 只是众多具有类似 Collatz 行为的、可能不停机的图灵机之一。当这些机器首次在标准“忙碌海狸”游戏的变体中被发现时，忙碌海狸猎人 Shawn Ligocki 将这些机器称为“神秘生物”（cryptids https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html ）。这些变体除了 0 和 1 之外还使用额外的磁带符号。例如，忙碌海狸游戏的 BB(3,3) https://wiki.bbchallenge.org/wiki/BB(3,3) 版本研究了具有三个规则的图灵机的行为，这些规则可以读写三个符号：0、1 和 2。

一只神秘生物，被弗恩 (Fern) 的朋友、忙碌海狸大挑战discord 服务器成员劳伦 (Lauren) 描绘成洛夫克拉夫特式（Lovecraftian）的海狸。

最早被发现的两种神秘生物分别名为“大脚怪”（https://wiki.bbchallenge.org/wiki/Bigfoot )和“九头蛇”（https://wiki.bbchallenge.org/wiki/Hydra “反九头蛇”因与“九头蛇”在数学上的联系而得名）；研究人员如今已发现如此之多的神秘生物，以至于不再有必要为每一种生物单独命名。所有这些神秘生物的存在意味着，在研究人员开发出新的数学工具来解决类似 Collatz 问题之前，BB(5) 以上的忙碌海狸数仍将遥不可及。据说，传奇数学家保罗·埃尔德什（Paul Erdős，1913 - 1996）曾说过：“数学可能还没有准备好应对此类问题。”

但这并不意味着忙碌海狸猎人应该放弃。在所谓的“神秘动物生态学”领域，仍有许多问题有待探索。神秘动物有多少个亚种？它们之间以及与科拉茨猜想之外的其他数学未解问题之间有何关联？ https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ 自忙碌海狸狩猎开始以来，狂热的猎人就不断遇到令人惊讶的图灵机新行为，而且这种模式丝毫没有减弱的迹象。

今年八月，我去了密歇根州上半岛的塔夸梅农瀑布，这里似乎是大脚怪目击事件的热点地区。幸运的是，我没有遇到任何神秘生物，但我确实对一些比较友好的小动物有了些了解。惊喜的发现可能无处不在！