五条规则的图灵机可视化。每列像素代表一步计算,步骤从左到右。黑色代表1。最右边表示图灵机的停机。(图片来源:Peter Krumins/Quanta Magazine)
“忙碌的河狸”这个问题的目的是为了找到运行时间最长的电脑程序。对它的研究与哥德巴赫猜想、黎曼猜想等一系列数学难题建立了惊人而又深刻的联系。程序员总想让代码跑的更快。
可在1962年,匈牙利数学家蒂博尔·拉多(Tibor Radó)却提出了截然相反的问题:要怎么才能让一个简单的电脑程序在终止之前跑的尽可能久?拉多将这样跑得尽可能低效但仍有效的程序称为“忙碌的河狸”。自从《科学美国人》于1984年刊载这则问题之后,众多程序员和业余数学爱好者们纷纷开始寻找“忙碌的河狸”。
不过最近几年,由于与一些高大上的概念与数学未解的难题建立起联系,“忙碌的河狸”已经变成了非常严肃的数学问题。最近一项研究表明,这些得跑到猴年马月的程序,或许能澄清一些数学命题,甚至告诉我们哪些内容是可知的。据研究者们称,忙碌的河狸能帮助我们判断一个数学问题的难易程度,比如哥德巴赫猜想和黎曼猜想。它能让人一目了然地看到数理逻辑到哪里就该走不下去了。
逻辑学家库尔特·哥德尔(Kurt Gödel)在大半个世纪之前就证明了,有一些命题既不能证明也不能证伪,也就是所谓的“不可知”。不过现在,忙碌的河狸能为我们指出,这个“不可知”究竟位于什么地方。
“忙碌的河狸”这个问题,归根结底是关于图灵机——这是阿兰·图灵(Alan Turing)于1936年提出的一种理想化模型,其中有一条被分为正方形小块的长度无限的纸带,用笔在上面写或者擦去记号,这些操作需要满足一套给定的规则。每一项规则都像冒险棋一样。有些规则甚至可以让你跳回到之前的规则。在这些规则中,最终有一条“停机”的指令。图灵证明,如果时间充足,规则得当的话,图灵机就能做任何计算。
困难在于,BB(27) 是如此大的一个数,写下来都很难,要运行那么多次去检验哥德巴赫猜想,这在我们的宇宙中是远不可能的。虽然如此,那个巨大的数字仍然是一个具体的数,亚伦森称,这代表着我们对于数论领域“现有知识的陈述”。
无论大小,不可知的阈值的确是存在的。亚伦森说道:“自从哥德尔以来,我们的世界就一直是如此(不可知);而‘忙碌河狸’函数得以让这一切更加清晰明了。”