“忙碌的河狸”这个问题的目的是为了找到运行时间最长的电脑程序。对它的研究与哥德巴赫料想、黎曼料想等一系列数学难题建立了惊人而又深刻的联系。本文来自微信民众号：全球科学（ID：huanqiukexue），撰文：John Pavlus，翻译：张和持，编辑：吴非，头图来自unsplash

程序员总想让代码跑的更快。可在1962年，匈牙利数学家蒂博尔·拉多（Tibor Radó）却提出了截然相反的问题：要怎么才气让一个简朴的电脑程序在终止之前跑的尽可能久？拉多将这样跑得尽可能低效但仍有用的程序称为“忙碌的河狸”。

自从《科学美国人》于1984年刊载这则问题之后，众多程序员和业余数学爱好者们份份最先寻找“忙碌的河狸”。不外最近几年，由于与一些高峻上的看法与数学未解的难题建立起联系，“忙碌的河狸”已经变成了异常严肃的数学问题，

得克萨斯大学的理论盘算机科学家斯科特·亚伦森克日揭晓了一篇关于“忙碌河狸学”的观察，他说：“在数学上，娱乐和真正主要的问题，其界线异常模糊。”

最近一项研究解释，这些得跑到猴年马月的程序，或许能澄清一些数学命题，甚至告诉我们哪些内容是可知的。据研究者们称，忙碌的河狸能辅助我们判断一个数学问题的难易水平，好比哥德巴赫料想和黎曼料想。它能让人一目了然地看到数理逻辑到那里就该走不下去了。逻辑学家库尔特·哥德尔（Kurt Gödel）在大半个世纪之前就证实了，有一些命题既不能证实也不能证伪，也就是所谓的“不能知”。不外现在，忙碌的河狸能为我们指出，这个“不能知”事实位于什么地方，就如统一张古老的舆图指引旅者走向天下的边缘。

无法盘算的问题

“忙碌的河狸”这个问题，归根结底是关于图灵机——这是阿兰·图灵（Alan Turing）于1936年提出的一种理想化模子，其中有一条被分为正方形小块的长度无限的纸带，用笔在上面写或者擦去记号，这些操作需要知足一套给定的规则，比方说：

规则1. 若是正方形中含有0，则擦掉改成1；然后向右一格，使用规则2；

规则2. 若是正方形中含有1，那就不改，然后向左一格使用规则3；

……

每一项规则都像冒险棋一样。有些规则甚至可以让你跳回到之前的规则。在这些规则中，最终有一条“停机”的指令。图灵证实，若是时间足够，规则适合的话，图灵机就能做任何盘算。

五条规则的图灵机可视化。每列像素代表一步盘算，步骤从左到右。玄色代表1。最右边示意图灵机的停机。（图片泉源：Peter Krumins/Quanta Magazine）

图灵称，为了真正盘算出一个效果，图灵机最终必须得停机——不能卡死或者陷入循环。判别是否能停机的问题称为停机问题。他在1936年证实了天下上并不存在解决停机问题的万金油算法。

而“忙碌河狸”提出了以下问题：给定有限条规则，那么图灵机在停机之前最多能走若干步？

蒂博尔·拉多（图片泉源：俄亥俄州立大学档案）

比方说，我们只用一条规则，又要保证图灵机停机，那么这条规则一定就必须包罗停机指令。我们把停机问题的最长步数称为忙碌河狸数，那么BB(1) = 1，由于最多走一步就得停机。

自变量稍有增添，需要思量的图灵机数目就会爆炸性增进。若是允许有两条规则，就有6561种图灵机，而它们中，只有一只“忙碌的河狸”，它最长可以走6步。其他大多数图灵机都不停机，这些不停机的一定不是“忙碌的河狸”，不外对于一样平常的情形，要怎么才气区别出它们？究竟前面图灵已经证实，不管图灵机跑了1000步照样100万步，都不能咬定图灵机不会停下来。

这样就使得寻找忙碌河狸的义务异常艰难。规则的条数随便一改，我们就得从头最先找最长步数的图灵机，没有捷径。即是说，一样平常的“忙碌的河狸” 问题是“不能盘算的“。

要证实 BB(2) = 6 和 BB(3) = 107 就已经异常复杂了，拉多的学生 Shen Lin 做出了这个功效，并于1965年获得了博士学位。拉多以为， BB(4) 的问题是“彻底的绝望“，不外照样有人在1983年解决了这个问题。除此之外，研究人员对于5条规则的情形，已经找到了一种图灵机，它在运行47 176 870步之后停机，也就是说，BB(5) 最少比这个数字要大。而 BB(6) 最小也得有7.4 × 10³⁶⁵³⁴。亚伦森说：“除非能找到新看法新思绪，否则这个问题基本不能能获得解决。”

