哥德巴赫猜想解决了吗？揭示数学的基本极限 _生活百科

文章插图

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

程序员通常希望最小化代码的执行时间。但在1962年，匈牙利数学家提博尔·拉多提出了相反的问题。他问，一个简单的计算机程序在终止之前最多能运行多少步骤？拉多将这些效率最高但仍能正常工作的程序称为“忙碌的海狸” 。
自从1984年在《科学美国人》的“计算机娱乐”专栏中流行以来，对于程序员和其他数学爱好者来说，寻找这些程序一直是一个极其有趣的谜题。但在过去的几年里，忙碌的海狸游戏已经成为一个研究的对象，因为它与数学中一些最崇高的概念和开放问题产生了联系。
最近的工作表明，搜索长时间运行的计算机程序可以阐明数学知识的状态，甚至告诉我们什么是可知的。根据研究人员的说法， “忙碌的海狸”游戏为评估某些问题的难度提供了一个具体的基准，例如尚未解决的哥德巴赫猜想和黎曼假设。它甚至让我们看到，数学背后的逻辑基石在哪里崩溃了。近一个世纪前，逻辑学家库尔特·哥德尔就证明了这种数学未知领域的存在。但忙碌的海狸游戏可以显示它实际上在数轴上的位置，就像一幅描绘世界边缘的古老地图。
无法计算的电脑游戏

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

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

【哥德巴赫猜想解决了吗？揭示数学的基本极限】每个规则都有这种分叉的“选择自己的冒险”风格。有些规则说要回到以前的规则，最终会有一条包含“停止”指令的规则。图灵证明，只要有正确的指令和足够的时间，这种简单的计算机就能进行任何可能的计算。
正如图灵在1936年指出的，为了计算一些东西，图灵机最终必须停止——它不能陷入无限循环。但他也证明了，没有可靠的、可重复的方法来区分机器停机和机器简单地无限循环运行，这个事实被称为停机问题。
“忙碌的海狸”游戏的问题是：给定一定数量的规则，在图灵机停止运行之前，它能执行的最大步骤是多少？

文章插图

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

例如，如果只允许一条规则，并且想要确保图灵机停止，那么这条规则里必须包含停止指令。单规则机器的忙碌的海狸数为1 ，即BB(1) =1 。
但只要再增加几条规则，需要考虑的机器数量马上就会激增。有两个规则的6561个可能的机器中，在停止运行之前的最大步骤是6步，也有些干脆无限循环了。这些都不是忙碌的海狸，但你如何确定地排除它们呢？图灵证明了，没有办法自动判断运行1000步或100万步的机器最终会不会终止。