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

CH4 图灵机,2019/6/12,2 of 158,4.1 图灵机的定义,图灵: 计算通常是一个人拿着笔在纸上进行的. 他根据 眼睛看到的纸上符号, 脑中的若干法则, 指示笔 在纸上擦掉或写上一些符号, 再改变他所看到的范围. 继续, 直到他认为计算结束.,脑:控制器 纸:存储带 眼睛和笔:读写头 法则:转移函数,2019/6/12,3 of 158,4.1 图灵机的定义,图灵机的基本模型如图所示。它由一个有限状态控制器，一个读写头和一个输入带组成。其中输入带具有最左端，但右端可以无限伸长。带上的每一格恰好有一个字符。开始时，带上最左边的n个格存放着由有限输入字母表上的字符组成的字符串，第n1格及其右边各格均为空格符。读写头一次可以在带上读或写一个字符，并可根据指令向左或向右移一格。有限状态控制器根据当前的状态，读到输入字符并发布指令。指令的内容包括状态转换，在带上的一格写上(更换)字符，以及读写头向左或向右移动一格等。,2019/6/12,4 of 158,与有限自动机的区别,有限自动机:,输入带长度有限 只能读和右移, 不能写和左移 读完输入停机,2019/6/12,5 of 158,4.1 图灵机的定义,定义4.1.1 图灵机TM是一个五元组 M=(K, , , s, H) 其中， K：是有穷状态集,其中的每个元素称为一个状态； ：是字母表，它的每一个元素称为一个输入符号,包括空格符和左端符, 但不包含符号 和 ； ：转换函数 s K称之为初始状态； HK称为停机状态集，y和n。,2019/6/12,6 of 158,4.1 图灵机的定义,例4.1.1: 删除非空格符,2019/6/12,7 of 158,4.1 图灵机的定义,例4.1.4: 图灵机的计算形式化,2019/6/12,8 of 158,4.1 图灵机的定义,例4.1.1: 删除非空格符,2019/6/12,9 of 158,4.1 图灵机的定义,例4.1.2:永不停机的图灵机,2019/6/12,10 of 158,4.1 图灵机的定义,定义4.1.2 图灵机的格局 除非当前正在扫描空格符,否则所有格局都用左端符开始并且永远不用空格符结束.,2019/6/12,11 of 158,4.1 图灵机的定义,2019/6/12,12 of 158,4.2 图灵机的约定,把不含空格符的输入字符串写在最左端符号 的右方，在输入左方留下一个空格，输入右方都是空格；带头就在与输入字符串之间的空格里；机器在初始状态里开始操作。如果M= (K, , , s, H)是TM, 并且w (-,)* ,那么M在输w上的初始格局 (s, w)。,2019/6/12,13 of 158,4.1 图灵机的定义,定义4.1.3 图灵机的格局产生规则,2019/6/12,14 of 158,4.1 图灵机的定义,例4.1.3: 定义4.1.3的举例,情形1. (q1, a) = (q2, b),例子: (q1, wau) |- M =,(q2, wbu),情形2. (q1, a) = (q2, ),例子(a) (q1, wau) |- M =,(q2, wau),(b) (q1, w) |- M =,(q2, w),情形3. (q1, a) = (q2, ),例子(a) (q1, wau) |- M =,(q2, wau),(b) (q1, wa) |- M =,(q2, wa),2019/6/12,15 of 158,4.1.1 图灵机的记号: 基本机器,写a机: a或者Ma,2019/6/12,16 of 158,4.1.1 图灵机的记号: 基本机器,左移带头机: M 缩写为L 右移带头机: M 缩写为R,2019/6/12,17 of 158,组合机器的规则: 3台机器的组合,约定最左边的机器总是初始机器,直到前一台机器停机为止才应用从前一台机器到后一台机器的连接；后一台机器于是从初始状态和前一台机器留下的带和带头位置上启动。所以，若M1, M2 和M3 都是TM, 则操作如下：在M1的初始状态启动，像M1那样操作直到M1停机为止；然后若当前扫描符号是a则启动M2 并且像M2那样操作；否则若当前扫描符号是b则启动M3并且像M3那样操作。,2019/6/12,18 of 158,组合机器的规则,2019/6/12,19 of 158,组合机器的规则,寻找右边第一个空格,2019/6/12,20 of 158,组合机器的规则,寻找右边第一个空格,寻找左边第一个空格,寻找右边第一个非空格,寻找左边第一个非空格,2019/6/12,21 of 158,组合机器的规则,复制机C,2019/6/12,22 of 158,组合机器的规则,左平移机 S 或者SL 右平移机 S 或者SR,2019/6/12,23 of 158,练习,4.1.9 机器LR和RL总是做相同的工作吗？试解释之。,2019/6/12,24 of 158,4.2 用图灵机计算,定义4.2.1,2019/6/12,25 of 158,4.2 用图灵机计算,设0 ( - , )是字母表，称为M的输入字母表 ；通过固定0是 - , 的子集，我们允许TM在计算中使用除在输入里出现符号外的额外符号 。如果L 0*是语言，并且对任何字符串w 0*，下列关系为真：若w L则M接受w；若w L则M拒绝w, 那么我们说M判定语言L。 若存在TM判定语言L, 则L称为递归的(或者图灵可判定的)。,2019/6/12,26 of 158,4.2 用图灵机计算,TM判定语言L的条件是，当在输入w上启动时它总是停机并且停机的状态是对输入的正确回答：若w L则是y；若w L则是 n。注意当机器的输入里包含空格或左端符时，定义里没有给出关于发生什么事情的保证。,2019/6/12,27 of 158,4.2 用图灵机计算,例4.2.1 图灵机判定语言 L=anbncn:n0,2019/6/12,28 of 158,练习,4.2.2 给出判定下列在a, b上的语言的图灵机: (1) (2) e (3) a (4) a*,2019/6/12,29 of 158,4.2 递归函数,定义4.2.3 递归的函数,2019/6/12,30 of 158,4.2 递归函数,例4.2.3 图灵机计算后继函数 succ(n)=n+1,2019/6/12,31 of 158,4.2 递归可枚举语言,定义4.2.4 设0 ( - , )是字母表，并设L 0*是语言。若对任何字符串w 0*，下列关系为真：w L当且仅当M在输入w上停机, 那么我们说M半判定语言L。 语言L是递归可枚举的(或者图灵可识别的),当且仅当存在TM M半判定L 。 只要它确实最终到达停机格局，我们就不深究它到达哪种停机格局。,2019/6/12,32 of 158,4.2 递归可枚举语言,例4.2.4 半判定举例,设L = w a, b* : w至少包含一个a。,它向右扫描直到遇到a为止，然后停机。若没有找到 a，这台机器就在输入后面跟着的空格里永远移动下去，永不停机。所以L恰恰是使M在输入w上停机的a, b*里的字符串w的集合。因此M半判 L，所以L是递归可枚举的。,2019/6/12,33 of 158,4.2 递归可枚举语言,不停机的3种常见方式,“在空格里永远移动下去 ”只是TM不停机的方式之一。也可 “死循环” (如(q, a) = (q, a) )。还可以设计更复杂的循环行为，让机器在有穷多个不同的格局里无限地运行下去。,2019/6/12,34 of 158,4.2 递归可枚举语言,定理4.2.1 若语言是递归的,则它是递归可枚举的.,除了反转两种特殊停机状y和n的作用以外, 都相同.,2019/6/12,35 of 158,各种语言类的包含关系,2019/6/12,36 of 158,4.3 图灵机的扩充: 多带图灵机(mTM),mTM的转移函数(k个带) : (K-H) kK( , )k 初始: 输入放在第1个带子上, 其它空白. 定理: 每个多带TM都有等价的单带TM.,2019/6/12,37 of 158,4.3 多带图灵机(mTM),例4.3.1 利用mTM实现复制机C,2019/6/12,38 of 158,4.3 多带图灵机(mTM),2019/6/12,39 of 158,4.3 多带图灵机(mTM),例4.3.2 利用mTM实现两个二进制数相加,2019/6/12,40 of 158,4.3 多带图灵机(mTM),2019/6/12,41 of 158,4.3 多带图灵机(mTM),4.3.2 双向无穷带图灵机 4.3.3 多带头图灵机 4.3.4 二维带图灵机,TM的另一种推广允许“带”是无穷的二维网格。 （你甚至可允许更高维的空间。）,2019/6/12,42 of 158,4.3 多带图灵机(mTM),定理4.3.2 有多带、多带头、双向无穷图灵机或者多维带的图灵机，它们判定或半判定的任何语言以及计算的任何函数，都分别可用标准图灵机判定、半判定或者计算.,2019/6/12,43 of 158,4.5 非确定型图灵机(NTM),2019/6/12,44 of 158,4.5 非确定型图灵机(NTM),例4.5.1 NTM验证合数,2019/6/