计算理论与算法分析设计：CH4 图灵机

CH4图灵机

11/6/202214.1图灵机的定义图灵:计算通常是一个人拿着笔在纸上进行的.

他根据

眼睛看到的纸上符号,脑中的若干法则,

指示笔在纸上擦掉或写上一些符号,

再改变他所看到的范围.

继续,直到他认为计算结束.脑:控制器纸:存储带眼睛和笔:读写头法则:转移函数11/6/202224.1图灵机的定义图灵机的基本模型如图所示。它由一个有限状态控制器，一个读写头和一个输入带组成。其中输入带具有最左端，但右端可以无限伸长。带上的每一格恰好有一个字符。开始时，带上最左边的n个格存放着由有限输入字母表上的字符组成的字符串，第n＋1格及其右边各格均为空格符。读写头一次可以在带上读或写一个字符，并可根据指令向左或向右移一格。有限状态控制器根据当前的状态，读到输入字符并发布指令。指令的内容包括状态转换，在带上的一格写上(更换)字符，以及读写头向左或向右移动一格等。11/6/20223与有限自动机的区别有限自动机:

输入带长度有限只能读和右移,不能写和左移读完输入停机11/6/202244.1图灵机的定义定义4.1.1

图灵机TM是一个五元组

M=(K,,δ,s,H)其中，K：是有穷状态集,其中的每个元素称为一个状态；：是字母表，它的每一个元素称为一个输入符号,包括空格符└┘和左端符►,但不包含符号和；δ

：转换函数s

K称之为初始状态；HK称为停机状态集，y和n。11/6/202254.1图灵机的定义例4.1.1:删除非空格符11/6/202264.1图灵机的定义例4.1.4:图灵机的计算形式化11/6/202274.1图灵机的定义例4.1.1:删除非空格符11/6/202284.1图灵机的定义例4.1.2:永不停机的图灵机11/6/202294.1图灵机的定义定义4.1.2图灵机的格局除非当前正在扫描空格符,否则所有格局都用左端符►开始并且永远不用空格符└┘结束.11/6/2022104.1图灵机的定义11/6/2022114.2

图灵机的约定把不含空格符的输入字符串写在最左端符号►

的右方，在输入左方留下一个空格，输入右方都是空格；带头就在►与输入字符串之间的空格里；机器在初始状态里开始操作。如果M=(K,,δ,s,H)是TM,并且w

(-{└┘,►})*,那么M在输w上的初始格局(s,►└┘w)。11/6/2022124.1图灵机的定义定义4.1.3图灵机的格局产生规则

11/6/2022134.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└┘)11/6/2022144.1.1

图灵机的记号:基本机器写a机:a或者Ma11/6/2022154.1.1

图灵机的记号:基本机器左移带头机:M缩写为L

右移带头机:M缩写为R11/6/202216组合机器的规则:3台机器的组合约定最左边的机器总是初始机器直到前一台机器停机为止才应用从前一台机器到后一台机器的连接；后一台机器于是从初始状态和前一台机器留下的带和带头位置上启动。所以，若M1,M2

和M3

都是TM,则操作如下：在M1的初始状态启动，像M1那样操作直到M1停机为止；然后若当前扫描符号是a则启动M2并且像M2那样操作；否则若当前扫描符号是b则启动M3并且像M3那样操作。11/6/202217组合机器的规则11/6/202218组合机器的规则寻找右边第一个空格11/6/202219组合机器的规则寻找右边第一个空格寻找左边第一个空格寻找右边第一个非空格寻找左边第一个非空格11/6/202220组合机器的规则复制机C11/6/202221组合机器的规则左平移机S或者SL

右平移机S或者SR11/6/202222练习4.1.9机器LR和RL总是做相同的工作吗？试解释之。11/6/2022234.2用图灵机计算定义4.2.111/6/2022244.2用图灵机计算设0(

-{└┘,►})是字母表，称为M的输入字母表；通过固定0是

-{└┘,►}的子集，我们允许TM在计算中使用除在输入里出现符号外的额外符号。如果L0*是语言，并且对任何字符串w0*，下列关系为真：若wL则M接受w；若wL则M拒绝w,那么我们说M判定语言L。

若存在TM判定语言L,则L称为递归的(或者图灵可判定的)。11/6/2022254.2用图灵机计算TM判定语言L的条件是，当在输入w上启动时它总是停机并且停机的状态是对输入的正确回答：若wL则是y；若wL则是

n。注意当机器的输入里包含空格或左端符时，定义里没有给出关于发生什么事情的保证。11/6/2022264.2用图灵机计算例4.2.1图灵机判定语言

L={anbncn:n0}11/6/202227练习4.2.2给出判定下列在{a,b}上的语言的图灵机:

(1)

(2){e}

(3){a}

(4){a}*11/6/2022284.2递归函数定义4.2.3递归的函数11/6/2022294.2递归函数例4.2.3图灵机计算后继函数

succ(n)=n+111/6/2022304.2递归可枚举语言定义4.2.4设0(

-{└┘,►})是字母表，并设L0*是语言。若对任何字符串w0*，下列关系为真：wL当且仅当M在输入w上停机,那么我们说M半判定语言L。

语言L是递归可枚举的(或者图灵可识别的),当且仅当存在TMM半判定L。只要它确实最终到达停机格局，我们就不深究它到达哪种停机格局。11/6/2022314.2递归可枚举语言例4.2.4半判定举例

设L={w{a,b}*:w至少包含一个a}。

它向右扫描直到遇到a为止，然后停机。若没有找到a，这台机器就在输入后面跟着的空格里永远移动下去，永不停机。所以L恰恰是使M在输入w上停机的{a,b}*里的字符串w的集合。因此M半判L，所以L是递归可枚举的。11/6/2022324.2递归可枚举语言

不停机的3种常见方式“在空格里永远移动下去”只是TM不停机的方式之一。也可“死循环”(如δ(q,a)=(q,a))。还可以设计更复杂的循环行为，让机器在有穷多个不同的格局里无限地运行下去。11/6/2022334.2递归可枚举语言定理4.2.1若语言是递归的,则它是递归可枚举的.定理4.2.2(递归语言的重要性质)若L是递归语言,则它的补L也是递归的.除了反转两种特殊停机状y和n的作用以外,都相同.11/6/202234各种语言类的包含关系正则语言上下文无关语言可判定语言图灵可识别语言11/6/2022354.3图灵机的扩充:多带图灵机(mTM)…C

mTM的转移函数(k个带)

:(K-H)

kK({,})k

初始:输入放在第1个带子上,其它空白.

定理:每个多带TM都有等价的单带TM.11/6/2022364.3多带图灵机(mTM)例4.3.1利用mTM实现复制机C

11/6/2022374.3多带图灵机(mTM)11/6/2022384.3多带图灵机(mTM)例4.3.2利用mTM实现两个二进制数相加

11/6/2022394.3多带图灵机(mTM)11/6/2022404.3多带图灵机(mTM)4.3.2双向无穷带图灵机4.3.3多带头图灵机4.3.4二维带图灵机

TM的另一种推广允许“带”是无穷的二维网格。（你甚至可允许更高维的空间。）11/6/2022414.3多带图灵机(mTM)定理4.3.2有多带、多带头、双向无穷图灵机或者多维带的图灵机，它们判定或半判定的任何语言以及计算的任何函数，都分别可用标准图灵机判定、半判定或者计算.11/6/2022424.5非确定型图灵机(NTM)11/6/2022434.5非