• 目前已知运行时间最长的五规则图灵机的可视化。每一列像素代表计算中的一步，从左向右移动。黑色方块表示机器打印了1的位置。最右边的一列显示了当图灵机停止时的计算状态。

程序员通常希望最小化代码的执行时间。但在1962年，匈牙利数学家提博尔·拉多提出了相反的问题。他问，一个简单的计算机程序在终止之前最多能运行多少步骤？拉多将这些效率最高但仍能正常工作的程序称为“忙碌的海狸”。

自从1984年在《科学美国人》的“计算机娱乐”专栏中流行以来，对于程序员和其他数学爱好者来说，寻找这些程序一直是一个极其有趣的谜题。但在过去的几年里，忙碌的海狸游戏已经成为一个研究的对象，因为它与数学中一些最崇高的概念和开放问题产生了联系。

最近的工作表明，搜索长时间运行的计算机程序可以阐明数学知识的状态，甚至告诉我们什么是可知的。根据研究人员的说法，“忙碌的海狸”游戏为评估某些问题的难度提供了一个具体的基准，例如尚未解决的哥德巴赫猜想和黎曼假设。它甚至让我们看到，数学背后的逻辑基石在哪里崩溃了。近一个世纪前，逻辑学家库尔特·哥德尔就证明了这种数学未知领域的存在。但忙碌的海狸游戏可以显示它实际上在数轴上的位置，就像一幅描绘世界边缘的古老地图。

无法计算的电脑游戏

“忙碌的海狸”是关于图灵机的行为的，它是由艾伦·图灵在1936年构想出来的原始的、理想化的计算机。图灵机在被分割成无数个正方形的带上执行操作。它是根据一系列规则来运行的。第一条规则是：

如果正方形包含0，则将其替换为1，向右移动一个正方形并参照规则2。如果正方形包含1，离开1，向左移动一个正方形并参考规则3。

每个规则都有这种分叉的“选择自己的冒险”风格。有些规则说要回到以前的规则，最终会有一条包含“停止”指令的规则。图灵证明，只要有正确的指令和足够的时间，这种简单的计算机就能进行任何可能的计算。

正如图灵在1936年指出的，为了计算一些东西，图灵机最终必须停止——它不能陷入无限循环。但他也证明了，没有可靠的、可重复的方法来区分机器停机和机器简单地无限循环运行，这个事实被称为停机问题。

“忙碌的海狸”游戏的问题是：给定一定数量的规则，在图灵机停止运行之前，它能执行的最大步骤是多少？

• 在这张未注明日期的照片中，提博尔·拉多发明了忙碌的海狸游戏，将理论上的不可计算性具体化。

例如，如果只允许一条规则，并且想要确保图灵机停止，那么这条规则里必须包含停止指令。单规则机器的忙碌的海狸数为1，即BB(1) =1。

但只要再增加几条规则，需要考虑的机器数量马上就会激增。有两个规则的6561个可能的机器中，在停止运行之前的最大步骤是6步，也有些干脆无限循环了。这些都不是忙碌的海狸，但你如何确定地排除它们呢？图灵证明了，没有办法自动判断运行1000步或100万步的机器最终会不会终止。

这就是为什么发现忙碌的海狸如此困难的原因。没有通用的方法来识别使用任意数量的指令运行时间最长的图灵机，你必须自己弄清楚每一种情况的具体情况。换句话说，“忙碌的海狸”游戏一般来说是“不可计算的”。

证明BB(2) = 6和BB(3) = 107是非常困难的，因此拉多的学生沈林在1965年获得了该研究的博士学位。拉多认为BB(4)完全没有希望了，但这最终在1983年解决了。除此之外，这些值实际上会暴增。研究人员已经确定了一个具有5条规则图灵机，例如，5规则图灵机运行47,176,870步才停止，所以BB(5)至少有这么大。BB(6)至少为7.4×10^36,534。要证明确切的值，需要新的想法和新的见解。

阈值

马里兰大学帕克分校的计算机科学家威廉·加斯克说，他对“忙碌海狸的数量实际上无法计算这一普遍概念”更感兴趣，而不是对确定忙碌海狸的数量的前景感兴趣。他和其他数学家主要感兴趣的是，将博弈作为衡量重要数学开放问题难度的标尺，或者用来弄清什么在数学上是可知的。

例如，哥德巴赫猜想询问是否每个大于2的偶数都是两个素数的和。在数论中，证明猜想的真假将是一个划时代的事件，使数学家们能够更好地理解质数的分布。2015年，一个名匿名用户发布了一个27条规则的图灵机代码，当且仅当哥德巴赫猜想是假的时候，该代码才会停止运行。它的工作原理是向上计算所有大于4的偶数，对于每一个整数，它都会通过将另外两个相加的所有可能方法来得到这个整数，并检查这两个整数对是否为素数。当它找到合适的质数对时，它移到下一个偶数并重复这个过程。如果它发现一个不能用质数对求和的偶数，它就会停止。

运行这个无需动脑筋的机器并不是解决猜想的实际方法，因为在它停止之前，我们无法知道它是否会停止。但忙碌的海狸游戏为这个问题提供了一些线索。如果计算BB(27)是可能的，这将为我们等待哥德巴赫猜想自动解决的时间提供一个上限。这是因为BB(27)对应的是这个27条规则的图灵机为了停止而必须执行的最大步骤数。如果我们知道这个数字，我们就可以运行图灵机这么多步骤。如果它停在那一点，我们就知道哥德巴赫猜想是假的。但如果它永远不会停下来，那么就证明了猜想的正确性。

问题是BB(27)是一个难以理解的巨大数字，更不用说去运行那么多步骤，在我们的物理宇宙中也根本不可能。然而，这个不可理解的巨大数字仍然是一个精确的数字。

2016年，三位数学家发现了一台744条规则图灵机，当且仅当黎曼假设为假时，它才会停止工作。黎曼假设也涉及质数的分布，是克莱数学研究所价值100万美元的“千年难题”之一。

当然，BB(744)是一个比BB(27)更大的数字。但是，努力确定一些更简单的东西，比如BB(5)，实际上可能会出现一些新的数字理论问题，这些问题本身就很有趣。例如，数学家帕斯卡•米歇尔在1993年证明，保持纪录的5规则图灵机表现出类似于科拉茨猜想中描述的函数的行为。科拉茨猜想是数论中另一个著名的开放问题。

1931年哥德尔著名的不完全性定理证明，任何一组基本公理，只要能作为数学的逻辑基础，都注定会有两种命运，【即要么公理将不一致，导致矛盾（比如证明0 = 1），或者他们会不完整，无法证明一些真实陈述数据（如2 + 2 = 4）】，支撑几乎所有的现代数学的公理系统。被称为ZF集合理论，有它自己的哥德尔边界。

2016年，研究生亚当·耶迪迪亚和他的导师设计了一个7910条规则的图灵机，只有在ZF集合理论不一致的情况下，图灵机才会停止。这意味着BB(7910)是一个避开了ZF集合理论公理的计算。这些公理不能用来证明BB(7910)代表的是一个数而不是另一个数，就像不能证明2 + 2 = 4而不是5一样。

随后，瑞娅尔设计了一个更简单的748规则机器，如果ZF不一致，它就会停止——实质上是将不可知阈值从BB(7,910)移近到BB(748)。俄亥俄州立大学的数学逻辑学家、名誉教授哈维•弗里德曼表示：“数量并非完全荒谬，这是一件引人注目的事情。”弗里德曼认为，这个数字还可以进一步降低。无论远近，这种不可知的阈值确实存在。