丘奇-图灵论题.ppt

1 朴秀峰xfpiao 计算理论 第3章丘奇 图灵论题 2 引言 什么是计算 计算机的基本能力和局限性是什么 3 引言 计算机科学历史上关于概念的争论 什么是计算什么是操作系统基本上解决什么internet 什么是数据库什么是数据仓库还在争论什么是数据网格解决方法 给出大众能理解的代表 4 引言 计算机科学历史上关于概念的争论 解决的办法 给出一个代表什么是3的倍数 3N N 1 2 3 x xmod3 0 代表元 3什么是操作系统代表元 Windows Unix什么internet代表元 大众理解 Web IE什么是计算 多个模型 代表元 图灵机 或递归函数论 5 引言 在还没有计算机的时候 凭想象力把后来出现的把计算机的理论模型建立起来了 1936年想得如此周到 严密好像从高度文明的外星来的文化使者 6 引言 AlanM Turing 1912 1954 In1936 Turingintroducedhisabstractmodelforcomputationinhisarticle OnComputableNumbers Atthesametime AlonzoChurchpublishedsimilarideasandresults 殊途同归 Turingmodel成为理论计算科学的标准模型standardmodel 7 引言 图灵机 TuringMachine TM 是计算机的一种简单的数学模型 历史上 冯 诺曼计算机的产生就是由图灵机诱发的 丘奇 图灵论题 一切合理的计算模型都等同于图灵机 8 主要内容 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描述图灵机的术语 9 3 1图灵机 TurningMachine 非形式化描述 根据当前状态和字符xi 决定写移转三动作 写letter 有存储器 左或右移动转移状态可以作循环语句磁带相当于数组 可读写 这是增加的重要资源 每一步 读写头在单向无穷带上左右移动并读写 10 图灵机 stateq0 初始 带子上只有输入串w 其它地方是空的 开始状态q0 计算过程中读写头左右移动 机器内部状态改变 带子上内容重写 数组结构 11 图灵机 输出约定 三种输出 接受 拒绝 循环 非常规意义循环 不停机引出可判定性 12 图灵机与有限自动机 状态控制器 相似性 有限状态集区别 1 图灵机在带子上既能读也能写 2 图灵机的读写头既能向左也能向右移动 3 图灵机的带子是无限长的 4 图灵机进入拒绝和接受状体将立即停机 13 图灵机 考虑图灵机M1 它检查语言B w w w 0 1 的成员关系 即设计M1 使得如果输入是B的成员 它就接受 否则拒绝 M1 对于输入字符串w 1 在 两边对应的位置上来回移动 检查这些对应位置是否包含相同的符号 如不是 或者没有 则拒绝 为跟踪对应的符号 消去所有检查过的符号 2 当 左边的所有符号都被消去时 检查 右侧是否还有符号 如果有则拒绝 否则接受 14 M1的运行示意图 M Tapeheadmovestoright 15 M1的运行示意图 M Tapeheadmovestoleft 16 M1的运行示意图 M Tapeheadmovestoright 17 M1的运行示意图 M Tapeheadmovestoleft 18 M1的运行示意图 M Tapeheadmovestoright 19 M1的运行示意图 M Tapeheadmovestoleft 20 M1的运行示意图 M accept Tapeheadmovestoright 21 图灵机的形式化定义 定义3 1 图灵机是一个7元组 Q q0 qaccept qreject 1 Q是状态集 2 是输入字母表 不包括特殊空白符号 3 是带字母表 其中 并且 4 Q Q L R 是转移函数 5 q0是起始状态 6 qaccept是接受状态 7 qreject是拒绝状态 qaccept qreject 例如 q a r b L 22 图灵机的计算方式 开始时 M以最左边的n个带方格接收输入w w1w2 wn 带的其余部分保持空白 即填以空白符 读写头从最左边的带方格开始运行 注意 不含空字符 故出现在带上的第一个空字符表示输入的结束 M开始运行后 计算根据转移函数所描述的规则进行 如果M试图将读写头从带的最左端再向左移出 即使转移函数指示的是L 读写头也停在原地不动 计算一直持续到它进入接受状态或拒绝状态 此时停机 如果二者都不发生 则M将永远运行下去 23 图灵机的格局 图灵机计算过程中 当前状态 当前带内容和读写头当前位置组合在一起 称为图灵机的格局 对于状态q和带字母表 的两个字符串u和v 以uqv表示如下格局 当前状态是q 当前带上的内容是uv 读写头的当前位置是v的第一个符号 带上v的字符最后字符以后的符号都是空白符 例如 1011q701111 q7 24 图灵机计算方式的形式化 如果图灵机能合法地从格局C1一步进入C2 则称格局C1产生格局C2 设a b和c是 中的符号 u和v是 中字符串 qi和qj是状态 则uaqibv和uqjacv是两个格局 如果转移函数满足 qi b qj c L 则说uaqibv产生和uqjacv M在输入w上的起始格局是格局q0w 表示机器处于起始状态q0 并且读写头处于带子的最左端位置 在接受格局里 状态是qaccept 在拒绝格局里 状态是qreject 接受和拒绝状态都是停机状态 它们都不再产生新的格局 由于图灵机只在接受或拒绝状态下才停机 可以等价地将状态转移函数简化 Q Q L R 其中Q 是取消qaccept和qreject的Q 25 图灵机计算方式的形式化 图灵机M接受输入w 如果存在格局的序列Cl C2 Ck使得 1 Cl是M在输入w上的起始格局 2 每一个Ci产生Ci 1 3 Ck是接受格局 M接受的字符串的集合称为M的语言 或被M识别的语言 记为L M 26 图灵机的形式化定义 定义3 2 如果一个语言能被某一图灵机识别 则称该语言是图灵可识别的 Turningrecognizable 也称为递归可枚举语言 输入上运行一个TM时 可能出现三种结果 接受 拒绝 循环 仅仅指机器不停机 对于一个输入 TM有两种方式不接受它 一种拒绝状态一种进入循环问题 如何区别长计算与死循环 因此 我们喜欢对所有输入都停机的图灵机 永不循环 这种机器为判定器 因为它们总能决定是接受还是拒绝 27 图灵机的形式化定义 定义3 3 如果一个语言能被某一图灵机判定 则称该语言是图灵可判定的 Turningdecidable 也称为递归语言 可识别与可判定 1 可识别 接受该语言 2 可判定 可以不接受该语言 28 图灵机举例 例3 4描述TMM2 它识别的语言是所有由0组成 长度为2的方幂的字符串 即A n 0 M2 对于输入字符串w 1 从左往右扫描整个带子 隔一个字符消去一个0 2 如果在第1步之后 带子上只剩下唯一的一个0 则接受 3 如果在第1步之后 带子上包含不止一个0 并且0的个数是奇数 则拒绝 4 读写头返回至带子的最左端 5 转到第1步 29 图灵机举例 q1 q3 q4 qreject q2 qaccept q5 0 R Rx R R 0 x R x R x R L 0 R x R R 0 x R x L0 L R 30 图灵机的例子 每重复一次第1步 消去了一半个数的0 由于在第1步中 机器扫描了整个带子 故它能够知道它看到的0的个数是奇数还是偶数 如果是大于1的奇数 则输入中所含的0的个数不可能是2的方幂 此时机器就拒绝 但是 如果看到的0的个数是1 则输入中所含的0的个数肯定是2的方幂 此时机器就接受 M2 Q q1 qaccept qreject 的形式化描述 Q q1 q2 q3 q4 q5 qaccept qreject 0 0 x 将 描述成状态图开始 接受和拒绝状态分别是q1 qaccept qreject 31 图灵机举例 例3 5下面给出图灵机M1形式化描述M1 Q q1 qaccept qreject 它的判定语言是B w w w 0 1 Q q1 q2 q8 qaccept qreject 0 1 且 0 1 x 用状态图描述 开始 接受和拒绝状态分别是q1 qaccept qreject 32 图灵机M1的状态图 q1 q8 q3 q5 q6 q4 q7 qaccept q2 R x R R 0 1 R R x R 0 1 x L 0 1 L L x R 1 x L 1 x R 0 x L R 0 x R 0 1 R x R 第一步由q1到q7实现 第二步由其余状态实现 33 图灵机举例 例3 6图灵机M3做一些初等算术 它判定的语言C aibjck i j k 且i j k 1 M3 对于输入字符串w 1 从左往右扫描输入 确认输入具有形式a b c 否则拒绝 2 读写头回到带子的左端点 3 消去一个a 并向右扫描直到b出现 在b与c之间来回移动 成对地消去b和c 直到把所有的b都消去 如果c全消除后还有b 则拒绝 4 如果还有a未消去 则恢复所有已消去的b 再重复第3步 如果所有的a都已被消去 则检查所有的c是否都已被消去 如果是 则接受 否则拒绝 34 图灵机举例 例3 7图灵机M4解所谓的元素区分问题 给出一列 0 1 组成的字符串系列 字符串之间用符号 隔开 M4的任务是 如果此序列中的所有字符串都不同 则接受 此语言是 E x1 x2 xl xi 0 1 且对任意i j xi xj 机器M4将x1与x2到xl进行比较 然后将x2与x3到xl进行比较 依此类推 M4的非形式描述如下 35 图灵机举例 M4 对于输入的w 1 在最左端的带符号的顶上做个记号 如果此带符号是空白符 则接受 如果此符号是 则进行下一步 否则 拒绝 2 向右扫描下一个 并在其顶上做第二个记号 如果在遇到空白符之前没有遇到 则带上只有x1 因此接受 3 通过来回移动 比较做了记号的 的右边的两个字符串 如果它们相等 则拒绝 4 将两个记号中右边的那个向右移到下一个 上 如果在碰到空白符之前没有遇到 则将左边的记号向右移到下一个 上 并且将右边记号移到后面的 上 如果这时右边记号还找不到 则所有的字符串都已经比较过了 因而接受 5 转到第3步继续执行 36 主要内容 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描述图灵机的术语 37 图灵机的变形 从不同的方面对TM进行扩充 双向无穷带TM允许TM的输入带是无穷的 多带TM允许TM有多于一条的输入带 此时每条带上将有一个读头 不确定的TM允许TM在某一状态下根据读入的符号选择地进行某一个动作 进入某个状态 在读头的当前位置印刷某个符号 将读头移向某个方向 多维TM相当于在双向TM的基础上进一步扩充 允许TM的 输入带 向更多的方向延伸 枚举器允许图灵机带有打印机 它们与基本的TM等价 在形式变化中保持不变的性质称为稳健性 38 多带图灵机 多带图灵机 multitapeTuringMachine 很像普通图灵机 只是有多个带子 每个带子都有自己的读写头 用于读和写 开始时 输入出现在第一个带子上 其它的带子都是空白 转移函数改为允许多个带子同时进行读 写和移动读写头 其形式为 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 且按此式所指示的那样移动每个读写头 39 多带图灵机 将一个多带TMM转换为一个与之等价的单带TMS 关健是怎样用S来模拟M 假设M有k个带子 S把此k个带子的信息都存储在它的唯一带子上 并以此来模拟k个带子的效果 它用一个新的符号 作为定界符 以分开不同带子的内容 除了带内容之外 S还必须记录读写头的位置 为此 它在一个符号的顶上加个点 以此来标记读写头在其带上的位置 S把它们想象为虚拟带子和虚拟读写头 像以前一样 加点的带符号应是已经加进带字母表的新符号 40 多带图灵机 41 多带图灵机 S 对于输入w w1 wn 1 S在白己的带子上放入 w1w2 wn 上边没加点 此格式表示了M的全部k个带子的内容 2 为了模拟多带机的一步移动 S在其带子上从标记左端点的第一个 开始扫描 一直扫描到标记右端点的第 k 1 个 其目的是确定虚拟读写头下的符号 然后S进行第二次扫描 并根据M的转移函数指示的运行方式更新其带子 3 任何时候 只要S将某个虚拟读写头向右移动到某个 上面 就意味着M已将自己相应的读写头移动到了其所在的带子中的空白区域上 即以前没有读过的区域上 因此 S在这个带方格上写下空白符 并将这个带方格到最右端的带方格中的内容都向右移动一个格 然后再像以前一样继续模拟 42 多带图灵机 推论3 9 一个语言是图灵可识别的 当且仅当存在多带图灵机识别它 一个图灵可识别语言可由一个普通的 单带 图灵机识别 这个普通图灵机是多带图灵机的一个特例 这就证明了此推论的一个方向 另一个方向可由定理3 8得证 43 非确定型图灵机 非确定型图灵机的有如其名 在计算的过程中 机器可以在多种可能性动作中选择一种继续进行 它的转移函数具有如下形式 Q P Q L R 其计算是一棵树 不同分支对应着机器的不同可能性 44 非确定型图灵机 定理3 10 每个非确定型图灵机都等价于某一个确定型图灵机 能用确定型TMD来模拟非确定型TMN的计算的证明思路是 让D试验N的非确定性计算的所有可能分支 若D能在某个分支中到达接受状态 则接受 否则D的模拟将永不终止 将N在输入w的计算看作一棵树 树的每个分支代表非确定型的分支 结点是N的一个格局 根是起始格局 TMD在这个树上搜索接受格局 我们采用 宽度优先 策略搜索整棵树 这个策略是 在搜索一个深度内的所有分支之后 再去搜索下一个深度内的所有分支 此方法能保证D可以访问树的所有结点 直到它遇到接受格局 45 非确定型图灵机 用于模拟的确定型TMD有3个带子 根据定理3 8 这等价于只有一个带子 机器D将这三个带子用于专门用途 第一个带子包含输入串 且不再改变 第二个带子存放N的带子中的内容 此内容对应N的非确定性计算的某个分支 第三个带子记录D在N的非确定性计算树中的位置 输入带 模拟带 地址带 46 非确定型图灵机 首先考虑第三个带子上表示的数据 N的每个格局确定一个集合 它是由此格局可能转移到的下一个格局组成 这些下一个格局是由N的转移函数指定的 N的非确定性计算中的每个结点最多有b个子结点 其中 b是上述集合中最大的集合所含的元素个数 对树的每个结点 可以给其分配一个地址 它是字母表 b 1 2 b 上的一个串 例如 把地址231分配给按以下方式到达的结点 从根出发走到它的第二个子结点 再由此走到第三个子结点 最后由此走到第一个子结点 此串中的数字告诉我们 在模拟N的非确定计算的一个分支时下一步应做什么 如果一个格局所能有的选择太少 则一个符号可能不对应任何选择 此种倩况下 地址将无效 不对应任何结点 第三个带子上包含 b上的一个串 它代表N的计算树中如下分支 起点是根 终点是此串表示的地址所对应的结点 除非这个地址是无效的 空串是树根的地址 47 非确定型图灵机 D的描述如下 1 开始时 第一个带子包含输入w 第二和第三个带子都是空的 2 把第一个带子复制到第二个带子上 3 用第二个带子去模拟N在输入w上的非确定性计算的某个分支 在N的每一步动作之前 查询第三个带子上的下一个数字 以决定在N的转移函数所允许的选择中作何选择 如果第三个带子上没有符号剩下 或这个非确定性的选择是无效的 则放弃这个分支 转到第4步 如果遇到拒绝格局也转到第4步 如果遇到接受格局 则接受这个输入 4 在第二个带子上 用字典顺序下的下一个串来替代原有的串 转到第2步 以模拟N的计算的下一个分支 48 非确定型图灵机 推论3 11 一个语言是图灵可识别的 当且仅当存在非确定型图灵机识别它 推论3 12 一个语言是可判定的 当且仅当存在非确定型图灵机判定它 确定型图灵机自然是一个非确定型图灵机 此定理的一个方向由此立刻得证 另个方向可内定理3 10得证 49 枚举器 它是图灵机的一种变形 粗略地说 枚举器是带有打印机的图灵机 图灵机把打印机当作输出设备 从而可以打印串 每当图灵机想在打印序列中增加一个串时 就把此串送到打印机 枚举器以空白输入带开始运行 如果不停机 它可能会打印出串的一个无限序列 枚举器E所枚举的语言是最终打印出的串的集合 而且E可能以任意顺序生成这个语言中的串 甚至还会有重复 50 枚举器示意图 控制器 打印机 aababaabba 工作带 51 枚举器 定理3 13 一个语言是图灵可识别的 当且仅当存在枚举器枚举它 52 枚举器 首先证明 如果有枚举器E枚举语言A 则有TMM识别A TMM如下运行 M 对于输入w 1 运行E 每当E输出一个串时 将之与w比较 2 如果w曾经在E的输出中出现过 则接受 显然 M接受在E的输出序列中出现过的那些串 现在证明另一个方向 设s1 s2 s3 是 中的所有串 如果有TMM识别语言A 为A构造枚举器E如下 E 忽略输入 1 对i 1 2 3 重复下列步骤 2 对s1 s2 s3 si中的每一个 M以其作为输入运行i步3 如果有计算接受 则打印出相应的sj 如果M接受串s 它终将出现在E生成的打印列表中 53 通用图灵机 通用TM universalTuringmachine 实现对所有TM的模拟 编码系统它可以在实现对TM的表示的同时 实现对该TM处理的句子的表示 用0和1对这些除空白符以外的其他的带符号进行编码 同时也可以用0和1对TM的移动函数进行编码 54 通用图灵机 M q1 q2 qn 0 1 0 1 B q1 B q2 用X1 X2 X3分别表示0 1 B 用D1 D2分别表示R L qi Xj qk Xl Dm 可以用0i10j10k10l10m表示 M可用111code111code211 11coder111codet是动作 qi Xj qk Xl Dm 的形如0i10j10k10l10m的编码 TMM和它的输入串w则可以表示成111code111code211 11coder111w按照规范顺序分别对表示TM的符号行和表示输入的符号行进行排序 55 通用图灵机 设TMM2 q1 q2 q3 q4 0 1 0 1 B q4 B q3 其中 的定义如下 q4 0 q4 0 R q4 1 q1 1 R q1 0 q1 0 R q1 1 q2 1 R q2 0 q2 0 R q2 1 q3 1 R 编码为1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111通用TM检查M是否接受字符串0011011101110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111001101110 56 主要内容 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描述图灵机的术语 57 算法的定义 非形式地说 算法是为实现某个任务而构造的简单指令集 在日常用语来说 算法有时称为过程或处方 算法在数学中也起着重要的作用 古代数学文献中包含了各种各样任务的算法描述 如寻找素数和最大公因子 当代数学中更是充满了算法 58 希尔伯特问题 1900年希尔伯特提出了23个数学问题 其中的第10个问题是关于算法的 通过有限多次运算就可以决定的过程 一个多项式是一些项的和 其中 每个项都是一个常数和一些变元的积 此常数叫系数 coefficient 例如 6 x x x y z z 6x3yz2是一个项 其系数是6 6x3yz2 3xy2 x3 10是一个多项式 它有四个项和三个变元x y z多项式的根 root 是对它的变元的一个赋值 使此多项式的值为0 上述多项式的一个根是x 5 y 3和z 0 这个根是整数根 integralroot 因为所有变元都被赋予整数值 59 希尔伯特问题 丘奇 图灵论题 Church Turingthesis 希尔伯特第10问题旨在设计一个算法来检测一个多项式是否有整数根 现在用上述术语来重新陈述希尔伯特第10问题 设D p p是有整数