宜斌

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

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

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

忙碌的海狸

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

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

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

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