计算机程序揭示了数学基本极限

宜斌

忙碌的海狸（Busy Beaver）游戏的目标是找到运行时间最长的计算机程序，它与数学有着令人惊讶的联系。该游戏是由匈牙利的数学家Tibor Radó在1962年发表的论文《On Non-Computable Functions》中提出的。

在计算机科学中，忙碌的海狸是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多地输出1。

然而对于程序员和其他数学爱好者来说，找到这些程序一直是一个巨大的难题。在过去的几年中，繁忙的海狸游戏之所以成为一个研究对象，是因为它与某些高阶的概念和数学中的开放性问题产生了联系。

忙碌的海狸

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

德克萨斯大学奥斯汀分校的理论计算机科学家Scott Aaronson说：“在数学上，有趣的娱乐与实际上重要的事物之间存在非常容易结合之处。”

最近的数据表明，运行时间长的计算机程序的搜索可以阐明数学知识的状态，甚至可以告诉我们什么是已知的。根据研究人员的说法，忙碌的海狸游戏为评估某些问题（例如未解决的哥德巴赫猜想和黎曼假设）的难度提供了具体的基准，它甚至可以让研究者一目了然地了解数学背后的逻辑基础。

什么是图灵机？图灵机是一个虚拟的机器，尽管这个机器很简单，但它可以模拟计算机的任何算法，无论这个算法有多复杂。

忙碌的海狸游戏全都涉及图灵机的行为——图灵机是1936年由艾伦·图灵（Alan Turing）构思的原始的理想化计算机，图灵机对被分成正方形的环形胶带执行动作，根据规则列表进行操作。

图灵机的简单示意图

假设有一个无穷的纸带，纸带就像一个存储器一样。纸带上面的每个格子是空白的，但是可以读写数据，在这个例子里，机器只能写0或1，或者什么也不写，这个机器就是包含3个信号的图灵机。

这个机器有一个探头，这个头可以移动到每一个空格上，用这个头，机器可以有3个基本操作——1.读空格的数据;2.编辑数据，可以是写一个新的数据，可以是擦除数据;3.移动纸带向左或者向右，这样机器可以读或者编辑旁边的格子。

不可知的阈值

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

忙碌的海狸游戏会问：给定一定数量的规则，图灵机停止之前可以执行的最大步数是多少？如果只允许一个规则，并且要确保图灵机停止，则必须立即添加停止指令。

目前还没有通用的方法来确定运行时间最长的图灵机，抛开一大堆的数学公式计算，马里兰大学学院分校的计算机科学家William Gasarch表示，他对固定忙碌的海狸数量的前景不感兴趣，而对“实际上却无话可说的一般概念”感兴趣。他和其他数学家主要对使用游戏作为衡量标准来衡量数学中重要的未解决问题的难度，或找出所有数学上可以理解的东西感兴趣。

还有网友问到量子计算机对运行这种忙碌的海狸图灵机有加速作用吗？结论是没有。因为图灵机运行过程是顺序性的，前面的没运行过，后面的就运行不了，所以量子计算机的并行运算对它使不上劲。