第四讲：图灵论题.pptVIP

* 图灵机举例 M4=“对于输入的 w： 1) 在最左端的带符号的顶上做个记号。如果此带符号是空白符，则接受。如果此符号是 #，则进行下一步。否则，拒绝。 2) 向右扫描下一个 #，并在其顶上做第二个记号。如果在遇到空白符之前没有遇到 #，则带上只有 x1 ，因此接受。 3) 通过来回移动，比较做了记号的 # 的右边的两个字符串，如果它们相等，则拒绝。 4) 将两个记号中右边的那个向右移到下一个 # 上。如果在碰到空白符之前没有遇到 #，则将左边的记号向右移到下一个 # 上，并且将右边记号移到后面的 # 上。如果这时右边记号还找不到 #，则所有的字符串都已经比较过了，因而接受。 5) 转到第 3 步继续执行。” * 主要内容 3.1 丘奇—图灵论题 3.1.1 图灵机的形式化定义 3.1.2 图灵机的例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.3 枚举器 3.2.4 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语 * 图灵机的变形 从不同的方面对 TM 进行扩充。 多带 TM 允许 TM 有多于一条的输入带。此时每条带上将有一个读头。 不确定的 TM 允许 TM 在某一状态下根据读入的符号选择地进行某一个动作：进入某个状态，在读头的当前位置印刷某个符号，将读头移向某个方向。 …… 它们与基本的 TM 等价。 在形式变化中保持不变的性质称为稳健性。 * 多带图灵机 多带图灵机 (multitape Turing Machine) 很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为： ?： Q×?k ? Q×?k×{L, R, S}k 此处 k 是带子的个数。表达式 ?( qi , a1 , a2 , …, ak ) = ( qj, b1, b2, …, bk , L, R, …, L) 指的是：若机器处于状态 qi ，读写头 1 到 k 所读的符号分别是 a1 到 ak ，则机器转移到状态 qj，各读写头分别写下符号 b1 到 bk，且按此式所指示的那样移动每个读写头。 * 多带图灵机 定理 3.8 每个多带图灵机等价于某一个单带图灵机 将一 个多带 TM M 转换为一个与之等价的单带 TM S，关健是怎样用 S 来模拟 M。 假设 M 有 k 个带子。 S 把此 k 个带子的信息都存储在它的唯一带子上，并以此来模拟 k 个带子的效果，它用一个新的符号 # 作为定界符，以分开不同带子的内容。除了带内容之外，S 还必须记录读写头的位置。为此，它在一个符号的顶上加个点，以此来标记读写头在其带上的位置。S 把它们想象为虚拟带子和虚拟读写头。像以前一样，加点的带符号应是已经加进带字母表的新符号。 * 多带图灵机 0 1 0 1 0 □ … M a a a □ … b a □ … # 0 1 0 1 0 # a a a # b a # □ … S * 多带图灵机 S = “对于输入 w=w1… wn： 1) S 在白己的带子上放入 #w1w2…wn#□ #□ # …#（上边没加点） 此格式表示了 M 的全部 k 个带子的内容。 2)为了模拟多带机的一步移动， S在其带子上从标记左端点的第一个 # 开始扫描，一直扫描到标记右端点的第 (k+1) 个 #。其目的是确定虚拟读写头下的符号。然后 S 进行第二次扫描，并根据 M 的转移函数指示的运行方式更新其带子。 3)任何时候，只要 S 将某个虚拟读写头向右移动到某个#上面，就意味着 M 已将自己相应的读写头移动到了其所在的带子中的空白区域上，即以前没有读过的区域上。因此，S在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个格。然后再像以前一样继续模拟。” * 多带图灵机 推论 3.9 一个语言是图灵可识别的，当且仅当存在多带图 灵机识别它。 一个图灵可识别语言可由一个普通的(单带)图灵机识别，这个普通图灵机是多带图灵机的一个特例，这就证明了此推论的一个方向。另一个方向可由定理3.8得证。 * 非确定型图灵机 非确定型图灵机的有如其名，在计算的过程中，机器可以在多种可能性动作中选择一种继续进行。它的转移函数具有如下形式： ? : Q×?? P(Q×?×{L, R}） 其计算是一棵树，不同分支对应着机器的不同可能性。 * 非确定型图灵机 定理 3.10 每个非确定型图灵机都等价于某一个确定型图灵 机