丘奇图灵论题.pptx

1朴秀峰xfpiao@计算理论第3章丘奇--图灵论题2引言什么是计算?计算机的基本能力和局限性是什么??什么是数据库什么是数据仓库还在争论什么是数据网格解决方法,给出大众能理解的代表4引言计算机科学历史上关于概念的争论解决的办法,给出一个代表什么是3的倍数{3N|N=1,2,3},{x|xmod3=0}代表元:3什么是操作系统代表元:Windows,代表元:大众理解:Web,IE什么是计算?多个模型;代表元:图灵机,或递归函数论5引言在还没有计算机的时候,凭想象力把后来出现的把计算机的理论模型建立起来了。1936年想得如此周到、(1912–1954)In1936,Turingintroducedhisputationinhisarticle“putableNumbers,”.Atthesametime,AlonzoChurchpublishedstandardmodel7引言图灵机(TuringMachine,TM),是计算机的一种简单的数学模型。历史上,冯•诺曼计算机的产生就是由图灵机诱发的。丘奇—图灵论题:—图灵论题 (TurningMachine)非形式化描述根据当前状态和字符xi,决定写移转三动作-写letter,有存储器-左或右移动转移状态可以作循环语句磁带相当于数组,可读写。这是增加的重要资源internalstatesetQRL每一步,读写头在单向无穷带上左右移动并读写。10图灵机stateq0初始,带子上只有输入串w*,其它地方是空的。开始状态q0。计算过程中读写头左右移动,机器内部状态改变,带子上内容重写。数组结构