用跑得最慢的电脑程序,理解最高深的哥德巴赫猜想

“忙碌的河狸”这个问题的目的是为了找到运行时间最长的电脑程序。对它的研究与哥德巴赫猜想、黎曼猜想等一系列数学难题建立了惊人而又深刻的联系。
程序员总想让代码跑的更快。可在1962年,匈牙利数学家蒂博尔·拉多(Tibor Radó)却提出了截然相反的问题:要怎么才能让一个简单的电脑程序在终止之前跑的尽可能久?拉多将这样跑得尽可能低效但仍有效的程序称为“忙碌的河狸”。
最近一项研究表明,这些得跑到猴年马月的程序,或许能澄清一些数学命题,甚至告诉我们哪些内容是可知的。据研究者们称,忙碌的河狸能帮助我们判断一个数学问题的难易程度,比如哥德巴赫猜想和黎曼猜想。它能让人一目了然地看到数理逻辑到哪里就该走不下去了。逻辑学家库尔特·哥德尔(Kurt Gödel)在大半个世纪之前就证明了,有一些命题既不能证明也不能证伪,也就是所谓的“不可知”。不过现在,忙碌的河狸能为我们指出,这个“不可知”究竟位于什么地方,就如同一张古老的地图指引旅者走向世界的边缘。
无法计算的问题

要证明 BB(2) =6和BB(3) =107就已经非常复杂了,拉多的学生Shen Lin做出了这个成果,并于1965年获得了博士学位。拉多认为, BB(4) 的问题是“彻底的绝望“,不过还是有人在1983年解决了这个问题。除此之外,研究人员对于5条规则的情况,已经找到了一种图灵机,它在运行47176870步之后停机,也就是说,BB(5) 起码比这个数字要大。而BB(6) 最小也得有7.4 × 1036534。亚伦森说:“除非能找到新观点新思路,否则这个问题根本不可能得到解决。”
不可知的阈值
原文链接:
IEEE Spectrum
《科技纵览》
官方微信公众平台

