《形式语言自动机-图灵机(二).ppt》由会员分享，可在线阅读，更多相关《形式语言自动机-图灵机(二).ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对基本图灵机的扩展 多带图灵机（多带图灵机（Multitape Turing Machines）双向无限带图灵机双向无限带图灵机5.3 修改型图灵机 基本图灵机是计算的一种通用模型，对它进行某些修改，会得出更复杂的图灵机。从可计算性角度来讲，能够证明这些图灵机和基本图灵机是等价的。1School of Computer Science&Technology,BUPT具有双向无限带的图灵机具有双向无限带的图灵机带头（带头（tape head）带带（tape）单元格单元格（cell）空白（空白（blank）带符）带符带符（带符（tape symbol）2School of Computer Sci
2、ence&Technology,BUPT双向无穷带的图灵机与基本图灵机的等价双向无穷带的图灵机与基本图灵机的等价 可以用一个双道的单向无穷带图灵机可以用一个双道的单向无穷带图灵机M1模拟具有双向模拟具有双向无穷带的基本图灵机无穷带的基本图灵机M.当M的读写头从初始位置右移时，M1用上道模拟M当M的读写头从初始位置左移时，M1用下道模拟MM1的初始单元：X0,￥,￥表示输入带最左单元。M1的形式构造：Q1=q,U,q,DqQq11=I,J,I,￥I,J,￥T1=Xi,B Xi TF1=q,U,q,D qF￥3School of Computer Science&Technology,BUPT多带
3、图灵机多带图灵机 多带图灵机由一个有限控制器，多带图灵机由一个有限控制器，n个读写头和个读写头和n条双向无条双向无限带组成。限带组成。一次动作：一次动作：n控制器状态转变控制器状态转变n每个读写头在扫到的单元重写一个字符每个读写头在扫到的单元重写一个字符n各读写头各自向左各读写头各自向左/右移动一个单元（含不移动的情况）右移动一个单元（含不移动的情况）x转移函数：转移函数：Qk QkL,R,Sk k是带的个数是带的个数形如形如(qi,a1,a2,ak)=(qj,b1,b2,bk,L,R,，L)4School of Computer Science&Technology,BUPT多带图灵机多带图
4、灵机定理：每个多带图灵机都有一个与之等价的单带图灵机定理：每个多带图灵机都有一个与之等价的单带图灵机.n假设M有k条带，nS将k条带的信息都存在它的一条带上，用新的符号#作为定界符，以分开不同带的内容。n此外，S还要记录读写头的位置，这里用符号加“点”来标记，S把它想象为虚拟读写头。（也可用双道+识别符）5School of Computer Science&Technology,BUPT非确定图灵机非确定图灵机 下一个移动步有多种选择下一个移动步有多种选择 转移函数可以转移函数可以为为 :Q 2Q D，其中其中 Q、和和 D 分分 别为有限状态集、带符号集和带头的移动方向别为有限状态集、带符
5、号集和带头的移动方向.即即 (q,X)为三元组的集合：为三元组的集合：(q1,Y1,D1),(q2,Y2,D2),(qk,Yk,Dk)非确定图灵机语言接受能力与（确定的）基本图灵机等价非确定图灵机语言接受能力与（确定的）基本图灵机等价（证明略）（证明略）6School of Computer Science&Technology,BUPT图灵机与计算机 以普通计算机模拟图灵机以普通计算机模拟图灵机 以多带图灵机模拟普通计算机以多带图灵机模拟普通计算机7School of Computer Science&Technology,BUPT以普通计算机模拟图灵机以普通计算机模拟图灵机 采用适当的数据
6、结构（如转移表）不难编制普通的计采用适当的数据结构（如转移表）不难编制普通的计 算机程序实现图灵机的有限状态控制机制算机程序实现图灵机的有限状态控制机制.存在问题的存在问题的 是如何模拟无限延伸的带，因为普通计算机的存储空是如何模拟无限延伸的带，因为普通计算机的存储空 间（包括各个级别的存储器间（包括各个级别的存储器）是有限的是有限的.但是，可以假但是，可以假 想一种可以无限扩充存储量的存储系统想一种可以无限扩充存储量的存储系统.实际上，可装实际上，可装 卸的卸的 外存系统并不严格规定存储量的上限，而且并非外存系统并不严格规定存储量的上限，而且并非 所有信息都需要在线存储所有信息都需要在线存储
7、.8School of Computer Science&Technology,BUPT以多带图灵机模拟普通计算机以多带图灵机模拟普通计算机 可以用多带图灵机模拟典型的存储程序式计算机，参可以用多带图灵机模拟典型的存储程序式计算机，参 见以下示意图见以下示意图.必要时，可增加更多的带必要时，可增加更多的带.9School of Computer Science&Technology,BUPT图灵机的本质特征图灵机的本质特征 图灵机的本质特征：图灵机的本质特征：可以无限制的访问无限的存储器。可以无限制的访问无限的存储器。这一特征将它和有限自动机，下推自动机等某些较弱这一特征将它和有限自动机，下推自动机等某些较弱的模型区别开来。的模型区别开来。已经证明：所有有此特点的模型在能力上都是等价的，已经证明：所有有此特点的模型在能力上都是等价的，只要它们满足一些合理的必要条件即可（如只要它们满足一些合理的必要条件即可（如“在一步中只能在一步中只能执行有限的工作量执行有限的工作量”）语言中的例子：语言中的例子：LISPPASCAL 描述了相同语法类。描述了相同语法类。10School of Computer Science&Technology,BUPT