最慢的计算机程序如何阐明数学的基本极限

程序员通常希望最大程度地减少执行代码所需的时间。但是在1962年，匈牙利数学家TiborRadó提出了相反的问题。他问：一个简单的计算机程序在终止之前可能会运行多长时间？ Radó将这些效率极低但仍能正常运行的程序称为“繁忙的海狸”。

自从1984年在《科学美国人》的“计算机娱乐”专栏中进行推广以来，对于程序员和其他数学爱好者来说，找到这些程序一直是一个巨大的难题。但是在最近几年，忙碌的海狸游戏已成为一种流行的游戏。研究对象本身具有优势，因为它已经与某些最崇高的概念和数学中的开放性问题产生了联系。

德克萨斯大学奥斯汀分校的理论计算机科学家Scott Aaronson说：“在数学上，有趣的娱乐活动与实际上重要的活动之间存在非常容易渗透的界限。”他最近发表了一项关于“ BusyBeaverology”的研究进展的调查。

最近的工作表明，对运行时间长的计算机程序的搜索可以阐明数学知识的状态，甚至可以告诉我们什么是已知的。根据研究人员的说法，繁忙的海狸游戏为评估某些问题（例如未解决的哥德巴赫猜想和黎曼假设）的难度提供了具体的基准。它甚至可以让您一目了然地了解数学背后的逻辑基础。逻辑学家库尔特·哥德尔（KurtGödel）在近一个世纪前就证明了这种数学界的存在。但是繁忙的海狸游戏可以显示它实际上在数字线上的位置，就像描绘世界边缘的古代地图一样。

忙碌的海狸游戏全都涉及图灵机的行为-图灵机是1936年由艾伦·图灵（Alan Turing）构想的原始，理想化的计算机。图灵机在无穷无尽的胶带上执行动作，这些胶带分成正方形。它根据规则列表进行操作。第一条规则可能会说：

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

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

正如图灵在1936年指出的那样，为了进行计算，图灵机必须最终停止​​运行-它不能陷入无限循环中。但是他还证明，没有可靠的，可重复的方法来区分停止运行的机器和永久运行的机器-这就是停机问题。

忙碌的海狸游戏会问：给定一定数量的规则，图灵机停止之前可以执行的最大步数是多少？

例如，如果只允许一个规则，并且要确保图灵机停止，则必须立即添加停止指令。因此，一台规则机器的繁忙海狸数或BB（1）为1。

但是，仅添加一些规则就会立即炸毁要考虑的计算机数量。在具有两种规则的6,561台可能的机器中，繁忙的海狸在停机前运行时间最长（六步）。但是其他一些只是永远运行。这些都不是繁忙的海狸，但是您如何确定排除它们呢？图灵证明，无法自动判断运行一千或一百万步的计算机是否最终不会终止。

这就是为什么很难找到繁忙的海狸的原因。目前尚无通用的方法来确定运行时间最长的图灵机，并带有任意数量的指令；您必须自己弄清楚每个案例的细节。换句话说，繁忙的海狸游戏通常是“无法计算的”。

证明BB（2）= 6且BB（3）= 107十分困难，以至Radó的学生Shen Lin于1965年获得了博士学位。Radó认为BB（4）“完全没有希望”，但此案终于解决了到了1983年。研究人员已经确定了一个五规则的图灵机，该机器在停止前要运行47,176,870步，因此BB（5）至少那么大。 BB（6）至少为7.4×10 36,534。 Aaronson说，证明确切的价值“如果可以做到的话，将需要新的想法和新的见解。”

马里兰大学学院分校的计算机科学家William Gasarch表示，他对固定繁忙的海狸数量的前景不感兴趣，而对“实际上却无话可说的一般概念”感兴趣。他和其他数学家主要对将游戏用作衡量标准来衡量数学中重要的未解决问题的难度，或者找出所有数学上可以理解的东西感兴趣。

例如，哥德巴赫猜想问，每个大于2的偶数整数是否是两个质数之和。在数论中证明猜想是真还是假是一个时代性的事件，这使数学家可以更好地理解素数的分布。 2015年，一个名叫Code Golf Addict的匿名GitHub用户为一台27规则的图灵机发布了代码，该图灵机在（且仅在）哥德巴赫猜想为假的情况下才停止。它通过向上计数所有大于4的偶数来工作。对于每一个，它都会尝试通过所有其他可能的方式，通过将另外两个加起来来检查该对是否为质数，从而获得该整数。当找到合适的素数对时，它将向上移动到下一个偶数整数并重复该过程。如果发现偶数不能用一对质数相加的整数，它将暂停。

