演示文稿计算理论图灵机.pptVIP

4.2.2 多带图灵机 当前第30页\共有64页\编于星期五\5点 4.2.2 多带图灵机 定理4-2 如果一个语言L被一个多带图灵机接受，它就能被一个单带图灵机接受。 当前第31页\共有64页\编于星期五\5点 4.2.3 非确定图灵机 【例4-8】下面的图灵机就是不确定图灵机。无向图G中，从a出发合法路径判定的不确定型图灵机。 当前第32页\共有64页\编于星期五\5点 4.2.3 非确定图灵机 非确定图灵机由一个有穷控制器、一条带和一个读头组成。对于一个给定的状态和被读头扫描的带符号，机器的下一个动作将有有穷个选择。 设一个非确定图灵机 M1=( K, Σ,Γ,δ,q0, B, F)，除转移函数δ外，其它同一般图灵机的定义。转移函数δ仍是从K×Γ到K×Γ×{L,R,S}上的映射，但它可能有多个映射的像,即存在q∈K, a∈Σ, δ(q,a)= (p1, b1, c1) δ(q,a)= (p2, b2, c2) …… δ(q,a)= (pr, br, cr) 当前第33页\共有64页\编于星期五\5点 4.2.3 非确定图灵机 定理4-3 如果语言L被一个非确定图灵机M1接受，则L将被某个确定图灵机M2接受。 当前第34页\共有64页\编于星期五\5点 4.2.4 多头图灵机 一个k头图灵机有k个读头，一个控制器和一条带，读头由1到k编号，图灵机的一个动作由当前状态和被每个读头所扫描的符号。在一个动作中，每个读头独立地左移、右移或不动。 定理4-4 如果L被某个k个读头的图灵机接受，则它能被一个单头图灵机接受。 当前第35页\共有64页\编于星期五\5点 4.2.5 多维图灵机 多维图灵机具有通常的有限控制器，但带却由k维单元阵列组成。这里，在所有2k个方向上（k个轴，每轴正、负两个方向），都是无限的，根据状态和扫视的符号，该装置改变状态，打印一个新的符号，在2k个方向上移动它的读头，开始时，输入沿着一个轴排列，读头在输入的左端。 当前第36页\共有64页\编于星期五\5点 4.2.6 离线图灵机 定理4-5 如果L被一个二维图灵机M1接受，那么L将被一个一维图灵机M2接受。 当前第37页\共有64页\编于星期五\5点 4.2.7 图灵机的组合 当前第38页\共有64页\编于星期五\5点 4.2.7 图灵机的组合 【例4-9】 设计一个TM ，完成乘法运算m×n。开始时带上符号为：0m10n1，结束时带上符号为0mn，用子程序调用的方式完成。 设计思想是：每当抹去左边一个０，就在第二个１后面拷贝n个０。当第一个１的左边全变为B时，带上就为　10n10mn，再抹去　10n1，带上就剩0mn，即为所求。 设计Copy子程序 这个子程序完成在第二个１拷贝n个０的操作。 第1次被调用 开始ID：B０m-11q10n1 结束ID：B０m-11q50n10n 第i次被调用 开始ID：Bi０m-i1q10n10(i-1)n 结束ID：Bi０m-i1q50n10in 在拷贝时，每当将一个０变成２，就在末尾写个０。当0n变为2n时，就已在右边加了0n。再将2变为0n。 当前第39页\共有64页\编于星期五\5点 4.2.7 图灵机的组合 设计主ＴＭ M M= {q0,q6,q7,q8,q9,q10,q11,q12,q13},{0,1},{0,1,2,B},δ,q0, B, {q13}) 开始ID为q00m10n1，进入Copy入口ID为B0m-11q10n1，为此， δ(q0,0)=(q6,B,R) δ(q6,0)=(q6,0,R) δ(q6,1)=(q1,1,R) 从Copy结束时的ID，进入主TM的开始ID (B0m-11q50n10n├Bq00m-110n10n) δ(q5,0)=(q7,0,L) δ(q7,1)=(q8,1,L) δ(q8,0)=(q9,0,L) δ(q9,0)=(q9,0,L) δ(q9,B)=(q0,B,R) 善后处理：Bm1q50n10mn 当前第40页\共有64页\编于星期五\5点 4.2.8 枚举器 当前第41页\共有64页\编于星期五\5点 4.2.8 枚举器 定理4-6 一个语言是图灵可识别的，当且仅当有枚举器枚举它。 证明：首先证明如果有枚举器E枚举语言L，则存在图灵机M识别L。构造M如下： 对于任意输入串w，运行E。每当E输出一个串时，与w比较，若相等，接受w，并停机。 显然，M接受在E输出序列中出现过的那些串。 现在证明若有图灵机M识别语言L，则有枚举器E枚举L。 设L={w1，w2，w3，…}，构造E如下： 对i=1,2,3,…执行如下步骤 （1）对w1，w2，w3