计算理论与算法

CH4 图灵机 5/17/202414.1 图灵机的定义图灵图灵:计算通常是一个计算通常是一个人人拿着拿着笔笔在在纸纸上进行的上进行的.他他根据根据 眼睛眼睛看到的纸上符号看到的纸上符号,脑脑中的若干中的若干法则法则,指示笔指示笔 在纸上在纸上擦掉或写上擦掉或写上一些符号一些符号,再再改变他所看到的范围改变他所看到的范围.继续继续,直到他认为计算结束直到他认为计算结束.脑脑:控制器控制器 纸纸:存储带存储带 眼睛和笔眼睛和笔:读写头读写头 法则法则:转移函数转移函数5/17/202424.1 图灵机的定义 图灵机的基本模型如图所示。它由一个有限状态控制器，图灵机的基本模型如图所示。它由一个有限状态控制器，一个读写头和一个输入带组成。其中输入带具有最左端，但右一个读写头和一个输入带组成。其中输入带具有最左端，但右端可以无限伸长。带上的每一格恰好有一个字符。开始时，带端可以无限伸长。带上的每一格恰好有一个字符。开始时，带上最左边的上最左边的n个格存放着由有限输入字母表上的字符组成的字个格存放着由有限输入字母表上的字符组成的字符串，第符串，第n1 1格及其右边各格均为空格符。读写头一次可以在格及其右边各格均为空格符。读写头一次可以在带上读或写一个字符，并可根据指令向左或向右移一格。有限带上读或写一个字符，并可根据指令向左或向右移一格。有限状态控制器根据当前的状态，读到输入字符并发布指令。指令状态控制器根据当前的状态，读到输入字符并发布指令。指令的内容包括状态转换，在带上的一格写上的内容包括状态转换，在带上的一格写上(更换更换)字符，以及读字符，以及读写头向左或向右移动一格等。写头向左或向右移动一格等。5/17/20243与有限自动机的区别有限自动机有限自动机:输入带长度有限输入带长度有限 只能只能读读和和右移右移,不能不能写写和和左移左移 读完输入停机读完输入停机5/17/202444.1 图灵机的定义n定义定义4.1.1 图灵机图灵机TM是一个五元组是一个五元组 M=(K,s,H)其中，其中，K：是有穷状态集是有穷状态集,其中的每个元素称为一个状态；其中的每个元素称为一个状态；：是字母表是字母表，它的每一个元素称为一个输入符号，它的每一个元素称为一个输入符号,包括包括空格符空格符和左端符和左端符,但不包含符号但不包含符号 和和；：转换函数：转换函数s K称之为称之为初始状态初始状态；H K称为称为停机停机状态集状态集，y和和n。5/17/202454.1 图灵机的定义n例例4.1.1:删除非空格符删除非空格符5/17/202464.1 图灵机的定义n例例4.1.4:图灵机的计算形式化图灵机的计算形式化5/17/202474.1 图灵机的定义n例例4.1.1:删除非空格符删除非空格符5/17/202484.1 图灵机的定义n例例4.1.2:永不停机的图灵机永不停机的图灵机5/17/202494.1 图灵机的定义n定义定义4.1.2 图灵机的格局图灵机的格局 除非当前正在扫描空格符,否则所有格局都用左端符开始并且永远不用空格符结束.5/17/2024104.1 图灵机的定义5/17/2024114.2 图灵机的约定把不含空格符的输入字符串写在最左端符号把不含空格符的输入字符串写在最左端符号 的右方，在输入左方留下一个空格，输入右方的右方，在输入左方留下一个空格，输入右方都是空格；带头就在都是空格；带头就在与输入字符串之间的空与输入字符串之间的空格里；机器在初始状态里开始操作。如果格里；机器在初始状态里开始操作。如果M=(K,s,H)是是TM,并且并且w (-,)*,那么那么M在输在输w上的初始格局上的初始格局(s,w)。5/17/2024124.1 图灵机的定义n定义定义4.1.3 图灵机的格局产生规则图灵机的格局产生规则 5/17/2024134.1 图灵机的定义n例例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)5/17/2024144.1.1 图灵机的记号:基本机器n 写写a机机:a或者或者Ma 5/17/2024154.1.1 图灵机的记号:基本机器n 左移带头机左移带头机:M 缩写为缩写为Ln 右移带头机右移带头机:M 缩写为缩写为R5/17/202416组合机器的规则:3台机器的组合n 约定最左边的机器总是初始机器约定最左边的机器总是初始机器直到前一台机器停机为止才应用从前直到前一台机器停机为止才应用从前一台机器到后一台机器的连接；后一一台机器到后一台机器的连接；后一台机器于是从初始状态和前一台机器台机器于是从初始状态和前一台机器留下的带和带头位置上启动。所以，留下的带和带头位置上启动。所以，若若M1,M2 和和M3 都是都是TM,则操作如下：则操作如下：在在M1的初始状态启动，像的初始状态启动，像M1那样操那样操作直到作直到M1停机为止；然后若当前扫描停机为止；然后若当前扫描符号是符号是a则启动则启动M2 并且像并且像M2那样操作；那样操作；否则若当前扫描符号是否则若当前扫描符号是b则启动则启动M3并并且像且像M3那样操作。那样操作。5/17/202417组合机器的规则5/17/202418组合机器的规则n寻找右边第一个空格寻找右边第一个空格5/17/202419组合机器的规则寻找右边第一个空格寻找右边第一个空格 寻找左边第一个空格寻找左边第一个空格寻找右边第一个非空格寻找右边第一个非空格 寻找左边第一个非空格寻找左边第一个非空格5/17/202420组合机器的规则n复制机复制机C5/17/202421组合机器的规则n左平移机左平移机 S 或者或者SLn 右平移机右平移机 S 或者或者SR5/17/202422练习n4.1.9 机器机器LR和和RL总是做相同的工总是做相同的工作吗？试解释之。作吗？试解释之。5/17/2024234.2 用图灵机计算n定义定义4.2.15/17/2024244.2 用图灵机计算n设设 0 (-,)是字母表，称为是字母表，称为M的的输入字母表输入字母表；通过固定；通过固定 0是是 -,的子集，我们允许的子集，我们允许TM在计算在计算中使用除在输入里出现符号外的额外符中使用除在输入里出现符号外的额外符号号。如果。如果L 0*是是语言，并且对任何语言，并且对任何字符串字符串w 0*，下列关系为真：若，下列关系为真：若w L则则M接受接受w；若；若w L则则M拒绝拒绝w,那么那么我们说我们说M判定判定语言语言L。n若存在若存在TM判定语言判定语言L,则则L称为称为递归的递归的(或者或者图灵可判定的图灵可判定的)。5/17/2024254.2 用图灵机计算nTM判定语言判定语言L的条件是，当在输入的条件是，当在输入w上启动时它总是停机并且停机的状态上启动时它总是停机并且停机的状态是对输入的正确回答：是对输入的正确回答：若若w L则是则是y；若；若w L则是则是 n。注意当机器的输入。注意当机器的输入里包含空格或左端符时，定义里没有里包含空格或左端符时，定义里没有给出关于发生什么事情的保证。给出关于发生什么事情的保证。5/17/2024264.2 用图灵机计算n例例4.2.1 图灵机判定语言图灵机判定语言L=anbncn:n 05/17/202427练习n4.2.2 给出判定下列在给出判定下列在a,b上的语上的语言的图灵机言的图灵机:(1)(2)e(3)a(4)a*5/17/2024284.2 递归函数n定义定义4.2.3 递归的函数递归的函数5/17/2024294.2 递归函数n例例4.2.3 图灵机计算后继函数图灵机计算后继函数succ(n)=n+15/17/2024304.2 递归可枚举语言n定义定义4.2.4 设设 0 (-,)是字母表，并设是字母表，并设L 0*是是语言。若对任何字符串语言。若对任何字符串w 0*，下列关系为真：，下列关系为真：w L当且仅当当且仅当M在输入在输入w上停机上停机,那么我们说那么我们说M半判定半判定语语言言L。n语言语言L是是递归可枚举的递归可枚举的(或者或者图灵可识别图灵可识别的的),当且仅当存在当且仅当存在TM M半半判定判定L。n只要它确实最终到达停机格局，我们就只要它确实最终到达停机格局，我们就不不深究它到达哪种停机格局。深究它到达哪种停机格局。5/17/2024314.2 递归可枚举语言n例例4.2.4 半判定举例半判定举例 设设L=w a,b*:w至少包含一个至少包含一个a。它向右扫描直到遇到它向右扫描直到遇到a为止，然为止，然后停机。若没有找到后停机。若没有找到 a，这台机，这台机器就在输入后面跟着的空格里器就在输入后面跟着的空格里永远移动下去，永不停机。所永远移动下去，永不停机。所以以L恰恰是使恰恰是使M在输入在输入w上停机上停机的的a,b*里的字符串里的字符串w的集合。的集合。因此因此M半判半判 L，所以，所以L是递归可是递归可枚举的。枚举的。5/17/2024324.2 递归可枚举语言n 不停机的不停机的3种常见方式种常见方式“在空格里永远移动下去在空格里永远移动下去”只是只是TM不停机的不停机的方式之一。也可方式之一。也可“死循环死循环”(如如(q,a)=(q,a)。还可以设计更复杂的循环行为，让机器在。还可以设计更复杂的循环行为，让机器在有穷多个不同的格局里无限地运行下去。有穷多个不同的格局里无限地运行下去。5/17/2024334.2 递归可枚举语言n定理定理4.2.1 若语言是递归的若语言是递归的,则它是递则它是递归可枚举的归可枚举的.n定理定理4.2.2(递归语言的重要性质递归语言的重要性质)若若L是递归语言是递归语言,则它的补则它的补L也是递归也是递归的的.除了反转两种特殊停机状除了反转两种特殊停机状y和和n的作用的作用以外以外,都相同都相同.5/17/202434各种语言类的包含关系正则语言正则语言 上下文无关语言上下文无关语言 可判定语言可判定语言 图灵可识别语言图灵可识别语言 5/17/2024354.3 图灵机的扩充:多带图灵机(mTM)C mTM的转移函数的转移函数(k个带个带):(K-H)kK(,)k 初始初始:输入放在第输入放在第1个带子上个带子上,其它空白其它空白.定理定理:每个多带每个多带TM都有等价的单带都有等价的单带TM.5/17/2024364.3 多带图灵机(mTM)n例例4.3.1 利用利用mTM实现复制机实现复制机C 5/17/2024374.3 多带图灵机(mTM)5/17/2024384.3 多带图灵机(mTM)n例例4.3.2 利用利用mTM实现两个二进制数实现两个二进制数相加相加 5/17/2024394.3 多带图灵机(mTM)5/17/2024404.3 多带图灵机(mTM)n4.3.2 双向无穷带图灵机双向无穷带图灵机n4.3.3 多带头图灵机多带头图灵机n4.3.4 二维带图灵机二维带图灵机 TM的另一种推广允许的另一种推广允许“带带”是无穷的二维网格。是无穷的二维网格。（你甚至可允许更高维的空间。）（你甚至可允许更高维的空间。）5/17/2024414.3 多带图灵机(mTM)n定理定理4.3.2 有多带、多带头、双向无有多带、多带头、双向无穷图灵机或者多维带的图灵机，它穷图灵机或者多维带的图灵机，它们判定或半判定的任何语言以及计们判定或半判定的任何语言以及计算的任何函数，都分别可用标准图算的任何函数，都分别可用标准图灵机判定、半判定或者计算灵机判定、半判定或者计算.5/17/2024424.5 非确定型图灵机(NTM)5/17/2024434.5 非确定型图灵机(NTM)n例例4.5.1 NTM验证合数验证合数5/17/2024444.5 非确定型图灵机(NTM)5/17/2024454.5 非确定型图灵机(NTM)5/17/202446用DTM模拟NTM5/17/2024474.5 非确定型图灵机(NTM)n确定型确定型TM对对NTM的模拟不是步对的模拟不是步对步的模拟。步的模拟。n它要求用它要求用n的的指数多步指数多步去模拟非确定去模拟非确定型机器的型机器的n步计算，而本章描述的所步计算，而本章描述的所有其他模拟事实上都是多项式的。有其他模拟事实上都是多项式的。5/17/202448