注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

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

2010-04-24 18:18:08|  分类: 人工智能 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转 2,3图灵机通用性得证 英国大学生获得2.5万美元奖金  - 易拉罐bb - 易拉罐的博客

图灵机是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图灵机是最简单的通用图灵机,证实了这个很早就已经提出的猜想,解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破,无疑是信息学界中的一件激动人心的大事。
http://www.matrix67.com/blog/archives/334

  评论这张
 
阅读(253)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017