第四章：图灵论题.ppt

*计算理论*引言什么是计算?计算机的基本能力和局限性是什么?*(1912–1954)In1936,Turingintroducedhisputationinhisarticle“putableNumbers,”.Atthesametime,AlonzoChurchpublishedstandardmodel*引言图灵机(TuringMachine,TM),是计算机的一种简单的数学模型。历史上,冯•诺曼计算机的产生就是由图灵机诱发的。丘奇—图灵论题:一切合理的计算模型都等同于图灵机.*—图灵论题 *(TurningMachine)非形式化描述根据当前状态和字符xi,决定写移转三动作-写letter,有存储器-左或右移动转移状态可以作循环语句磁带相当于数组,可读写。这是增加的重要资源internalstatesetQRL每一步,读写头在单向无穷带上左右移动并读写。*图灵机stateq0初始,带子上只有输入串w*,其它地方是空的。开始状态q0。计算过程中读写头左右移动,机器内部状态改变,带子上内容重写。数组结构*图灵机输出约定三种输出:接受、拒绝、eptstateqrejector非常规意义循环——不停机引出可判定性*图灵机与有限自动机状态控制器相似性:有限状态集区别:(1)图灵机在带子上既能读也能写。(2)图灵机的读写头既能向左也能向右移动。(3)图灵机的带子是无限长的。(4)图灵机进入拒绝和接受状体将立即停机。*图灵机考虑图灵机M1,它检查语言B={w#w|w∈{0,1}*}的成员关系。即设计M1,使得如果输入是B的成员,它就接受,否则拒绝。M1=“对于输入字符串w(1)在#两边对应的位置上来回移动,检查这些对应位置是否包含相同的符号,如不是,或者没有#,则拒绝,为跟踪对应的符号,消去所有检查过的符号。(2)当#左边的所有符号都被消去时,检查#右侧是否还有符号,如果有则拒绝,否则接受。”