获奖;证明了最简单的通用图灵机

(主奖页面:Wolfram 2,3图灵机研究奖

“尽管这无疑很难证明,但这台图灵机最终可能会被证明是通用的。”

所以我写了709页一门新的科学(NKS)

我在计算的宇宙中寻找最简单的可能的宇宙图灵机.我找到了一个候选人——我的直觉告诉我,他可能是普世的。但我不确定。

作为纪念五周年的一部分一门新的科学今年5月14日,我们宣布一个25000美元的奖金来确定图灵机是否是通用的。

我不知道要花多长时间才能获奖。一个月?一年?一个十年?一个世纪?也许这个问题甚至在形式上是不可判定的(比如从通常的数学公理)。

但今天,我很激动地宣布,仅仅五个月后,我们就获得了诺贝尔奖——我们有了答案:图灵机事实上通用!

来自英国伯明翰的20岁大学生亚历克斯·史密斯拿出了一份40页的证明。

我很高兴我的直觉是正确的。但更重要的是,我们现在有了另一个证据来证明计算等价原理PCE一门新的科学

半个多世纪以来,我们一直在寻找最简单的通用图灵机。

在这儿。只有两个州和三种颜色。并且能够做任何可以做的计算。

图灵机

自从1936年艾伦·图灵发明了通用图灵机以来,我们已经取得了长足的进步四页用密集的符号来描述。

在20世纪中期,有一些更简单的通用图灵机被制造出来——从1962年开始,有7个州,4种颜色的图灵机。

这个记录保持了40年,直到2002年,我给了一台2.5通用机器一门新的科学

我们知道没有2 2机器可以是通用的。所以最简单的可能性是。

通过搜索2985984个可能的2、3台机器,我找到了一个候选人。到今天为止,我们知道这实际上是普遍的。

从我们日常使用电脑的经验来看,这似乎相当令人惊讶。毕竟,我们已经习惯了cpu经过精心设计,有数百万个门的计算机。

看起来很奇怪,我们居然能够用像上面那样简单的机器来实现通用计算——我们只需要在可能的机器空间里做一点搜索就能找到。

但这是我们从NKS得到的新直觉。在计算的宇宙中,像普适性这样的现象实际上是相当普遍的——即使在规则非常简单的系统中也是如此。

只是在我们正常的工程工作中,我们受到了太多的限制,无法看到这些东西。

从我对计算领域的所有研究中,我得出了一个非常普遍的原理,我称之为计算等价原理。

它本质上说的是:当一个人看到不明显简单的行为时,它本质上总是对应于一个在某种意义上最复杂的计算。

有人可能认为计算能力是一个渐进的现象:随着系统规则复杂度的增加,系统将逐渐显示出更强的计算能力。

但是PCE说这不是它的工作原理。它表示,在一个非常低的阈值之上,所有系统的计算能力将完全相同。

如果这是真的,就会产生一些非常基本的后果。关于精确科学的局限性关于宇宙中智慧的出现。关于自由意志的现象。关于为什么数学很难。关于技术的新方向。

但是PCE是真的吗?

我肯定是。但是,就像科学中的许多基本原则一样,这不是一种可以抽象证明的东西。

相反,人们必须通过积累证据来判断它是否正确——通过做实验,看结果如何。

嗯,PCE的一个预测是,一旦人们看到像图灵机这样的东西,它的行为是复杂的,这个系统最终将是通用的——即使它的基本规则真的很简单。

这是一个理论上可以验证的预测。

第一个重大的考验出现在NKS的书中:在最简单的细胞自动机中,110规则已经是普遍的。

那么图灵机呢?这就是奖励的意义所在。

到今天为止,我们知道PCE的预测也得到了验证。

我们做了一个实验;验证PCE。

但与一些科学实验不同的是,它不需要数十亿美元的粒子加速器。只是一个20岁的大学生用了一台电脑。

我真想知道什么样的人会赢得我们的奖。我认为成为“专业”和“业余”的几率是差不多的。

我不知道证明是否需要花哨的数论或其他只有“专业人士”才能理解的数学。或者它是否可以完全用显式的“基本”计算术语来完成。

但是,在6月30日(周六)20:53:59,也就是我们宣布获奖后的47天,我们收到了一份意见书,上面对提交人的描述是:“Alex Smith是英国伯明翰大学电子与计算机工程专业的本科生。”他有数学和深奥编程语言的背景。”

我们看了看。40页详细的论证和代码。很明显,这是一次严肃的服从。我们开始分析它。

它显然走了很长一段路。但它还没有被证明具有通用性,因为实际上它仍然需要一个单独的通用计算机来为2,3机器设置每个程序。

8月1日,我们发回了详细的评论。六天后,一份修改过的证据出现了——这更接近事实了。

我们给我们的奖委员会.委员会的一位成员问这个证明是否真的满足他在1956年的一篇开创性论文中给出的关于普遍性的正式定义。

几周后,我们收到了另一个版本,澄清了这一点。

这里有相当多的微妙之处。早期的普适性定义假设图灵机器的程序必须只包含有限数量的“非零位”——并且图灵机器必须“停止”。

但是2,3图灵机——就像现代计算机(或自然界的系统)一样——不会“停止”。在亚历克斯·史密斯的设计中,图灵机“磁带”(即。(如内存)必须用无限的位元模式来填充。

但关键的一点是,位的模式可以在不进行通用计算的情况下建立。这意味着当我们看到通用计算时,它实际上是由2,3机器完成的,而不是我们使用的编码。

Alex Smith需要做的是建立普遍性并赢得这个奖项,只是为了证明存在一些编程方式为2、3机器做任何计算。有可能制作一个“编译器”,为一些已知的通用机器类编译“代码”,为2,3机器编写代码。

他这么做。但是他的“编译器”并没有做出非常紧凑或高效的代码。事实上,除了最简单的情况之外,任何情况下,代码都趋向于非常庞大且效率非常低。

但这不是重点。要点之一是原理:2,3图灵机是通用的。

毫无疑问,我们有可能找到更好的编译器,编写出更好的代码。

那将会很有趣。也许有一天,甚至会有实用的分子计算机,由这个2,3图灵机建造而成。

磁带有点像RNA链,头部像核糖体一样上下移动。

当我们想到纳米级计算机时,我们通常会想象仔细地设计它们,以模仿我们今天所知道的计算机的结构。

但nks的其中一个教训——由亚历克斯·史密斯的证明再次带回家——是,有一种完全不同的操作方式。

我们不需要小心翼翼地用工程学来构建东西。我们可以走出去,在计算的宇宙中搜索,找到像通用计算机这样简单到我们可以想象用分子制造它们的东西。

几天前,我给Alex Smith打了电话,告诉他我们最终确信他解决了问题并赢得了奖金。

我问他为什么要做这件事。他说他认为这是一个很好的难题。一开始,他非常确信图灵机器的行为非常简单,他可以证明它是正确的不是普遍的。但后来,在他研究的过程中,他意识到还有一些更复杂的行为。正是通过这些,他展示了普遍性。

这是一件非常好的作品。在计算宇宙中建立了一座伟大的纪念碑——图灵机器普适性边缘的标志。

我们计划在几周内举行一个正式的颁奖典礼——非常合适,在Bletchley Park图灵(Alan Turing)在这里从事战时工作。

但现在,我很高兴看到这么好的科学成果出来了。

花25000美元是一种非常令人满意的方式。


有关其他说明,请参见简单图灵机、通用性、编码等。

Baidu