图灵机的思想与模型简介.ppt

/38,图灵机的思想与模型简介,-图灵的贡献,-图灵机：计算机的理论模型,-指令、数据、程序与程序执行,冯.诺依曼计算机：机器级程序及其执行,2.2.1 图灵机的思想与模型简介,钙岁契跋灿滇搐岁蹋蔽险逃瑶挨戌挞肾僻名晾世颈依湛霹悍顽娃睡照育私图灵机的思想与模型简介图灵机的思想与模型简介,图灵及其贡献,图灵,(Alan Turing,19121954)，出生于英国伦敦，19 岁入剑桥皇家学院，22 岁当选为皇家学会会员。,1937 年，发表了论文论可计算数及其在判定问题中的应用，提出了,图灵机模型,，后来，冯,诺依曼根据这个模型设计出历史上第一台电子计算机。,1950 年，发表了划时代的文章：机器能思考吗?,成为了人工智能的开山之作。,计算机界于1966年设立了最高荣誉奖：,ACM 图灵奖,。,图灵是谁?,你能查阅一下哪些人获得图灵奖了吗？因为什么贡献而获奖呢？,循背觅昏氢惺吩诵册捏锰货鄂苛濒拎师戒兼痒恃剩战颅律么码忻耶必根歪图灵机的思想与模型简介图灵机的思想与模型简介,所谓,计算,就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的,变换过程,。,计算,10001110110,0110101,10001,0110101,由“程序”控制，一步步将输入“转换”为输出,输入,输出,程序,通用机器,图灵认为什么是计算?,寒檄伏缚沿裹泄竹凉邑糠蛤过爷坦蹄淆坞目障贡爵起曝繁碟箔虎睁哟触茸图灵机的思想与模型简介图灵机的思想与模型简介,图灵机的思想,是关于数据、指令、程序及程序/指令自动执行的基本思想。,输入被制成一串0和1的纸带，送入机器中-,数据,。如00010000100011,机器可对输入纸带执行的,基本动作,包括：,“,翻转0为1,”,，或,“,翻转1为0,”,“,前移一位,”,“,停止,”,。,对基本动作的控制-,指令,，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示,：,01,表示,“,翻转0为1,”,(当输入为1时不变)，,10,表示,“,翻转1为0,当输入0时不变),11,表示,“,前移一位,”,00,表示,“,停止,”,。,输入如何变为输出的控制可以用指令编写一个,程序,来完成,如:,01,11,10,11,01,11,01,11,00,机器能够读取程序，按程序中的指令顺序读取指令，,读一条指令,执行,一条指令。由此实现,自动计算,。,乙奉帽浆寂镜铱慌篮紫撮奢绥掩厘坎抨哎舒础癣舍惜帝刃橡勃陋釉垫藉藤图灵机的思想与模型简介图灵机的思想与模型简介,基本的,图灵机模型,为一个七元组,如右图示意,几点结论:,(1)图灵机是一种思想模型，它由一个控制器(有限状态转换器)，一条可无限延伸的带子和一个在带子上左右移动的读写头构成。,(2),程序是五元组形式的指令集,。其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方格中写入符号Y,然后向右移一格R(或向左移一格L或不移动N),同时将机器状态设为p供下一条指令使用。,图灵机是什么?,图灵机模型,鞍狮脊歪洱霜爹亿榷昨沼邓荐东敲湿迹粟喀悸溪栓烂柱艘氮完释钡纹篡畴图灵机的思想与模型简介图灵机的思想与模型简介,图灵机模型示例,。,(注:圆圈内的是状态，箭线上的是，其含义见前页),执行过程,功能：将一串1的后面再加一位1,0 0 1 1 1 1 0 0 0,控制器,(S,1,0,0,R,S,1,),(S,1,1,1,R,S,2,),(S,2,1,1,R,S,2,),S,2,0,1,L,S,3,),(S,3,1,1,L,S,3,),(S,3,0,0,N,S,4,),S,1,S,2,S,3,S,4,1,1,R,1,1,R,0,1,L,1,1,L,0,0,N,S,1,：开始状态,S,2,：右移状态,S,3,：左移状态,S,4,：停机状态,0,0,R,0 0 1 1 1 1 0 0 0,0 0 1 1 1 1 0 0 0,(S,1,0,0,R,S,1,),(S,1,1,1,R,S,2,),0 0 1 1 1 1 0 0 0,(S,2,1,1,R,S,2,),0 0 1 1 1 1 0 0 0,(S,2,0,1,L,S,3,),0 0 1 1 1 1 1 0 0S,3,1,1,L,S,3,),0 0 1 1 1 1 1 0 0,(S,3,0,0,N,S,4,),钾汐焊赣攒碉谣柄沾哩怪疽镜票荐函棒享邱松钾帆深叁缝卖贰棋垢庭摔埂图灵机的思想与模型简介图灵机的思想与模型简介,几点结论(续):,(3),图灵机模型,被认为是计算机的基本理论模型,-计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种离散的、有穷的、,构造性的,问题求解思路，,一个问题的求解可以通过构造其图灵机(即程序)来解决,。,(4)图灵认为：,凡是能用算法方法解决的问题也一定能用图灵机解决,;,凡是图灵机解决不了的问题任何算法也解决不了,-图灵可计算性问题。,魁宣悍京毗屋扛釉亲跋旅帧讥强窜魏静瓦稗往撩静棍烬境陋辩泞绊啥圣尊图灵机的思想与模型简介图灵机的思想与模型简介,谢谢观看,！,过三第一组全体成员！,剐淮牡霹姚波祖纹速嘱忿冠射食靶慌客真僧炉恃裹颂岸狈纽厂特亨旗评粤图灵机的思想与模型简介图灵机的思想与模型简介,