大多数人听到“忙碌海狸”时可能不会想到数学。但这些勤奋的小动物象征着这个错综复杂的领域中最令人惊叹的概念之一：并非所有事物都可以计算，无论你多么努力（或者你有多么勤奋）。忙碌海狸函数是不可计算的数学表达式的第一个例子。该函数本身很容易解释：它指的是计算机程序在停止之前可以执行的最大步数，如果该程序有 n 个状态，其中状态指的是问题的复杂性。但它的值，称为 BB(n)，对于所有数量的 n 而言，将永远无法得知。数学家和理论计算机科学家长期以来一直在思考数学工具在哪个 n 值时会失效：可计算性的极限究竟在哪里？
40 多年来，许多专家认为 BB(5) 可能超出可计算性的这个极限，因此是无法达到的。但现在，一个名为“忙碌海狸挑战”的国际合作项目已经成功确定了 BB(5) 的值，并且其计算已通过计算机辅助证明助手进行了正式验证。根据这项新研究，BB(5) 的神奇数字是 47,176,870，这意味着一个具有五个状态的程序在停止之前最多可以执行 47,176,870 步——或者它将永远不会停止。上一次重大的“忙碌海狸”成果发生在 1983 年，当时已故计算机科学家艾伦·布雷迪证明 BB(4) 等于 107。
忙碌海狸深深扎根于数学基础之中。在 20 世纪，许多专家梦想找到一个基础，所有数学真理都可以在此基础上得到证明。但在 1931 年，逻辑学家库尔特·哥德尔，当时年仅 25 岁，就粉碎了他们的希望。他证明，在数学中不可避免地存在不可证明的陈述——既不能被证明也不能被证伪的陈述。最初，专家们希望这只是一个抽象的结果，没有重要的应用。但他们错了。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事能够拥有未来。
数学家现在知道许多不可证明的问题。最早的例子之一是停机问题，它涉及算法的执行。在 20 世纪 30 年代，艾伦·图灵发现，没有算法可以预测具有特定输入的计算机程序是会永远运行还是会在某个时候停止。当时，图灵正在研究这种计算机的理论模型，现在称为图灵机。这种理论机器由一条无限长的磁带组成，磁带上标记着 1 和 0，以及一个读取磁带、描述磁带并将其向右或向左移动的磁头。这种机器理论上可以执行任何类型的计算——就像计算机一样。
假设您想编写一个图灵机程序来乘两个数字。磁带上的 1 和 0 则对应于这两个数字。在计算之前，您为机器定义一定数量的状态或规则，例如 A、B、C 和 D，以及 HALT。这些状态决定了图灵机如何对每个输入做出反应。例如：如果五状态机器在状态 A 中读取磁带上的 1，它会将此 1 覆盖为 0，将磁带向左移动并切换到状态 C。因此，对于状态 A 到 D 中的每一个状态，都需要两条指令，具体取决于机器在磁带上找到的是 1 还是 0。在某些情况下（例如，状态 B 在读取 1 时），机器可以切换到 HALT 状态。在这种情况下，图灵机停止，计算完成。结果将是那时磁带上的数字。
正如图灵所证明的那样，没有图灵机可以确定对于图灵机的所有可能配置（即所有算法），它们是否会在某个时候停止。而这就是勤奋的海狸发挥作用的地方。
停机问题
在 1962 年开发的“忙碌海狸游戏”中，匈牙利数学家蒂博尔·拉多寻找特定大小的最勤奋的图灵机：具有 n 个状态的图灵机在某个时候停止时，可以执行的最大计算步数是多少？
要普遍回答这个问题，您必须解决停机问题。要找到最勤奋的海狸，您需要知道哪些图灵机会停止（因此在某个步骤停止运行），哪些不会停止。但图灵表明，知道这一点是不可能的，这意味着忙碌海狸函数 BB(n) 对于所有可能的状态数都无法计算。
尽管如此，拉多还是确定了 BB 函数的前三个值，尽管在某些情况下付出了巨大的努力。困难的部分原因在于，随着状态数 (n) 的增加，可能的图灵机（计算机算法）的数量迅速增加。对于两个输入值 0 或 1 中的每一个，图灵机在特定状态下执行三个不同的步骤
它将输入替换为输出（0 或 1）。此步骤有两种可能的运算。
它将磁带向右或向左移动。这也包含两种可能的运算。
它更改为 n 个状态之一或 HALT 状态。此步骤需要 n + 1 种可能的运算。
因此，对于每个输入值和 n 个状态中的每一个状态，都有 2 x 2 x (n + 1) 种可能的运算。组合两个输入将得到总共 (4n + 4)2n 种不同的可能步骤集，其中每个步骤集代表不同的算法或不同的图灵机。如果只允许一个状态，则已经有 64 种不同的图灵机。在这些机器中，只有那些在第一个计算步骤后切换到 HALT 状态的机器才会停止。因为除了 HALT 之外只有另一条规则，如果机器不停止，它将永远继续执行该规则。因此，没有一个停止的图灵机会超过一个计算步骤，这就是为什么 BB(1) = 1。
如果您允许两个状态，情况会变得稍微复杂一些。在这种情况下，已经有 (4 x 2 + 4) 的四次方，即 20,736 个图灵机需要检查。没有普遍有效的方法来调查哪些图灵机停止。正如拉多发现的那样，具有两个状态的最长运行程序（最勤奋的海狸）可以执行六个算术步骤，因此 BB(2) = 6。
拉多和他的时任博士生沈林也在 1965 年阐明了三个状态的情况：在 16,777,216 个图灵机中，那些在某个时候停止的机器最多可以执行 BB(3) = 21 个计算步骤。1963 年，拉多将计算 BB(4) 的尝试描述为毫无希望的。但20 年后，布雷迪成功确定了 BB(4)：具有四个状态（或四个规则）的图灵机的最高计算步数是 107。这仍然是四十年来可以精确确定的忙碌海狸函数的最后一个值。
“忙碌海狸”猎人
在布雷迪的结果发布后不久，数学界转向精确计算 BB(5)。专家们于 1984 年在德国城市多特蒙德组织了一场竞赛，他们试图找到该函数的第五个值。参与者正在寻找五状态图灵机，这些机器在停止之前执行尽可能多的计算步骤。竞赛的获胜者是计算机科学家乌韦·舒尔特，他找到了一个具有 134,467 个计算步骤的程序。五年后，计算机科学家海纳·马尔克森和于尔根·本特罗克找到了五状态机器中的一台，它直到达到 47,176,870 步才停止，从而提出了 BB(5) 的新最小值。然而，无法证明在五状态图灵机中没有潜伏着更勤奋的程序。
忙碌海狸猎人需要证明所有其他机器无限期运行或比第 47,176,870 步更早停止。而且存在大量五状态图灵机。要确定 BB(n)，必须清楚地表明某些图灵机永远不会停止。例如，您必须证明程序最终会进入一个重复自身的循环。更棘手的是证明图灵机在没有重复模式的情况下无限期地继续运行——就像无理数的小数位一样。
在过去的几十年里，寻找执行超过 47,176,870 个计算步骤的停止的五状态图灵机一直没有成功。因此，许多专家怀疑 BB(5) = 47,176,870。但如果没有确凿的证据，这仅仅是假设。
出于这个原因，当时的计算机科学博士生特里斯坦·斯特林于 2022 年发起了忙碌海狸挑战。该项目的目的是收集和检查所有与忙碌海狸相关的结果。例如，如果有人证明五状态程序可以无限期运行，他们可以在那里发布证明并由计算机辅助证明软件进行检查。这使得许多感兴趣的人可以协同工作并呈现有效的结果。该项目在本月完成，最终证明 BB(5) 确实是 47,176,870。
因为每个忙碌海狸都对应一个算法，您可能想知道 BB(5) 实际上在计算什么。该程序对应于一个递归函数，类似于考拉兹猜想中的函数，考拉兹猜想是数论中最大的未解决问题之一。BB(5) 计算输入 x 的值 (5x + 18) / 3，如果 x 可被 3 整除；如果 x 除以 3 余数为 1，则计算 (5x + 22) ⁄ 3；如果 x 除以 3 余数为 2，则程序停止。
而对忙碌海狸的搜索仍在继续。具有六个状态的图灵机的记录保持者已经执行了如此多的算术步骤，您需要一种新的算术运算才能以紧凑的方式记录该数字（10↑↑15，或 10 的 10 的 10 次方，总共 15 次）。此外，越来越多的证据表明 BB(6) 可能无法计算。最能说明问题的是，在2024 年，发现了一台六状态图灵机，它几乎对应于考拉兹问题。因此，如果要证明这台机器停止（或永远运行下去），就相当于解决了考拉兹问题。考拉兹猜想指出，如果您从一个正整数开始并遵循两个特定规则，您将最终进入一个特定的循环。数学家们几十年来一直试图解决这个问题，但没有成功。因此，人们担心考拉兹问题是数学中不可证明的陈述之一。
在这种情况下，计算 BB(6) 的尝试将不可避免地注定失败。计算机科学家斯科特·阿伦森也不太抱希望，正如他在一篇博客文章中所写：“如果以及当人工智能超级智能接管世界时，他们可以担心 BB(6) 的值。然后上帝可以担心 BB(7) 的值。” 也许数学家们真的已经达到了 BB(5) 的可计算极限。但谁知道呢：也许有人会再次设法让专家们感到惊讶。
本文最初发表于《Spektrum der Wissenschaft》，经许可转载。