计算理论第4章图灵机.ppt

1 第4章图灵机 许桂靖杨莹 2 Overview 图灵机 TuringMachine TM 是计算机的一种简单的数学模型 历史上 冯 诺曼计算机的产生就是由图灵机诱发的 丘奇 图灵论题 一切合理的计算模型都等同于图灵机 3 类型文法结构产生式形式限制条件 0短语结构文法 PhraseStructure 上下文有关文法 1A 2 1 2 1 2 1A 2 1ContextSensitive 1 2 CSG A 上下文无关文法A A 2ContextFree CFG 正右线性文法A xB C yA B C 3规文左线性文法A Bx C yx y T 法 4 Overview 0型语言 图灵机1型语言 CSL 线性界限自动机2型语言 CFL 下推自动机3型语言 正规集 有限自动机 5 Overview 图灵机所定义的语言类 递归可枚举集合图灵机所计算的整数函数类 部分递归函数以图灵机为模型 研究问题的可计算性 即确定该问题是可计算的 部分可计算的 还是不可计算的 6 Overview 4 1图灵机模型4 2图灵机的变化和组合4 3通用图灵机4 4图灵机可计算性 7 4 1图灵机模型 8 4 1图灵机模型 定义4 1图灵机M K q0 B F 其中K是有穷的状态集合 是所允许的带符号集合 B 是空白符 B 是输入字符集合 F K 是终止状态集合 q0 K 是初始状态 9 4 1图灵机模型 K K L R S 是图灵机的动作 状态转移 函数 这里L表示读头左移一格 R表示读头右移一格 S表示读头不动 q a p b z 表示状态q下读头所读符号为a时 状态转移为p 读头符号变为b 同时读头变化为z 10 4 1图灵机模型 定义4 2设当前带上字符串为x1x2 xn 当前状态为q 读头正在读xi 图灵机的瞬时描述ID为x1x2 xi 1qxi xn 11 4 1图灵机模型 定义4 3设当前的瞬时描述ID1 x1x2 xi 1qxi xn若有 q xi p y L 则图灵机瞬时描述变为ID2 x1x2 xi 2pxi 1yxi 1 xn 若有 q xi p y R 则图灵机瞬时描述变为ID2 x1x2 xi 1ypxi 1 xn 12 4 1图灵机模型 定义4 3瞬时描述ID1经过一步变为瞬时描述ID2 称ID1与ID2具有一步变化关系 表示为ID1 ID2若ID1经过n步变为ID2 n 0 即有ID1 ID ID2称ID1与ID2具有多步变化关系 简记为ID1 ID2 13 4 1图灵机模型 定义4 4对于图灵机M K q0 B F 定义图灵机接受的语言集L M 为L M w w u0 u v q qf u0 u v q K qf F q0w u0qB uqfv 14 4 1图灵机模型 例4 1 设计一个图灵机 使得L M 0n1n n 1 设计思路 在带上每当将一个0变为X 就把一个1变为Y 当将所有的0变为X时 恰将所有的1变为Y 这个串就是合法的 最后将X Y分别还原为0 1 15 4 1图灵机模型 16 4 1图灵机模型 例4 2 设计一个图灵机 使之接受L M wcw w a b 设计思路 在c左侧 从左至右逐一字符 用状态记下它并标志该符号为已处理符号 移至c右侧对应位置后 判断是否是相同符号 若相同 再返回c左侧循环 直至所有符号比较完毕 最后将标志符号修改回原符号 在设计时 特别注意用状态存贮符号的方法 这是图灵机设计的重要方法之一 17 4 1图灵机模型 18 4 1图灵机模型 例4 3 设计一个图灵机 计算自然数n的以2为底的对数 用一进制表示输入和输出值 an表示输入n bm表示输出m 设计思路 从左到右扫描带 把所碰到的a划掉一个 留一个 并将计数器加1 重复此过程 直至a不复存在 这里 用字符c表示划掉的字符 19 4 1图灵机模型 20 4 1图灵机模型 例4 4 设计一个图灵机 计算二个自然数m n的减法 设计时 整数n用0n表示 开始时 带上符号为0m10n 结束时 带上符号为0 每当在1的左边将一个0改变为B 就在1的右边将一个0改为1 若1的右边无0时 再将左边改为B的0恢复回来 m n若m nm n 0否则 21 4 1图灵机模型 R 22 4 1图灵机模型 例4 5 设计图灵机实现数字从一进制表示到二进制表示的转换 这个图灵机的设计可以仿例4 3 不同在于每次循环时 要保留除以2的余数作为当前二进制位的值 注意这里首先计算出的是二进制的低位值 所以要将结果不断右移以插入新生成的位 生成的结果是低位在右端 初始时 整数n用an表示 结束时 带上是0 1构成的二进制数 23 4 1图灵机模型 R 24 4 2图灵机的变化和组合 4 2 1双向无穷带图灵机4 2 2多带图灵机4 2 3非确定图灵机4 2 4多头图灵机4 2 5多维图灵机4 2 6离线图灵机4 2 7图灵机的组合4 2 8枚举器 25 4 2 1双向无穷带图灵机 定理4 1L被一个具有双向无穷带的图灵机识别 当且仅当它被一个单向无限带的图灵机识别 证明 单向无限TM模拟双向无限TM 采用多道技术 26 4 2 2多带图灵机 27 4 2 2多带图灵机 例4 6 设计一个二带图灵机 使得T M 0 1 这个问题的关键是比较字符串前后两个部分 为此 首先要对带上字符串计数 每二元素计数加1 按计数值将字符串分为前后两个部分 并将它们分别存放于不同带上 然后进行比较 28 4 2 2多带图灵机 29 4 2 2多带图灵机 例4 7 设计二带图灵机 实现二进制到一进制的转换 设这个图灵机为M7 其第一带用作输入带 第二带用作输出带 设计思路是从左到右扫描输入带上的二进制字符 并使用公式r 2 b生成输出带上一进制数 其中r是当前输出带上的一进制数 b是当前输入带上扫描的字符 这里的r 2就是将原输出带上的一进制数r复制一遍 例如 1001的一进制数计算过程 30 4 2 2多带图灵机 31 4 2 2多带图灵机 定理4 2如果一个语言L被一个多带图灵机接受 它就能被一个单带图灵机接受 32 4 2 3非确定图灵机 例4 8 下面的图灵机就是不确定图灵机 无向图G中 从a出发合法路径判定的不确定型图灵机 33 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 34 4 2 3非确定图灵机 定理4 3如果语言L被一个非确定图灵机M1接受 则L将被某个确定图灵机M2接受 35 4 2 4多头图灵机 一个k头图灵机有k个读头 一个控制器和一条带 读头由1到k编号 图灵机的一个动作由当前状态和被每个读头所扫描的符号 在一个动作中 每个读头独立地左移 右移或不动 定理4 4如果L被某个k个读头的图灵机接受 则它能被一个单头图灵机接受 36 4 2 5多维图灵机 多维图灵机具有通常的有限控制器 但带却由k维单元阵列组成 这里 在所有2k个方向上 k个轴 每轴正 负两个方向 都是无限的 根据状态和扫视的符号 该装置改变状态 打印一个新的符号 在2k个方向上移动它的读头 开始时 输入沿着一个轴排列 读头在输入的左端 37 4 2 6离线图灵机 定理4 5如果L被一个二维图灵机M1接受 那么L将被一个一维图灵机M2接受 38 4 2 7图灵机的组合 39 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 40 4 2 7图灵机的组合 设计主 MM 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 41 4 2 8枚举器 42 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 wi中的每一串 让M以其作为输入运行i步 2 若在这个计算中 M接受wj 则打印wj M接受w 它最终将出现在E的枚举打印中 事实上 它可能在E的列表在出现无限多次 因为每一次重复运行 M在每一个串上都从头开始运行 43 4 3通用图灵机 缓冲域带的最左面是标记符 的右边是 K 2个单元构成的缓冲 K 分别是状态集和字母集的元素数目 的描述字域缓冲区域右边紧接的是 的描述字dM 以 为开始标志 以 个 结束 对于转移函数 q a q a d 我们用五元组表示为 q a q a d 将顺序调整为 q a a d q dM就是由这样的五元组组成的序列 对于每个五元组中的状态和字符 我们用其序号的一进表示 其间用 分隔 五元组间用 个 分隔 例如 若有 q q 表示成上面定义的五元组是 q q 再用其序号表示为 2 0 2 0 3 在U2的带上表示为011101011101011110 的输入描述域 的描述字域的右边存放的是输入串的编码 用字母的序号表示该字母 并用 分隔 该域以 为起始标志 如输入为111 则该串表示为 110110110 44 4 3通用图灵机 UTMU2模拟 具体步骤如下 步0将读头置于描述字区域的开始符号 上 此时缓冲区域是 步1U2复写标记 或 后面的状态到缓冲域的初始位置 然后在其后面加一个辅助符号 读写头右移到符号 步2U2复写 后面的初始带模式到缓冲区部分 即在 之后 步3U2将 改为0 现缓冲区中包含当前状态和扫描的字母 步4对描述字域进行搜索 查看前两项匹配的元组 若所有的五元组都不匹配 则表明 停机 U2也停机 若找到一个匹配的五元组 标记 表示正在比较的状态或符号 45 4 3通用图灵机 步5 找到匹配的五元组 删去缓冲区的内容 并把标记 右移一个符号 使 处于该五元组的新符号的前面 步6用新符号代替标记 后面的符号 可能需扩充或压缩原输入描述域 U2将标记 右移至五元组的方向分量前 步7U2计数方向分量中 的个数 然后按要求向左或向右移动标记 若 向左离开了输入串 则U2停机 若 向右离开了输入串 U2必须添加一个表示下一个方格的新的 串 当前U2描述字域标记 后面不是结束状态 则转至步1 否则接受输入串并停机 46 4 3通用图灵机 47 4 3通用图灵机 对于任何一个图灵机M 都有一个确定的描述字dM 如在例4 10中dM 1010101101100101110111010111001101101101101 将它看作一个二进制数 实质上 它是一个整数 因此按这种表示 任何一个图灵机都和一个整数相对应 这个整数 称为图灵机的标记 48 4 4图灵可计算性 4 4 1图灵可计算性函数4 4 2图灵机的枚举定理4 4 3图灵机的计算限界 49 4 4 1图灵可计算性函数 定义4 5函数f x1 x2 xn 是部分图灵可计算的 若有一图灵程序P 使得 P x1 x2 xn f x1 x2 xn 其中 P x1 x2 xn 是P对应的函数 表示若有定义 则值相等 否则 均无定义 50 4 4 1图灵可计算性函数 定义4 6函数f x1 x2 xn 是全函数 若它对一切x1 x2 xn都有定义 定义4 7函数f x1 x2 xn 是图灵可计算函数 若它是部分图灵可计算的而且是全函数 51 4 4 1图灵可计算性函数 52 4 4 1图灵可计算性函数 定理4 7设g1 g2 gm是n元图灵可计算函数 h是m元图灵可计算函数 则复合函数f h g1 g2 gm 也是图灵可计算的 53 4 4 2图灵机的枚举定理 1 图灵机的标记2 图灵可计算的重要定理定义4 8若z是一个图灵机M的标记 并且M计算部分函数g x1 x2 xn 则定义函数 n 为 n z x1 x2 xn g x1 x2 xn 54 4 4 2图灵机的枚举定理 定理4 8 枚举定理 对于每个自然数z 部分函数 n z x1 x2 xn 是 部分 图灵可计算函数 证明 它能枚举所有部分可计算函数 具体说就是 n 1元函数 n z x1 x2 xn 将枚举所有n元部分可计算函数 事实上 任给一个n元图灵可计算函数g x1 x2 xn 则必有一个图灵程序M对应它 令z是它的标记 我们有 n z x1 x2 xn g x1 x2 xn 55 4 4 2图灵机的枚举定理 定理4 9 迭代定理 对一切n 有图灵可计算函数 S n z x1 x2 xn 使得对一切m 有 n m z x1 x2 xn y1 y2 ym m S n z x1 x2 xn y1 y2 ym 证明 56 4 4 2图灵机的枚举定理 定义4 9计步谓词STP n 定义如下 STP n z x1 x2 xn M 描述字为z的图灵机程序T对于输入x1 x2 xn在M步内停机 其中 一步 定义为完成图灵机T的状态转移函数的一个变换 定理4 10 计步定理 对任意n 谓词STP n z x1 x2 xn M 是图灵可计算的 证明 57 4 4 3图灵机的计算限界 58 4 4 3图灵机的计算限界 1 域函数和停机函数 59 4 4 3图灵机的计算限界 60 4 4 3图灵机的计算限界 61 4 4 3图灵机的计算限界 62 4 4 3图灵机的计算限界 定理4 11对角线停机函数h不是图灵可计算的 证明 定理4 12空带停机函数h0不是图灵可计算的 其中 证明 63 4 4 3图灵机的计算限界 64 4 4 3图灵机的计算限界 2 完全性函数 65 4 5习题