计算理论与算法12年CH4TM.ppt

1.7 对偶与范式 CH4 图灵机 4.1 图灵机的定义 4.1 图灵机的定义 与有限自动机的区别 4.1 图灵机的定义 4.1 图灵机的定义 4.1 图灵机的定义 4.1 图灵机的定义 4.1 图灵机的定义 4.1 图灵机的定义 4.1 图灵机的定义 4.2 图灵机的约定 4.1 图灵机的定义 4.1 图灵机的定义 4.1.1 图灵机的记号: 基本机器 写a机: a或者Ma 4.1.1 图灵机的记号: 基本机器 左移带头机: M? 缩写为L 右移带头机: M? 缩写为R 组合机器的规则: 3台机器的组合 约定最左边的机器总是初始机器 组合机器的规则 组合机器的规则 寻找右边第一个空格 组合机器的规则 组合机器的规则 复制机C 组合机器的规则 左平移机 S? 或者SL 右平移机 S? 或者SR 练习 4.1.9 机器LR和RL总是做相同的工作吗？试解释之。 4.2 用图灵机计算 定义4.2.1 4.2 用图灵机计算 设?0 ? (? -{└┘ , ?})是字母表，称为M的输入字母表 ；通过固定?0是? -{└┘ , ?}的子集，我们允许TM在计算中使用除在输入里出现符号外的额外符号 。如果L ? ?0*是语言，并且对任何字符串w ? ?0*，下列关系为真：若w ? L则M接受w；若w ?L则M拒绝w, 那么我们说M判定语言L。 若存在TM判定语言L, 则L称为递归的(或者图灵可判定的)。 4.2 用图灵机计算 TM判定语言L的条件是，当在输入w上启动时它总是停机并且停机的状态是对输入的正确回答：若w ? L则是y；若w ?L则是 n。注意当机器的输入里包含空格或左端符时，定义里没有给出关于发生什么事情的保证。 4.2 用图灵机计算 例4.2.1 图灵机判定语言L={anbncn:n?0} 练习 4.2.2 给出判定下列在{a, b}上的语言的图灵机:(1) ? (2) {e}(3) {a}(4) {a}* 4.2 递归函数 定义4.2.3 递归的函数 4.2 递归函数 例4.2.3 图灵机计算后继函数succ(n)=n+1 4.2 递归可枚举语言 定义4.2.4 设?0 ? (? -{└┘ , ?})是字母表，并设L ? ?0*是语言。若对任何字符串w ? ?0*，下列关系为真：w ? L当且仅当M在输入w上停机, 那么我们说M半判定语言L。 语言L是递归可枚举的(或者图灵可识别的),当且仅当存在TM M半判定L 。 只要它确实最终到达停机格局，我们就不深究它到达哪种停机格局。 4.2 递归可枚举语言 例4.2.4 半判定举例 4.2 递归可枚举语言 不停机的3种常见方式 4.2 递归可枚举语言 定理4.2.1 若语言是递归的,则它是递归可枚举的. 4.3 图灵机的扩充: 多带图灵机(mTM) 4.3 多带图灵机(mTM) 例4.3.1 利用mTM实现复制机C 4.3 多带图灵机(mTM) 4.3 多带图灵机(mTM) 例4.3.2 利用mTM实现两个二进制数相加 4.3 多带图灵机(mTM) 4.3 多带图灵机(mTM) 4.3.2 双向无穷带图灵机 4.3.3 多带头图灵机 4.3.4 二维带图灵机 4.3 多带图灵机(mTM) 定理4.3.2 有多带、多带头、双向无穷图灵机或者多维带的图灵机，它们判定或半判定的任何语言以及计算的任何函数，都分别可用标准图灵机判定、半判定或者计算. 4.5 非确定型图灵机(NTM) 4.5 非确定型图灵机(NTM) 例4.5.1 NTM验证合数 4.5 非确定型图灵机(NTM) 4.5 非确定型图灵机(NTM) 用DTM模拟NTM 4.5 非确定型图灵机(NTM) 确定型TM对NTM的模拟不是步对步的模拟。 它要求用n的指数多步去模拟非确定型机器的n步计算，而本章描述的所有其他模拟事实上都是多项式的。 设L = {w ? {a, b}* : w至少包含一个a}。 它向右扫描直到遇到a为止，然后停机。若没有找到 a，这台机器就在输入后面跟着的空格里永远移动下去，永不停机。所以L恰恰是使M在输入w上停机的{a, b}*里的字符串w的集合。因此M半判 L，所以L是递归可枚举的。 “在空格里永远移动下去 ”只是TM不停机的方式之一。也可 “死循环” (如δ(q, a) = (q, a) )。还可以设计更复杂的循环行为，让机器在有穷多个不同的格局里无限地运行下去。 定理4.2.2(递归语言的重要性质) 若L是递归语言,则它的补L也是递归的. 除了反转两种特殊停机状y和n的作用以外, 都相同. 各种语言类的包含