不能知的阈值

威廉·加斯塔克（William Gasarch）是马里兰大学学院市分校的盘算机科学家，他体贴的不是若何解决忙碌河狸数问题，相反他对“一样平常的不能盘算问题”异常感兴趣。他和其他数学家正以此为基础，来估量数学上一些未解之谜的难题水平，或是看看这些问题事实是否是可知的。

比方说哥德巴赫料想，说的是对于任何大于2的偶数，总能分解为两个质数的和。要是这个问题能获得解决，那么数论这一学科将迎来史诗般的一刻，数学家对质数漫衍的领会也会加倍深入。2015年，一位网名为Code Golf Addict的Github用户公布了一台27条规则的图灵机代码。这台图灵机异常稀奇，它当且仅当哥德巴赫料想不建立时，才会停机。实在很简朴，它一最先事情，就会从4最先，挨着检查哥德巴赫料想（固然也是靠遍历）。若是找到了所需的两个质数，就往上继续，以此往复。若是发现了不能示意为质数和的偶数，就会停机。

这种暴力的方式是不能能解决哥德巴赫料想的，由于若是不停机，我们永远也不会知道料想是不是准确的。不外，“忙碌河狸”问题为我们提供了一些思绪。如果我们能盘算出 BB(27) ，那我们最多也只需运行 BB(27) 这么多步，再往上若是还没停机的话，就说明哥德巴赫料想建立。究竟 BB(27) 就是27规则停机问题的最大步数了。若是在此之前就停机，自然说明料想不建立。

难题在于，BB(27) 是云云大的一个数，写下来都很难，要运行那么多次去磨练哥德巴赫料想，这在我们的宇宙中是远不能能的。虽然云云，谁人伟大的数字仍然是一个详细的数，亚伦森称，这代表着我们对于数论领域“现有知识的陈述”。

2016年，亚伦森同尤里·马季亚谢维奇（Yuri Matiyasevich）、斯特凡·奥里尔（Stefan O’Rear）一同做了一项类似的事情。他们设计了一台744条规则的图灵机，当且仅当黎曼料想不建立时停机。黎曼料想同样与质数的漫衍有关，是七大千禧问题之一，奖金高达一百万美元。亚伦森的这台图灵机只要运行 BB(744) 步，就能解决黎曼料想。固然这里也是同样暴力的算法，挨着遍历直到反例泛起。

BB(744) 比 BB(24) 又大了许多许多。不外亚伦森说道，要是深入研究一些简朴的问题，好比 BB(5) ，“就有可能从中发现一些自己就很有趣的数论问题。”例如，数学家帕斯卡尔·米歇尔（Pascal Michel）在1993年证实，现在保持着5规则步数纪录的谁人图灵机，其规则与考拉兹料想中函数行为极其相似，而后者是数学中又一个著名的未解之谜。

亚伦森说道：“这么多问题可以归结为‘图灵机是否停机？’，那若是我们能知道所有的‘忙碌河狸数’，就能解决所有问题。”

最近，亚伦森又在使用一种基于“忙碌河狸”的方式去丈量整个数学系统的“不能知阈值”。哥德尔1931年证实了他那著名的不完整定理：对随便的正义聚集，要么正义不相容（也就是会产生矛盾），要么不完整（存在不能证实的真命题）。而现代数学赖以生存的ZF聚集正义也绝不例外地存在哥德尔界线。而亚伦森想要用“忙碌河狸”去估量它的界线详细在那里。

2016年，他和他的研究生亚当·叶迪迪亚（Adam Yedidia）鼓捣出了一台7910条规则的图灵机，当且仅当ZF聚集理论不相容时停机。这就是说 BB(7910) 次盘算就能获得ZF聚集理论的相容性。而这些正义自己在盘算 BB(7910) 的时刻是用不到的，就像我们算2 2 = 4的时刻用不到聚集正义时一样。

奥里尔紧接着提出了一个更简朴的748条规则的图灵机，同样用来检测ZF正义。这样就把不能知的阈值降低了。奥尔良州立大学名誉教授，数理逻辑学家哈维·弗里德曼（Harvey Friedman）说：“这有些戏剧性，规则数变得没那么夸张了。”弗里德曼以为，这些数字还能进一步降低：“我以为最终谜底应该在50左右。”而亚伦森以为，真正的阈值应该靠近BB(20) 。

无论巨细，不能知的阈值的确是存在的。亚伦森说道：“自从哥德尔以来，我们的天下就一直是云云（不能知）；而‘忙碌河狸’函数得以让这一切加倍清晰明晰。”

原文链接：

https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/

本文来自微信民众号：全球科学（ID：huanqiukexue），撰文：John Pavlus，翻译：张和持