运行这种无意识的机器并不是解决该猜想的实用方法，因为我们无法知道它是否会一直停下来。但是繁忙的海狸游戏揭示了这个问题。如果有可能计算BB（27），那么将为我们必须等待多长时间自动解决哥德巴赫猜想提供一个上限。这是因为BB（27）对应于此27条规则的图灵机必须暂停执行的最大步数（如果有的话）。如果我们知道这个数字，那么我们可以将图灵机运行那么多步骤。如果到那时止步不前，我们就会知道哥德巴赫猜想是错误的。但是，如果它走了许多步骤并且没有停止，我们肯定会知道它永远不会-因此证明了这一猜想是正确的。

令人难以理解的是，BB（27）的数量如此之多，以至于即使将其写下来，更不用说在许多步骤中运行哥德巴赫伪造机了，这在我们的物理宇宙中也是遥不可及的。然而，这个难以理解的巨大数字仍然是一个精确的数字，根据亚伦森的说法，它的数量代表着“关于我们当前理论知识的陈述”。

2016年，Aaronson与Yuri Matiyasevich和Stefan O’Rear合作建立了类似的结果。他们确定了一个只有744条规则的图灵机，当且仅当黎曼假设为假时，该机器才停止。黎曼假说也涉及素数的分布，是克莱数学研究所的“千年问题”之一，价值100万美元。亚伦森的机器将以BB（744）步提供自动解决方案。 （它的工作原理基本上与哥德巴赫机器相同，无需担心，向上迭代直到找到反例。）

当然，BB（744）的数量甚至比BB（27）大得多。但是努力确定诸如BB（5）之类的更简单的东西，“实际上可能会提出一些本身就很有趣的新的数论问题，” Aaronson说。例如，数学家帕斯卡尔·米歇尔（Pascal Michel）在1993年证明了保持记录的五规则图灵机的行为类似于Collat​​z猜想中描述的函数的行为，这是数论中另一个著名的开放问题。

“很多数学可以编码为一个问题，‘这个图灵机是否停止？’” Aaronson说。 “如果您知道所有繁忙的海狸数量，那么您可以解决所有这些问题。”

最近，Aaronson使用了一个忙于海狸的准绳来衡量整个数学系统中他所谓的“不可知阈”。哥德尔（Gödel）于1931年著名的不完全性定理证明，任何可以作为数学逻辑基础的基本公理都注定是以下两种命运之一：两种公理都将不一致，从而导致矛盾（例如证明0 = 1），否则它们将是不完整的，无法证明一些关于数字的真实陈述（例如2 + 2 = 4的事实）。建立于几乎所有现代数学基础之上的公理系统，即Zermelo-Fraenkel（ZF）集合论，具有自己的哥德尔式边界-Aaronson希望利用繁忙的海狸游戏来确定它们的位置。

2016年，他和他的研究生亚当·耶迪迪亚（Adam Yedidia）指定了一个7,910规则的图灵机，该方法仅在ZF设置理论不一致时才会停止。这意味着BB（7,910）是一个计算，它忽略了ZF集理论的公理。这些公理不能用来证明BB（7,910）代表一个数字而不是另一个数字，这就像无法证明2 + 2 = 4而不是5一样。

O'Rear随后设计了一种简单得多的748规则的机器，如果ZF不一致，则将停止运行-实质上将不可知性的阈值从BB（7,910）移至BB（748）。俄亥俄州立大学的数学逻辑学家和名誉教授哈维·弗里德曼说：“这是一种戏剧性的事情，（规则）的数量并不完全荒谬。”弗里德曼认为这个数字可以进一步降低：“我认为也许50是正确的答案。” Aaronson怀疑真实阈值可能与BB（20）接近。

无论是接近还是遥远，这种不可知的阈值确实存在。 “这是自哥德尔以来我们对世界的愿景，”亚伦森说。 “繁忙的海狸功能是使其具体化的另一种方式。”