今天我们为一台小型图灵机颁奖

(本文最初发表于Wolfram的博客.)

也许具有讽刺意味的是,在发布了可能是有史以来最复杂的计算系统之后的两周,我们今天宣布了一个对于最简单的计算系统。

但今天是五周年的出版一种新的科学为了纪念这一点,我们决定设立第一个NKS奖。

该奖项与NKS基础科学的一个核心目标有关:绘制出可能的计算系统的抽象宇宙。

我们从NKS了解到,非常简单的程序可以显示非常复杂的行为。在NKS的书中,我制定了计算等价原理这就解释了这一发现。

这一原则有很多预测。其中之一就是通用计算的能力,即能够进行通用计算的能力,即使在规则非常简单的系统中也应该是普遍的。

今天的cpu有数百万个组件。但是计算等价原则意味着所有种类的非常简单的系统也应该支持通用计算。

NKS的书已经给出了几个引人注目的例子。但该奖项的目的是为一种特别经典的计算系统——图灵机——确定通用计算的边界。

1936年,艾伦·图灵发明了图灵机,作为第一个成功的抽象计算模型,图灵机在理论计算机科学中得到了广泛的应用。

但在NKS的整个框架出现之前,研究特定的简单图灵机似乎只是一种好奇。事实上,即使他确实有能力做到这一点,我也不相信艾伦·图灵自己曾经明确地模拟过任何图灵机。

在NKS的书中,我发现了目前已知的最简单的通用图灵机2个州和5种颜色

我还对更简单的图灵机做了广泛的研究。在这样做的时候,我发现一个更简单的通用性候选:下面的2,3图灵机:

2、3图灵机

我对这台机器做了不少分析。但我既不能证明它是普遍的,也不能证明它不是。

这很容易模拟Mathematica.事实上,在Mathematica6我们只是添加了一个内置的图灵机函数.所以运行这台机器的t步就是:

图灵机器[{596440,2,3},{1,{{},0}},t]

在过去的五年中,我们做了各种各样的事情来帮助支持NKS社区的发展。

今天我们又增加了一个奖项:我们正在建立我们的第一个NKS奖。

我们将提供25,000美元给第一个能确定上述2,3图灵机是否是通用的人或团体,并能提供证明。

所有的细节都在www.wolframprize.org

Baidu