有限自动机理论CH6.ppt

第六章图灵机 接收能力最强的自动机图灵机 即TuringM TM 由A Turing于1936年提出 TM是可计算性的数学模型研究可计算性 可计算的特点是有穷 离散 机械执行 停机 为计算机的发展奠定了理论基础 图灵机可以模拟现代的计算机的计算能力 使用图灵机可以解决计算机程序的可计算问题 图灵机的构造技术类似于计算机的编程 设计指令 技术 6 1图灵机的基本模型 6 1 1图灵机的定义 图灵机的物理模型 a1 a2 a3 aj an an 1 FSC 一个有限状态控制器 FSC 一个外部的存储设备可以向右扩展的无限长度带带上具有左端点 使用 表示图灵机直接扫描输入带上左端点右边的第一个符号 带分解为单元 每个单元可以为空 B 或存放字母表上的字母符号有限状态控制器通过一个读 写头与带进行耦合 带的右边用B标记带的右期间 在某个时刻 有限状态控制器处于某个状态 读 写头将扫描带上的一个单元依照状态和扫描到的带上符号 图灵机将有一个动作如下 有限状态控制器的状态进行改变 把刚刚扫描过的单元上符号擦除掉 并印刷上一个新的符号 有可能印刷上与原来符号相同的符号 读 写头向左或者向右移动一个单元 或者读 写头不移动 五元式描述动作 其中 x W 图灵机处于状态q 扫描到符号x 则状态变换为q 印刷上新的符号W 读 写头向左 或向右或不移动 例6 1用TM接收 语言 a2n n 0 图灵机带上符号串为 aaa aaaB图灵机初始处于状态even 将要扫描第一个a 则 可省略 若带上a的个数为偶数 则图灵机经过多个动作后 处于接收状态accept 若带上a的个数为奇数 根据 图灵机将不会停机 可以永远继续下去这与其它的自动机不同 即图灵机可能会导致永不停止的计算 例6 2语言为 a2n n 0 定义6 1图灵机是一个五元式 TM Q q0 q Q是有限状态集合 是带上字母表的有限集合 B A 的增广集合 即输入带上符号的集合 q0 Q 是开始状态q Q 是接收状态 Q Q L R N 对于任意的 q x Q q x q W L R N 将 记为一般形式 或图灵机是一个七元组 TM Q q0 B F F Q终止状态集合 是带符号集合 B 称为空白符 Q Q R L N 定义6 2图灵机的格局ID w1qw2 w1是读 写头左边带上的符号串q是图灵机当前所处的状态w2是还未扫描到的带上的符号串 Q 图灵机在格局w1qw2时停机若w1qw2 w1qxw对于无定义 q x 定义6 3格局的转换 若M在w1qw2上不停机 则如下定义格局的转换 某个时刻 图灵机处于格局w1qw2 r1yqxr2 其中 r1y w1 若w1 则y B r1 xr2 w2 若w2 则r2 x B 使用 表示图灵机的格局转换 若 q x q x L 则r1yqxr2 若 q x q x N 则r1yqxr2 若 q x q x R 则r1yqxr2 r1q yx r2 r1yq x r2 r1yx q r2 使用 代表格局的多次变换使用 代表格局的任意次变换 定义6 4 图灵机M Q q0 q 在字母表 上接收的语言为L M 则L M w 存在w1 w2 有 q0w w1q w2 定义6 5完全的图灵机 如果图灵机对于一切输入串都能够停机 完全的图灵机 完全的图灵机接收的语言L称为递归语言 图灵可判定语言 6 1 2图灵机的构造 例 接收仅有一个1的0 1串TM q0 q1 q2 0 1 q0 q2 0 1 B q1 B 例6 4构造图灵机 接收语言 anbn n 0 思路 当图灵机遇到a时 将a改写为 向右寻找b 找到b 将b改写为 再向左找a 直到所有a都找完 向左找的a是整个a串最左边的a 指令为 读到一个a 用 代替它 向右找b 处于状态del b 扫描到b 用 代替它 向左寻找a 从 重复循环 最右的a seek a状态时 没有再发现a 都已被 所代替 还需要检查是否所有的b都已经被扫描过 问题 该图灵机能接收anbn的所有串但该图灵机也能接收aababb等原因 使用 代表已扫描的a和b没有保证a和b的顺序 为了区别原来的字母a和b使用 和 分别代替字母a和b当a和b都识别后 带上的串为 B 例6 5修改上例 读到一个a 用 代替它 向右寻找b 处于状态del b 扫描到b 用 代替它 向左寻找a 从 重复循环 在seek a状态时 没有再发现a 都已经被 所代替 需检查是否所有的b都已经被扫描过还必须注意 与 的顺序 例6 6 anbn n 0 的第二种算法 当图灵机遇到a时 将a改写为 向右寻找b 找到b 将b改写为 再向左找a 此时的a是整个a串最左边的a 直到所有a都找完 指令 读到一个a 用 代替它 向右寻找b 处于状态del b 扫描到b 用 代替 向左寻找a 从 重复循环 跳过a串 最右 最左a 在seek a状态时 没有再发现a 需检查是否所有的b都已经被扫描过 思考 比较对于相同的输入串 两种算法的图灵机的指令数量 每条指令的执行次数 总次数 能否给对图灵机的性能进行评价 例6 7 anbn n 0 第三种算法 思路 首先检查输入串是否为a b 的格式 如果不是 则拒绝该串如果是 检查a和b的个数是否相等 指令 扫描a 扫描b 开始检查a和b的个数是否相等 已经保证顺序 检查是否有多余的b 例6 8接收语言 anbncn n 0 TM Q start accept Q start del b del c seek a check1 check2 check3 accept a b c a b c B 指令 读到一个a 用 代替它 向右寻找b 处于状态del b时 扫描到b 用 代替它 向右寻找c 处于状态del c时 扫描到c 用 代替它 向左找a 从 开始又重复循环 在seek a状态时 没有再发现a 都已经被 所代替 还需要检查是否所有的b和c都已经被扫描过注意 和 的顺序 识别第一个 跳过剩余 类似地 图灵机接收语言 anbncn n 0 也有多种方法 思考 构造TM接收语言 aibjci j i j 0 构造TM接收语言 aibjci j i j 0 构造TM接收语言 wcwT w a b 6 2图灵机作为非负整数函数计算模型 设有k元函数f n1 n2 nK m如果TM接受输入串0n110n21 10nk而 输出 符号串0m 则称TM计算k元函数f 或称f为TM计算的函数 也称f是图灵可计算的 但当f n1 n2 nK 无定义时 TM没有适当的输出 自动机都具有识别语言的功能图灵机还具有 计算 功能可以规定非负整数的表示方法 从而实现非负整数的函数求值 使用 一进制 方式表示一个非负整数 即使用0m表示整数m 若需要计算f m n 则可以在输入带上存放0m10n形式的串图灵机将串改写为0f m n 的形式 即表示出计算f m n 的结果 加法图灵机 对于非负整数n m 计算n m 分析 图灵机输入0n10m需要输出0n m算法 将1改写为0 最后一个0改写为B 可能是1改写成的0 TM Q start accept Q start q1 q2 accept 0 1 0 1 B 指令 串为1或10m第1个0跳过剩余的0遇到1 改为0遇到B 向左找0最后的0改为B 注意 扫描1左边和右边的0的工作都由完成 整个串只允许一个1 例6 16构造TM 实现非负减法 真减法 m n m nm n 0m n 即全是B 或 思路1 带上字符串的形式为0m10n寻找1左边的0 删除1右边的0可能在寻找1左边的0时结束 m n 或者在删除1右边的0时结束 m n 1 扫描第1个0 2 原标记的1 3 将1后的第1个0变为1 后加的 strat 1 q2 B 4 向左找0读写头位置转 1 重复上述动作 m n 5 遇到最右边的B 表示1右边已没有0将1改写为B补写1个0 结束 m n 6 start将遇到第一个1将后面1改写为B将后面0改写为B结束此时 输入带上全为 表示 m n 在第 5 步开始时 输入带上的字符串形式为 BBB B000 011 11Bm n 1个n个左边B有n 1个 m n 根据TM的动作 在左边消除一个0 再去1的右边找0当发现1的右边已经没有0时 此时减法工作应该结束 m n 但左边多消除了一个0因此 第 5 步 在q4的的控制下除了将1改写为B外还应该将一个0补写回来 才能结束减法工作 m n 此时 输入带上的字符串形式为 BBB B000 0Bm n个 m n时 整个减法的结果应该为0输入带全为 B 特殊 m n 0 则串为1BB 结束 思路2自学 图灵机反复进行下面的工作 先用B替换1左边领头的0向右搜寻1右边的第一个0 并将这个0替换为X 然后左移到B 重新开始循环 退出循环的条件有两种 1 1的左边找不到0 说明m n输出0 应将所有非B符号改写为B 2 1的右边找不到0 说明m n输出0m n 应将1换为0 将X换为B 状态转换函数为 1 开始循环 用B替换1左边领头的0 2 向右搜寻1 3 向右寻1右边的第一个0 并将这个0替换为X 4 左移到B 重新开始循环 5 符合退出条件1 即1的左边找不到0 用状态q4向右扫描将所有非B符号改写为B 并进入终止状态q6 6 符合退出条件2 即1的右边找不到0 用状态q5向左扫描将所有X改写为B 将1替换为0 并进入终态q6 1换为0 6 3图灵机的构造技术 构造TM 就相当于编写一个程序 指令或规则的组合 本节介绍的图灵机的一些构造技术 这些技术具有一般性 对于图灵机的构造 程序设计 具有较大的意义 6 3 1图灵机的存储技术 例6 12构造TM 识别字母表 a b c 上的语言L 每个字符串的第一个符号在该串中仅仅出现一次 思路 要求 第一个符号仅仅出现一次图灵机可以 记住 输入带上的第一个符号 a或b或者c 使用二元式表示状态第一个分量仍然表示原来的状态 第二个分量存储带上的第一个符号 q a q b 和 q c 分别代表输入串的第一个符号为a b和c的状态 1 扫描第一个符号 并存储 2 第一个符号是a 3 第一个符号是b 4 第一个符号是c 结束 5 遇到最右的B 接收该串 注意 直接运用规则 1 和 5 可以接收仅仅只有一个符号的输入串 例6 13构造TM 识别 a b c 上的语言L 每个句子的最后一个符号在该串中仅仅出现一次 思路1 最后个符号仅仅出现一次TM先将读 写头移动到带的最后 记住 输入带上的最后一个符号向左扫描输入带上的其他符号与最后一个符号进行比较 x a b c 1 将读 写头移动到带的最后 start B 2 存储最后的符号 向左扫描输入带上的其他符号遇到 结束 思路2 TM需要存储已经出现过的符号为了识别输入带上的最后一个符号 图灵机还需要存储当前扫描的符号 以便确定最后一个符号 使用三元组表示单个状态 第一个分量仍然表示原来的状态 第二个分量是已经出现过的符号的串 ab ac或bc 第三个分量表示上一次扫描的符号 如 q ab a 代表输入带上的字符已经出现过a和b上一次扫描的符号为a 具体指令略 思考 构造TM 该语言的每个句子的 倒数 第n个符号在该串中仅仅出现K次 n 1 2 3 K 1 2 3 6 3 2图灵机的移动技术 在解决比较复杂的问题时TM需要将输入带上一组连续的非空符号左移或者右移若干个单元 使用n元式存储多个符号直到某个阶段再将这些符号印刷到需要的位置上 例6 14构造TM a b c 将输入串右移两个单元使用三元组 q a1 a2 表示状态q表示原来的状态 a1 a2可以代表a b c 设串长度 3 1 扫描第一个符号 并存储 2 扫描第二个符号 并存储 3 将a1放在a3位置 将a3存储 4 将倒数第二个符号放在右边空白单元 将最后一个符号存储在状态中 5 将最后一个符号放在带上 其中规则 3 需要重复多次使用 本例使用三元组表示特殊状态也可以使用二元组表示特殊状态如 q a1 a2 可以记为 q a1a2 n元组也可以表示为二元组 对带上符号进行移动 一般只是比较复杂的TM的识别任务中的一部分工作移动本身不会涉及到串的接收或拒绝问题复杂的TM可以继续从end move状态开始其他的工作 思考 构造TM 将整个输入串前两个符号删除 思路 将带上符号从右向左移动两个单元 例6 15构造TM 输入字母表为 0 1 在输入串的开始处添加子串10 略 例6 16构造TM a b c 将整个串包含的第一个abc子串删除 思路 存储技术寻找到第1个abc子串的位置将后面的符号向左移动三个单元 略 例6 18 构造TM 输入字母表为 0 1 要求M接收语言L 该语言的每个字符串包含且仅只能包含一个101子串 有且仅有一个101 不可以没有101子串 思路 当识别出第一个101后 检查输入带上剩余的串不能再包含10110101 TM Q start accept Q start q 0 q 1 q 10 check check 0 check 1 check 10 refuse accept 0 1 0 1 B 1 扫描第一符号空串 2 3 已经扫描到 1 等待可能的 0 4 已经扫描到 10 等待可能的 1 5 已扫描到101 检查串的剩余部分 6 7 8 的第2条指令与 9 可以省略 8 9 整个输入串中没有101 结束 10 整个输入串只有一个101 思考 构造TM 接收语言L 该语言的每个句子必须包含两个101 例6 19 构造TM 接收语言L 该语言的每个句子最多只能包含一个100子串 可以没有100子串 思路 接收1个100子串的所有串 接收没有100子串的所有串 例6 23构造TM 接收语言L 该语言的每个句子不包含子串100 思路 当识别出第一个100后 就拒绝 6 3 3图灵机扫描多个符号技术 略 6 3 4图灵机的多道技术 为了能够保存和处理更复杂的数据 可以将TM的输入带划分为若干道在各道上可以存放不同的符号 没有改变图灵机的基本模型 只是将带上符号当做一个向量的组合每个符号可以是一个K维向量 将输入带划分为K道 单带K道的图灵机 状态转换函数 一般形式为对于K道图灵机一次需要扫描一个符号的多道 思考 二进制的加法考查第3题 例6 24 构造图灵机 字母表为 a 接收语言L an n 0 且n为完全平方数 基本数学公式 n 1 2 n2 2n 1 思路 使用三道的图灵机第一道存放输入串 第二 三两道作为 运算器 使用 初始时 从i 0开始在第二道上放i2个a比较第一道与第二道上a的个数如果相等 就接收 不相等 则在第三道上设置 计算 出2 i 1个a 将第三道上的a加入到第二道上去 从而 在第二道上形成 i 1 2个a再与第一道上a的个数进行比较 初始i 0第2道a个数为02 aaa aBn个aBBB B02 0BBB B 第3道设置为2 0 1 aaa aBBBB B02aBB B2 0 1 第2道设置为12i 1 aaa aBaBB B12aBB B 第3道设置为2 1 1 aaa aBnaBB B12aaaB B2 1 1 第2道设置为22i 2 aaa aBnaaaaB B22aaaB B 第3道设置为2 2 1 aaa aBnaaaaB B22aaaaaB B2 2 1 第2道设置为32i 3 aaa aBnaaaaaaaaaB B32aaaaaB B 第3道设置为2 3 1 aaa aBnaaaaaaaaaB B32aaaaaaaB B2 3 1 第2道设置为42i 4 aaa aBnaaaaaaaaaaaaaaaaB B42aaaaaaaB B 上述动作一直重复下去 直到第一 二道上a的个数相等 则接收 或者第一 二道上a的个数不相等则拒绝该输入串 从i 2过渡i 3到时 图灵机输入带为 TM Q start accept Q start q1 q9 refuse accept a a B 1 对于两种特殊情况 n 0或者n 1 进行处理 2 i 0 准备工作在第三道上放一个a 3 计算 i 1 2其中 x y a B 将第 道的a复制第2道的a的后面 向左找复制标志b或 建立新标志 i 0 在第三道上放b为新标志 其中 x a B 在第二道上复制一个a 其中 x a B 4 计算2 i 1 1 为下次做准备 实际上 在第3道每次增加2个a 仅当输入串为a4和a9时 i2 2 i 其中 x y a B 5 比较第一道和第二道上a的个数 第一道上a的已经查完 其中 x a B 仅当输入串为a4和a9时 i2小于2i 第二道的a少于第一道的a 继续扫描 6 拒绝情况 可省略 第二道的a多于第一道上的a 停机第一道上已经没有a 停机 6 3 5图灵机的查讫技术 在TM的工作中 有时需要对已经扫描过的符号进行检查 为了区分带上的某个符号是否已经检查过 可以使用查讫符号 进行标记需要使用多道技术存储查讫符号 初始时 所有带上符号的查讫标记都标记为 B 例6 25构造TM L M w2w w 0 1 分析 依次比较2前后的符号将带分成两条道第一条道上存放输入符号串第二条道上存放检查标记 初始 输入带上的符号情况为 a1a2 an2b1b2 bmB BB BBBB BB 比较时 使用存储技术 将符号 2 前面的待比较符号存储 再与2后面相应位置的符号进行比较 某个时刻 输入带上的符号情况 a1a2 an2b1b2 bmB BB B BB M的初始状态为start令a 0或1 b 0或1 记录待比较符号 读头右移到2的后面 找到要比较的位置 比较后相同则继续 2个a必须同为0或1 读头左移到2前 读头左移过2后有两种情况 未比较完已比较完 未比较完时读头左移到待比较符号 已比较完则看右边是否处理完 6 3 5图灵机的子程序技术 与通常的程序设计技术相似子程序的思想在TM的构造中也是十分重要的技术 子程序技术的使用 可以将复杂的问题进行分解 化简 同时 也可以将TM的构造 模块化 TM的子程序技术的基本思想是将TM中需要重复使用的功能分解出来 作为一个子程序 完成整个功能的图灵机为M 作为主程序对待 完成某个特定功能的图灵机为M 即子程序作为某个小的图灵机 图灵机M 从状态q开始到一个固定的状态f结束状态q f是图灵机M的两个一般状态 当图灵机M进入状态q时 就启动M 相当于调用子程序 当M 进入状态f时就返回到M 相当于子程序结束 注意 图灵机M 中可以有多个状态但仅有两个状态 即M 的开始状态q和接收状态f 是与主程序的图灵机M共用的图灵机M 的其他状态是私有的 不能被主程序的图灵机M所使用 例6 26 构造TM 完成正整数的乘法运算 正整数的乘法运算的数学公式 m n 1 1 1 nm个1 使用TM实现正整数的乘法运算TM的输入带上存放串0m10n 运算后 使得带上的串变为0m n形式 TM处理该问题的最一般的方法为 当从1的左边消去一个0后 应该在0n的后面增加n个0 补1作为分隔标记 当1左边的所有的0 共有m个 消完后 再消去多余的符号 两个1和原来的0n 就得到了0m n形式 在0n后面添加n个0的过程是重复的 可以使用子程序技术 在某个时刻 TM输入带上的符号为 Bh0m h10n10h n完成 1 1 1 1 nh个 M的状态函数分为3部分 1 初始化 将第一个0变为B 并在最后一个0后面设置标记为1该标记表明了增加0的开始位置使得增加的0在第二个1的后面 并将读 写头移动到n个0中的第一个处 则格局变换为 q00m10n B0m 11q10n1 注意 此时 只是消去了第一个0设置标记1 但还没有在后面增加0即将扫描原来0n的第一个0 2 主控程序 初始化后 状态变为q1 q1相当于子程序图灵机的开始状态 进入子程序 将n个0增加到第二个1的后面 当退出子程序时 状态为q5 q5也就是子程序图灵机的结束状态 此时需要将读 写头移动到前面m个0中剩余0的第一个处并将这个0改为B 准备进入下次循环 对应的格局转换为 Bhq00m h10n10 h 1 n Bh0m h1q10n10 h 1 n 进入子程序 Bh0m h1q50n10h n Bh 1q00m h 110n10h n 当找不到前面m个0中剩余的0时 表示乘法计算工作已经结束 需要消去多余的符号 两个1和原来的0n 得到最后的结果串 对应的格局转换Bmq810n10m n Bm n 1 1q140m n其中 状态q14是接收状态 3 子程序 将n个0增加到原来0n的后面 子程序TM从它的开始状态q1启动 进入接收状态q5时完成一次工作 并返回到主控程序 进入图灵机子程序时 输入带上符号串的形式情况及读 写头位置为 Bh0m h1000 010 h 1 nq1读 写头指向0n的第一个0 子程序对应的格局转换为 Bh0m h1q10n10 h 1 n Bh0m h1q50n10h n 整个图灵机的格局转换情况 初始化 q00m10n B0m 11q10n1 主程序和子程序 Bhq00m h10n10 h 1 n Bh0m h1q10n10 h 1 n主程序消除0Bh0m h1q10n10 h 1 n Bh0m h1q50n10h n子程序增加0nBh0m h1q50n10h n Bh 1q00m h 110n10h n主程序消除0 Bmq810n10m n Bm n 1 1q140m n主程序消除多余符号 初始化 不止执行一次 在最后增加标记1 控制在串的最后只能放一个1此时 将扫描原来0n的第一个0 子程序 将0标记为2 以方便复制0n向右寻找B遇到标记1 第二个1 复制一个0 向左寻找0n中剩余的0 寻找标记2 准备复制下一个0n个0都已复制 将2恢复为0子程序结束 读 写头仍然在0n的第一个0处 主程序 上一次循环结束 本次循环开始 m个0都消完 循环结束 消去多余串10n1 此时 图灵机带上的符号形式为 Bm n 1 10mn 图灵机共有15个状态 其中 子程序图灵机使用了5个状态 q1 q2 q3 q4 q5主程序图灵机使用了12个状态 q0 q1 q5 q6 q7 q8 q9 q10 q11 q12 q13 q14 教学活动结束 谢谢 丘奇 图灵论题 在研究可计算性问题时一种观点认为 对于任何输入 算法都应该能够终止否则 只能称其为 计算 过程 根据这个观点 对于某些输入不能够停机的图灵机就不能够称为算法 也就是说 如果某个图灵机使用永不停机的方式表示对某个输入串不能够接收的话 该图灵机就不是算法 而只有对任何输入都必定停机的图灵机 才称为算法 或者说 接收递归语言的图灵机是算法 接收递归可枚举语言的图灵机不一定是算法 另一种观点则忽略停机问题 从而扩大了可计算问题的范围 丘奇 图灵论点是递归论中最重要的基本结论 递归论又称可计算性理论 它是研究计算的一般性质的数学理论 其中心问题是 计算的本质是什么 哪些问题是可计算的 哪些问题是不可计算的 不可解的程度如何 这些问题经过长期的探索 终于在本世纪30年代由于递归论的建立而得到了确切地解决 递归论的建立首先得益于哥德尔等人关于原始递归函数的提出 所谓原始递归函数是指由初始函数出发 经过有限次的代入与原始递归式而做出的函数 1934年哥德尔在他人的启示下 又提出了一般递归函数的概念 一般递归函数就是由初始函数出发 经过有穷次使用代入 原始递归式和m算子而做成的可定义函数 同时 数学家丘奇 克林也提出了一类可计算的叫做l可定义的函数 事隔不久 丘奇 克林就分别证明了l可定义函数正好就是一般递归函数 即这两类可计算函数是等价的 一致的 在这一有力的证据基础之上 丘奇公开发表了他早在1934年就孕育过的一个论点即著名的丘奇论点 每个能行可计算的函数是一般递归的 也就在1936年 数学家图灵定义了另一类可计算函数 图灵可计算函数 并且提出了图灵论点 能行可计算的函数都是用图灵机可计算的函数 一年后 图灵进一步证明了图灵可计算函数与l可定义函数是等价的 当然也和一般递归函数是等价的 于是这三类可计算函数实际上就是一种 这样一来 丘奇论点和图灵论点也就是一回事了 现统称为丘奇 图灵论点 至此 人们便把直观的能行可计算函数归结为一般递归函数了 对可计算性的实质有了清楚的认识 丘奇 图灵论题 又称为丘奇假说 对于任何可以用有效算法解决的问题 都存在解决此问题的图灵机 对于计算机科学 丘奇 图灵论点的意义是很直接的 它明确刻画了计算机的本质或计算机的计算能力 确定了计算机只能计算一般递归函数 对于一般递归函数以外的函数 计算机是无法计算的 可以说 递归性是使用计算机的前提 丘奇 图灵论点常常又被说成 凡可计算的函数都可用计算机计算 当然 这是从理论意义上来讲的 从现实意义上讲 计算机还有一个现实可计算性的问题 不过这是由另一门学科 计算复杂性理论来研究的 描述算法有三种基本方式 形式描述 实现描述和高水平描述 形式描述需要详细给出图灵机的状态定义 转换函数的定义 是最详细程度的算法描述 实现描述通常使用自然语言来描述图灵机的动作 如读 写头的移动 怎样存储数据等 不需要给出具体的状态转换函数的描述 高水平描述采用自然语言描述 忽略了图灵机的实现模型 即通常意义上的算法描述 6 5通用图灵机 图灵机是一个算法的实现装置 直观地 一台通用的计算机 如果不受存储空间和运行时间的限制的话 它应该能够实现所有的有效算法 按照丘奇 图灵论题 图灵机应该是现代计算机的形式化的模型 6 4图灵机变型 略 上面介绍了最基本的图灵机极其图灵机的构造技术 本节从不同的方面对图灵机进行扩充 包括双向无穷带图灵机 多带多读写头图灵机 不确定图灵机和多维图灵机等 为了区别扩展的图灵机 上面介绍的单向无穷带图灵机 称为基本图灵机 与基本的图灵机相比 它们都在不同的方面进行了扩展 但它们仍然与基本的图灵机是等价的 对基本的图灵机进行扩展 使得构造复杂的图灵机变得更加简便和容易 由于这些扩展实际上都是技术上的一些改进 而且它们的基本描述相对都比较复杂 在本书中 将致力于基本思想和基本方法的介绍 而忽略那些比较烦琐的描述 包括一些形式化的描述 这与本书前面的较为严格的论述不同 但是 根据基本思想和基本方法的介绍 读者较容易给出相应的形式化的描述和严格的证明 只不过这些形式化的描述和严格的证明 比较烦琐而已 6 4 1双向无穷带图灵机基本的图灵机的模型中 输入带上规定有左端点 所以 对于基本的图灵机 读 写头是不能够向左移动出该左端点的 对基本图灵机取消左端点的限制 得到双向无穷带图灵机 双向无穷带图灵机的输入带向左和向右都是无限的 输入带上所有空单元 包括左边和右边 全部标记为B 双向无穷带图灵机 读写头可以向左或向右任意移动 其他定义与基本图灵机的一致 定理6 2如果语言L能够被一个双向无穷带图灵机所接收 则该语言L也能够被一个单向无穷带图灵机 即基本图灵机 所接收 6 4 2多带多读 写头图灵机基本图灵机的另一个重要的扩展是双向多带多读 写头图灵机 这种双向的多输入带图灵机具有多条双向的无穷输入带 每一个输入带都有自己的读 写头 在每一个动作中 图灵机根据当前的状态以及每个读 写头正在扫描的带上符号确定图灵机的下一个状态 并且各个读 写头可以相互独立地向各自希望的方向进行移动 双向多带多读 写头图灵机简称为多带图灵机 multi tapeTuringmachine 将具有K条输入带的图灵机简称为K带图灵机 K tapeTuringmachine 多带图灵机的一个动作可以描述为 1 改变图灵机当前的状态 2 在各自的输入带上印刷一个符号 3 各个读 写头向各自希望的方向进行移动 K带图灵机的状态转换函数的形式为 p X1 X2 X3 Xk q Y1 D1 Y2 D2 Y3 D3 Yk Dk 定理6 3 多带图灵机与基本图灵机等价 证明 由于基本图灵机是多带图灵机的一个特例 所以 只需要证明 对于任意一个多带图灵机 都有一个与之等价的基本图灵机 略 6 4 3不确定图灵机 对于前面介绍的图灵机是一个五元式 TM Q q0 q 其中 是Q Q L R N 的状态转换函数 q x q W L R N 称该图灵机是确定的图灵机 对于一个给定的状态和读入符号 确定的图灵机只能有一种可选动作 确定有限状态自动机DFA可以向非确定有限状态自动机NFA的进行扩展 类似地 确定的图灵机也能够扩展为非确定的图灵机 定义6 7 图灵机M称为不确定的图灵机 或非确定的图灵机 除状态转换函数 的定义外 它的其余部分的定义同确定的图灵机 即对于某个状态q和扫描到的带上符号x 图灵机可能有多个动作 即M的状态转换函数 可能将Q 映射到Q L R N 的一个子集上 不确定的图灵机是一个五元式 TM Q q0 q 其中 Q是有限状态集合 是带上字母表的有限集合 用 U B 代表 的增广集合 q0 Q 是开始状态 q Q 是接收状态 是Q 2Q L R N 的状态转换函数 即对于任意的 q X Q q X q1 Y1 D1 q2 Y2 D2 qn Yn Dn 定义6 8 不确定图灵机M Q q0 q 在字母表 上接收的语言为L M 则L M w w 且存在w1 w2 有q0w w1q w2 对于不确定图灵机M 一方面可以认为 对于给定的输入串 M能够自动地选择一系列正确的动作 使得M能够最终进入接收状态 即不确定的图灵机M具有具有一定的 智能 另一方面 由于处理一个输入串的所有可能的动作系列都是可以逐个列举的 所以 对于任意的输入串 可以让不确定的图灵机M逐一地按照当前列举出的动作系列去处理该输入串 如果该输入串是不确定图灵机M所能够识别的串 即该输入串是不确定图灵机M接收语言的句子 则M最终能够执行接收该输入串的动作系列 不确定图灵机与确定图灵机的等价性证明就是基于这一思想的 定理6 4 若语言L能被不确定的图灵机所识别 则存在确定的图灵机M 有L M L 证明 需要证明 对于任意一个不确定的图灵机 都存在一个与之等价的确定的基本图灵机 定理6 5不确定的图灵机和确定的图灵机是等价的 证明 略 6 4 4多维图灵机前面接触过的图灵机的输入带都是一维的 也就是说 图灵机的输入带要么是只可以向右无限延长的 要么是只可以向左或向右无限延长的 因而 图灵机的读 写头只能够向前或向后进行移动 现在 将图灵机的输入带扩展为多维的 这种图灵机的读 写头可以沿着多个维移动 该图灵机称为多维图灵机 multi demensionalTuringmachine 如果图灵机的读 写头可以沿着k维移动 该图灵机称为k维图灵机 k demensionalTuringmachine k维图灵机可以转换为一维图灵机 6 4 5其他图灵机1多头图灵机多头图灵机 multi headTuringmachine 是指图灵机只有一条输入带 但有多个读 写头 多头图灵机的多个读 写头 统一地受图灵机的状态控制器的控制 多头图灵机根据当前的状态和多个读 写头当前扫描的多个字符 确定当前多头图灵机的一个动作 在多头图灵机的一个动作中 各个读 写头在输入带上所印刷的新符号和所移动的方向都可以是相互独立的 如果多头图灵机有K个读 写头 该图灵机称为k头图灵机 k headTuringmachine 定理6 6多头图灵机与基本图灵机等价 证明 2离线图灵机离线图灵机 off lineTuringmachine 是一种多带图灵机 但对于其中一条输入带 只能读 不能印刷上符号 即不能写 通常使用符号 和 标记离线图灵机的只读输入带的左 右端点 只允许离线图灵机的读 写头在 和 标记的区域内来回进行移动 离线图灵机实际上是多带图灵机的一个特例 如果只允许离线图灵机的读 写头从左向右进行移动 称这种离线图灵机为在线图灵机 on lineTuringmachine 虽然离线图灵机是多带图灵机的一个特例 但离线图灵机却能够模拟任何一个图灵机 定理6 7离线图灵机与基本图灵机等价 证明 对于基本图灵机M 构造离线图灵机M 模拟M 最简单的方法是让离线图灵机M 比基本图灵机M多一条输入带 用以复制基本图灵机的输入串 然后将该输入带当作是基本图灵机的输入带 模拟基本图灵机进行相应的处理 具体证明过程略 3作为枚举器的图灵机图灵机是递归可枚举语言的识别器和非负整函数的计算器 出此之外 图灵机还可以作为语言的产生模型 产生语言的图灵机称为作为枚举器的图灵机 是一个特殊的多带 多头 的图灵机 其中一个带专门作为输出带 并且规定 一旦一个字符被印刷在输出带上 就不能再被更改 如果输出带的读 写头的正常移动方向是向右的话 则输出带的读 写头不允许向左移动 基本的图灵机每次启动后 只处理输入带的一个输入串 即对于多个串 需要多次启动 而作为枚举器的图灵机 在启动之后 在输出带上将产生相应语言的每一个句子 为了区别每个句子 每次产生一个句子 就在该句子后面印刷一个分隔符号 如 注意 如果作为枚举器的图灵机产生的语言是一个无穷的语言 则作为枚举器的图灵机将永不停机 4 多栈机下推自动机实际上相当于非确定的多带图灵机 具有一条只读输入带和一条存储带 模拟堆栈 多栈机 multi stackmachine 具有一条只读输入带 和多条模拟堆栈的存储带 输入带上的读 写头不能够向左移动 存储带上可以印刷上规定的符号 并且存储带上的读 写头可以向左或向右进行移动 需要注意的是 存储带上的读 写头在向左移动时 必须在当前扫描的带单元中印刷上空白符号B 因此 存储带上的读 写头在向左移动时 该读 写头的右部全是空白符号B 将当前的单元作为了栈顶 另外 存储带上的读 写头在向右移动时 一般情况下 应该在当前扫描的带单元印刷上一个非空白符号 在特殊情况下 也可以印刷上一个空白B 如下面介绍的计数机图灵机 一个确定的双栈机 doublestackmachine 是一个确定的图灵机 具有一条只读输入带和两条模拟堆栈的存储带 存储带上的读 写头向左移动时 只能印刷上空白符号B 定理6 8一个任意的单带图灵机可以被一个确定的双栈机模拟 5 计数机计数机 countermachine 是一种离线图灵机 具有一条只读输入带 和多条用于计数的单向无穷带 存储带 用带上读头到最左边符号的距离 即单元的个数 表示所计的数 一个具有n条用于计数的带的计数机称为n计数机 用于计数的单向无穷带上只能有两种字符 一个为相当于作为栈底符号的Z 该字符也当作是记数带的首字符 它仅仅出现在记数带的最左端 另一个就是空白字符B 一条记数带上所记的数就是该记数带从Z开始到该记数带的读 写头当前位置所包括的空白符号符号B的个数 定理6 9一个任意的图灵机可以被一个记数机模拟 证明 略 6丘奇 图灵论题与随机存取机在研究可计算性问题时 一种观点认为 对于任何的输入 算法都应该能够终止 否则 只能称其为 计算 过程 根据这个观点 对于某些输入不能够停机的图灵机就不能够称为算法 也就是说 如果某个图灵机使用永不停机的方式表示对某个输入串不能够接收的话 该图灵机就不是算法 而只有对任何输入都必定停机的图灵机 才称为算法 或者说 接收递归语言的图灵机是算法 接收递归可枚举语言的图灵机不一定是算法 另一种观点则忽略停机问题 从而扩大了可计算问题的范围 1934年 丘奇使用称为 演算的记号系统来定义算法 1936年图灵使用计算模型 图灵机来描述 定义 算法 丘奇 图灵论题 又称为丘奇假说 对于任何可以用有效算法解决的问题 都存在解决此问题的图灵机 该论题还没有被严格的证明 对于计算机科学 丘奇 图灵论点的意义是很直接的 它明确刻画了计算机的本质或计算机的计算能力 确定了计算机只能计算一般递归函数 对于一般递归函数以外的函数 计算机是无法计算的 可以说 递归性是使用计算机的前提 因此 丘奇 图灵论点常常又被说成 凡可计算的函数都可用计算机计算 当然 这是从理论意义上来讲的 从现实意义上讲 计算机还有一个现实可计算性的问题 不过这是由另一门学科 计算复杂性理论来研究的 需要说明的是 丘奇 图灵论点并不象哥德尔不完备性定理那样能给出一个严格的数学证明 因为这一论点原本就不是一条定理 其中包含了一个数学上意义不明确的概念 能行可计算 即一面是直观的日常概念 另一面是明确的数学概念 一般递归函数 要证明二者是一致的 这是不可能的 后来人们实际上是把这一论点看作是对直观概念能行可计算的数学定义 既然是对一个不明确的概念给以明确的定义 这就无所谓正确与否 因此用不着证明也无法证明 因为 只能列出算法的有限性 机械可执行性 确定性 终止性等特征 即有效算法说明的可解性概念是非形式化的 不严格的 而图灵机的概念却是形式化的和严格的 但是 图灵机作为人们普遍接受的计算模型 使得将算法集中在可以用图灵机描述的计算上 因此 可以认为 可计算问题可以等同于图灵机的可计算问题 丘奇 图灵论点是递归论中最重要的基本结论 递归论又称可计算性理论 它是研究计算的一般性质的数学理论 其中心问题是 计算的本质是什么 哪些问题是可计算的 哪些问题是不可计算的 不可解的程度如何 这些问题经过长期的探索 终于在本世纪30年代由于递归论的建立而得到了确切地解决 递归论的建立首先得益于哥德尔等人关于原始递归函数的提出 所谓原始递归函数是指由初始函数出发 经过有限次的代入与原始递归式而做出的函数 1934年哥德尔在他人的启示下 又提出了一般递归函数的概念 一般递归函数就是由初始函数出发 经过有穷次使用代入 原始递归式和m算子而做成的可定义函数 同时 数学家丘奇 克林也提出了一类可计算的叫做l可定义的函数 事隔不久 丘奇 克林就分别证明了l可定义函数正好就是一般递归函数 即这两类可计算函数是等价的 一致的 在这一有力的证据基础之上 丘奇公开发表了他早在1934年就孕育过的一个论点 即著名的丘奇论点 每个能行地可计算的函数都是一般递归的 也就在1936年 数学家图灵定义了另一类可计算函数 图灵可计算函数 并且提出了图灵论点 能行可计算的函数都是用图灵机可计算的函数 一年后 图灵进一步证明了图灵可计算函数与l可定义函数是等价的 当然也和一般递归函数是等价的 于是这三类可计算函数实际上就是一种 这样一来 丘奇论点和图灵论点也就是一回事了 现统称为丘奇 图灵论点 至此 人们便把直观的能行可计算函数归结为一般递归函数了 从而对可计算性的实质有了清楚的认识 随机存取机 randomaccessmachine RAM 是更接近现代数字计算机的 图灵机 模型 随机存取机含有无穷多个存储单元 这些存储单元按照0 1 2 进行编号 每个存储单元可以存放一个任意整数 随机存取机还包含有穷个能保存任意整数的算术寄存器 这些整数可以译码成通常的各类计算机指令 显然 如果选择一个适当的指令集合 随机存取机RAM就可以用来模拟任何的现代数字计算机 图灵机与随机存取机RAM具有相同的能力 定理 如果随机存取机RAM的基本指令都能够用图灵机来实现 那么 就可以用图灵机实现随机存取机RAM 证明 略 TM等同于各种存储指令的计算机系统 可以将TM用作算法定义的精确模型 描述算法有三种基本方式 形式描述 实现描述和高水平描述 形式描述需要详细给出图灵机的状态定义 转换函数的定义 是最详细程度的算法描述 实现描述通常使用自然语言来描述图灵机的动作 如读 写头的移动 怎样存储数据等 不需要给出具体的状态转换函数的描述 高水平描述采用自然语言描述 忽略了图灵机的实现模型 即通常意义上的算法描述 6 5通用图灵机 图灵机是一个算法的实现装置 直观地 一台通用的计算机 如果不受存储