号外:2,3图灵机通用性得证 英国大学生获得2.5万美元奖金

    图灵机是1936年Alan Turing提出的一个计算机模型。这种计算机由一个一维数组(或者叫磁带)构成,还有一个可以左右移动的指针。磁带上每个格子里都有一种颜色(共可从m种颜色中选择),指针本身则可以是n种状态中的一种。给定一个m*n的表格,你就定义了一个图灵机。这个表格告诉机器,如果当前指针的状态是x,它所指的格子的颜色是y,那么下一步机器应该把这个格子染成什么颜色,然后指针应该左移一位还是右移一位,指针的新状态又是什么。有了一个图灵机后,我们便可以把它当做一个计算机进行数据处理了。我们可以给这个图灵机编写一个初始状态(也就相当于现在所说的程序和数据),让它按照这个表格不断执行下去,对数据进行处理并“输出”适当的结果来。
    能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。不是所有的图灵机都是通用的:很多图灵机只能完成一些特定的运算,而只有通用图灵机才能完成更一般的操作,是一台“通用的”机器。这些通用图灵机就像现代计算机一样,可以用来编程执行各种各样的操作,能实现现代计算机的各种功能。我们经常说一种程序语言是图灵完全的(Turing Complete),指的就是这种语言等价于通用图灵机,能够执行任何一种复杂的数学运算。
    50年代起,科学家们疯狂地寻找通用图灵机,所需要的颜色数和状态数越来越小。最好的结果是1967年由Marvin Minsky得到的,他发现了一个7,4通用图灵机,即一个只需要7种状态,4种颜色的通用图灵机。人们开始好奇,最简单的通用图灵机是什么样子的。2002年,Stephen Wolfram(没错,就是MathWorld的那个Wolfram)做出了一个重大的突破:他发现了一个2,5通用图灵机,并且给出了一个很可能是通用图灵机的2,3图灵机。很早以前人们就证明了,不存在2,2的通用图灵机;因此如果Wolfram提出的2,3图灵机是通用图灵机的话,它就是最小的通用图灵机了。但Wolfram始终不能证明这个2,3图灵机是通用的,于是在今年三月份用25000美元悬赏征解。
    昨天,英国伯明翰大学的一名20岁在校大学生Alex Smith提交了一篇55页的论文,证明了Wolfram的2,3图灵机与另一个已知的通用机器等价,从而证明了2,3图灵机是最简单的通用图灵机,证实了这个很早就已经提出的猜想,解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破,无疑是信息学界中的一件激动人心的大事。

做人要厚道 转贴请注明出处
新闻来源:来源1 来源2

7 条评论

回复给 dasdfasdfasdf 取消回复

  ×  1  =  4