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