形式语言与自动机理论：第4章 Turing机

第4章Turing机4.1Turing机的定义4.2用Turing机计算4.3Turing的扩充4.4随机存取Turing机4.5非确定型Turing机4.6文法4.7数值函数引论图灵（AlanMathisomTuring）在1963年提出了图灵模型，它是一个通用的计算模型；TM是计算机的一个简单的数学模型，与现今看到的计算机具有相同的功能。我们希望通过研究图灵机，来研究它所定义的语言——递归可枚举集（recursivelyenumerableset）和它所能计算的整函数——部分递归函数（partialrecursivefunction），同时，也为算法和可计算性的研究提供形式化描述工具。4.1Turing机的定义图灵提出TM的目的是为了对有效的计算过程（算法）进行形式化的描述。Turing机被设计成同时满足以下三个标准：它们应当是自动机，即它们的构造和功能一般应与前面研究过的装置相同；它们应当尽量简单，这是就描述、形式化定义和讨论来说的;它们应当尽量一般，这是就可完成的计算而言。图灵给出的基本模型包括：一个有穷控制器，一条含有无穷多个带方格的输入带，一个读头。基本图灵机的物理模型：控制器一步操作：根据当前状态和读写头当前扫描的带符号，控制器完成二种功能：改变有穷控制器的状态；在当前扫描的方格里写一个符号替换该位置符号；或者把读写头向右或者向左移动一格。q0q1q3q2h

abaa读写头（双向移动）有穷控制器定义4.1.1Turing机是五元组(K,∑,δ,s,H),其中K是状态的有穷集；∑是字母表，包含空格符︺和左端符▽，但不含←和→；s∈K是初始状态；HK是停机状态的集合；δ是转移函数，它是从(K-H)×∑到K×(∑∪{←,→})的函数，使得对所有q∈K-H，若δ(q,▽)=(p,b),则b=→；对所有q∈K-H和a∈∑，若δ(q,a)=(p,b),则b≠▽；

对δ的要求的注意：当M看到带左端▽时，它必须向右移动；M永写不出▽，▽是带左端标志，应是唯一的；δ在H里的状态上无定义，当机器到达停机状态就停止。【例4.1.1】考虑Turing机M=(K,∑,δ,s,{h})其中：

K={}， ∑={a,∟,h}，s=;qδ(q,)a(,∟)∟(h,∟)(,→)a(,a)∟(,→)(,→)状态变换如下（,）→（,→）→（,a）→（,∟）→（,→）→（,a）→（,∟）→（,→）→（,∟）→（h,∟）∟aa∟∟h注意：这台Turing机完成把带上非空格符改成空格，也称删除非空格符号。【例4.1.2】考虑TMM=(K,∑,δ,s,H)，其中：

K={}， ∑={a,∟,}，

s=，

H={h}。 其中δ如下表所：

这台机器向左扫描直到发现 ∟为止，然后停机。如果从带头 位置向左到带左端的每个方格都包含a，带左端包含，那么M将移动到带左端，并从此就再带左端和它右方的方格之间来回移动。Turing机的操作可以永不停止。qδ(q,)a(,←)∟(h,∟)(,→)定义4.1.2Turing机M＝(K,∑,δ,s,H)的格局是

K×▽×((－{︺})∪{e})的成员。

注：状态头前串+头处符号头后串除非当前正在扫描空格符，否则所有格局都用左端符开始且永远不用空格符结束。 因此： 是格局； 不是格局。 状态分量属于H的格局称为停机格局。我们写wau表示格局(q,wa,u)，即把(q,wa,u)记作(q,wau)。定义4.1.3

设M＝(K,∑,δ,s,H)是Turing机，考虑M的两个格局 （）和（），其中。 那么 当且仅当对某个1.当b∈∑时，并且；2.当b=←时，而且(a)若≠∟或则，(b)若a1＝∟且则；3.当b=→时，而且(a)，或者(b)，并且=∟。【例4.1.3】设 ，其中u不用∟结尾，a,b∈∑。

1.

例子：

2. 3.下面用例子说明上述定义的含义：也分3种情形定义4.1.4

对任意Turing机M，设是的自反传递闭包；若格局 ，则称格局产生格局。M的计算是格局序列，其中n≥0，称计算的长度为n或它有n步，写成。【例4.1.4】考虑例4.1.1中描述的Turing机M，计算如下：4.1.1Turing机的记号使用分层的记号，其中越来越复杂的机器被从更简单的材料中构造出来。基本机器：写符号机和移带头机。写符号机：固定字母表∑，对每个a∈∑∪{←，→}-{}，Turing机Ma=({s,h},∑,δ,s,{h}),其中对每个b∈∑-{}δ(s,b)=(h,a)，则这台机器唯一操作就是完成动作a——若a∈∑,则写符号a，若a∈{←,→}，则按照a所指示的方向移动——然后立即停机。写符号机用的太多，用写a来代替Ｍ。移带头机M←和M→缩写称L和R。组合机器的规则直到前一台机器停机为止才应用从前一台机器到后一台机器的连接；后一台机器于是从初始状态和前一台机器留下的带和带头位置上启动。所以，若M1，M2和M3都是Turing机，则下图里显示的机器操作如下：在M1的初始状态启动，像M1那样操作直到M1停机为止；然后若当前扫描符号是a则启动M2并且像M2那样操作；否则若当前扫描符号是b则启动M3并且像M3那样操作。M1M3M2ab用它的各部分给出组合成的Turing机的明确定义是直截了当的。并可用上图所示机器作示范。假设三台Turing机M1

，M2和M3分别是：我们假定所有这些机器的状态都不相交，因为在组合机器的背景下这样假定是最方便的。于是，上图里所示的组合机器是： 其中： 对每个如下定义：

＞RRab∟图4.4(a)两台R机组合＞RRab∟图4.4(b)左机缩记图4.5(a)右移到空格为止R∟＞R＞Ra≠∟图4.5(b)左机R∟缩记＞RLa∟a≠∟图4.6右移到非空格符，并在其左边复制之＞RR∟∟a≠∟图4.8复制机C即﹄W﹄=>﹄W﹄W﹄图4.9左平移S←即▽﹄W﹄=>▽W﹄L∟∟a≠∟＞L∟R4.2用Turing机计算首先约定输入，M在输入上的初始格局是。定义4.2.1设M＝(K,∑,δ,s,H)是Turing机,使得包含 两个不同的停机状态(y和n分别表示“是”和“否”)。状 态分量是y的任何停机格局都称为接受格局，而状态 分量是n的停机格局称为拒绝格局。 对输入

，若

产生接受格局则我 们说M接受w；若

产生拒绝格局则我们说M拒 绝w。设是字母表，称为M的输入字母表；通过固定∑0是 的真子集，我们允许Turing机在计算中使用除在输入里出现符号外的额外符号。如果是语言，并且对任何字符串，下列关系为真：若则M接受w；若则M拒绝w，那门我们说M判定语言L。若存在Turing机判定语言L则称L是递归的。即Turing机判定语言L的条件：当在输入w上启动时它总是停机，并且停机的状态是对输入的正确回答。接受w或拒绝wRdRdRdL∟yndab,c∟c,∟a,∟a,dbcb,d【例4.2.1】考虑语言

（之前的语言识别器都无法识别）4.2.1递归函数定义4.2.2

设M＝(K,∑,δ,s,{h})是Turing机，

是字母表，并设。假设M在输入w上停机，而 且对某个，则y称为M 在输入w上的输出，并表示成M(w)。注意仅当M在输 入w上停机时M(w)才有定义，而且事实上是在形如 的格局里停机，其中。现在设f是从到的任意函数，对于所有则我们说M计算函数f。若存在Turing机计算函数f，则称f为递归的。【例4.2.2】函数k(w)=ww可用机器CS←计算，即在复制机后面跟着左平移机。任何自然数可用唯一的方式表示成里的字符串。定义4.2.3

设M＝(K,∑,δ,s,{h})是Turing机使得0,1,;∈∑， 并设对某个k≥1，f是从到N的函数。若对所有的

（即对都是整数的二进制编码的 任意k个字符串），

则我们说M计算函数f。即若M在整数的二 进制表示的输入上启动则它最终停机，并且当它确实 停机时带上有表示数字的字符串——函 数值。若存在计算函数的Turing机M，则f称为递归的。多变量数值函数：【例4.2.3】设计后继函数succ(n)=n+1的机器;R∟L101SR10∟L∟4.2.2递归可枚举语言定义4.2.4

设M＝(K,∑,δ,s,H)是Turing机，是 字母表，并设是语言。若对任意字符串 下列关系为真：w∈L当且仅当M在输入w上停机,则我 们说M半判定L。语言L是递归可枚举的当且仅当存在 Turing机M半判定L。当向M提供输入w∈L时，要求它最终停机。只要它确实最终达到停机格局，我们就不深究他达到了何种停机格局。若，则M必然永不进入停机状态，因为任何非停机格局都产生某种其它格局，所以在这种情形里机器必然无限的继续计算。我们将M在输入w上不停机记作M(w)=↗。则Turing机M半判定语言的定义如下： 对所有，M(w)=↗当且仅当。例4.2.4设L={w∈{a,b}*:w至少包含一个a}

于是下图所示Turing机半判定语言L。对于某个w∈{a,b}*，初始格局，只是向右扫描直到遇到a为止，然后停机。否则永不停机。Ra注意：1、图灵机半判定性是确定性有穷自动机接受概念的扩充，但有穷自动机读完了所有输入时它总是停机---这种计算装置是一个算法。2、半判定语言L的图灵机不能用来辨别字符串w是否属于L，因为若w不属于L时它永不停机（不知道等多久能得到答案）---半判定语言的图灵机都不是算法。4.2.2递归可枚举语言定理4.2.1

若语言是递归的，则它是递归可枚举的。证明：给定判定L的任意Turing机M＝(K,∑,δ,s,{y,n})，可定义半判定L的Turing机如下：M’＝(K,∑,δ’,s,{y})，其中δ’只是δ增加下列关于n的转移（n不再是停机状态）：对于所有a∈∑,δ’(n,a)=δ(n,a)----即在n状态“死循环”很显然，若M判定L，则M’半判定L。定理4.2.2

若L是递归语言则它的补L

也是递归的。证明：很显然只要互换y和n状态即可。M’(w)=y当且仅当M(w)=n，因此M’判定L的补语言。注意：以上两个命题的逆命题均不成立！4.3图灵机的扩充从多种方向上扩充Turing机模型的效果。“新改进型”的Turing机在每种情形里都是可用标准模型模拟，即说明Turing机是终极的计算装置。4.3.1多带Turing机定义4.3.1设k≥1是整数。k带Turing机是(K,∑,δ,s,H)五元组，其中K，∑，s和H都是像在普通Turing机的定义里那样，而转移函数δ是从(K-H)×∑

k到K×(∑∪{←,→})

k的函数。即，对每种状态以及带符号的每个K元组（a1,…,ak），δ(q,(a1,…,ak))=(p,(b1,…,bk))其中p像前面那样是新状态，bj在直观上是M在带j上采取的动作。自然，我们还坚持，若对某个j≤K

，aj=►,

则bj=

→.定理4.3.1

对某个k≥1，设M=(K,∑,δ,s,H)是k带Turing机。那么存在标准Turing机M’=(K’,∑’,δ’,s’,H)，其中∑⊆∑‘,使得下列关系成立：对任意输入字符串x∈∑*，M在输入x上停机并且在第一条带上有输出y当且仅当M’在输入x上在同样的停机状态里停机，并且在带上有同样的输出y。另外，如果M在输入x上在t步之后停机，那么M‘在输入x上O(t▪（|x|+t）)步之后停机。推论：

k带Turing机计算的任何函数或者判定、半判定的任何语言，也分别可用标准Turing机计算或判定、半判定。定义4.3.2设M=(K,∑,δ,s,H)是k带Turing机.M的格局是K×(►∑*×(∑*(∑-{⊥})∪{e}))k

的成员。即格局说明当前状态以及K条带里每条的带内容和带头位置。4.3.2双向无穷带Turing机

顾名思义：带是两个方向上的且在两个方向上是无穷的。

具体描述：Turing机的带在左右两个方向都是无穷的。除里面包含的输入的那些方格外，所有其余带方格起初都是空格。

关键点：标准Turing机中的►符号（左端符）在此类Turing机中是不必要和无意义的。

模拟实现：双向无穷带可用2带机器模拟实现，其中，一条带包含第一个输入符号所在方格右边的那部分带，另一条带用相反方向包含该方格左边的那部分带。这台2带机可用标准Turing机模拟（线性时间）。显然。有多条双向无穷带的也可以用同样的方式模拟。4.3.3多带头Turing机

顾名思义：一条带上不止一个带头，而是有多个带头与有穷控制器联接。

具体描述：允许在标准Turing机的一条带上扩充多只带头，每条带头都进行移动和写。

关键点：是否会造成不同的带头间冲突？避免此冲突的机制：让编号低的带头有较高的优先权。

模拟实现：类似于模拟k带机器那样实现。基本想法：把带划分成轨道，除第一条轨道外，所有其余轨道都专门用来记录多个带头位置。扫描2遍模拟多带头机一步计算：第一遍扫描发现所有带头位置上符号；第二遍扫描改变这些符号或适当地移动带头。

4.3.4二维带Turing机

推广思路：另一种推广是允许带是无穷的二维网格。注意：综上就是几种主要的Turing机模型的扩充方法。当然，这些扩充是可被组合起来的。可以设想：Turing机有多条带，所有的或是部分的带都是双向无穷的并且上面有多只带头，甚至可以是多维的。尽管如此，Turing机的根本能力还是保持原样。定理4.3.2

有多带、多带头、双向无穷带或多维带的Turing机，它们判定或半判定的任何语言以及计算的任何函数，都分别可用标准Turing机判定、半判定或者计算。4.4随机存取Turing机

4.4.1定义：随机存取Turing机

是二元组M=(k，Π)，其中K>0是寄存器的个数，Π=(Π1,Π2,…,Πp,)，即程序，Π是指令的有穷序列，其中每条指令Πi是书中图4-19所示类型之一。假设最后一条指令Πp总是halt指令。(程序也可包含其它的halt指令)

随机存取Turing机（k,Π）的格局是k+2元组(x,R0,R1,…,Rk-1,T),其中x∈N是程序计数器(0≤x≤p的整数)。若x是零，则格局是停机格局。对于每个j(0≤j＜k)，Rj∈N是寄存器j的值。T即带内容,是正整数有序对的有穷集。(i,m)∈T意味着第i个带方格当前包含整数m；i＞0，m＞0。不在T中有序对第一分量对应带方格都假定包含0。

参看书p137页图4-19

定义

(续)

设M=(k,Π)是随机存取机器。设C=(x,R0,R1,…,Rk-1,T)和C’==(x’,R’0,R’1,…,R’k-1,T’)是M的两个格局。若在直观上，x’与诸R’j和T’的值，正确的反映了把当前指令Πx的“语义”应用到x与诸Rj和T上的效果，则我们说格局C一步产生格局C’,表示成C├C’。注释:参考图4-19理解格局产生含义：若Πx形如readj，其中j<k,则这条指令的执行有下列效果：寄存器0包含的变成等于编号为Rj的带方格的值。即R’0=T[Rj]，其中若满足(Rj,m)∈T,则T[Rj]=m，否则它是0。另外，指令计数器x=x+1。格局C’的所有其余分量都与C相同。

产生关系├*M是├M的自反传递闭包。随机存取Turing机的判定工作上面讲述了随机存取Turing机的机制，下面将讲述其对输入的判定工作过程。定义4.4.2

字母表Σ满足︺∈Σ并且Σ。另外，设E是Σ和{0，1，…，|Σ|-1}之间的固定双射，这个双射是编码随机存取Turing机的输入和输出地方式。假设E（︺）=0。随机存取Turing机M=（k，Π）在输入=…上的初始格局是（k，，…，，T），其中k=1，对所有j，=0，并且T={（1，E（）），（2，E（）），…，（n，E（））}。若在输入字符串x∈∑*上的初始格局最后产生满足R0=1的停机格局，则我们说M接受x。若在输入x上的初始格局产生满足R0=0的停机格局，则我们说M拒绝x。换句话说，一旦M停机，我们就在寄存器0中读到判定结果：若这个值是1，则机器接受；若值是0，则它拒绝。设∑0∑-{︺}是字母表，并设L∑*0是语言。若每当x∈L，M就接受x；每当x∈L，M就拒绝x，则称M判定L。若下列关系为真：x∈L当且仅当M在输入x上产生某个停机格局，则称M半判定L。设f:∑*0∑*0是函数。若对于所有x∈∑*0，机器M在输入x上的初始格局产生停机格局，并且带内容是{(1,E(a1)),(2,E(a2)),。。。,(n,E(an)),}，其中f(x)=a1a2…an，则称M计算f。例4.4.2下面用缩写形式描述随机存取Turing机程序，他判定语言acount:=bcount:=ccount:=0,n:=1;WhileT[n]==1don:=n+1,acount:=acount+1;WhileT[n]==2don:=n+1,bcount:=bcount+1;WhileT[n]==3don:=n+1,ccount:=ccount+1;Ifacount==bcount==ccountandT[n]==0thenacceptelsereject;其中：假设E(a)=1,E(b)=2,E(c)=3,分别用变量acount,bcount和ccount表示迄今为止找到的a,b和c的个数。也用缩写accept表示“load=1,halt”，reject表示“load=0,halt”。

随机存取Turing机和基本Turing机等价的证明：

定理4.4.1

任何递归或递归可枚举语言，以及任何递归函数，分别可用随机存取Turing机判定、半可判定和计算。

（注：随即存取Turing机→基本Turing机）定理4.4.2

随机存取Turing机判定或半判定的任何语言，以及随机存取Turing机计算的任何函数，分别可用标准Turing机判定、半判定和计算。另外，如果随机存取机器在输入上停机，那么标准Turing机所花费的步数不超过随机存取Turing机在同一个输入上步数的多项式。（注：随即存取Turing机←基本Turing机）4.5非确定性Turing机

（这里，├M产生不必是单值的，一个格局可以在一步里产生多个其它格局）定义4.5.1

设M=（K,∑,△,s,H）是非确定型Turing机。若对输入ω∈(∑-{►，︺})*，对某个h∈H以及a∈∑,u,v∈∑*，(s,►︺ω)├*M（h,uav）,则我们说M接受ω。注意：即使非确定型Turing机在输入上有许多非停机计算，只要存在一种停机格局即可。若对语言L∈（∑-{►

，︺}）*，对所有ω∈(∑-{►

，︺})*，下列关系成立：ω∈L当且仅当M接受ω，则我们说M半判定L。定义4.5.2：设M=（K,∑,△,s,{y,n}）是非确定型Turing机。设L(∑-{►，︺})*是语言，若对任意ω∈(∑-{►，︺})*，下列两个条件成立：(a)存在自然数N，它依赖于M和ω，使得不存在任何格局C满足(s,►

︺ω)├NMC。---最多N步就停机，即N步内停机。

(b)ω∈L当且仅当对某个u,v∈∑*，a∈∑，(s,►︺ω)├*M（y,uav）。则我们说M判定L。设f:(∑-{►,︺})*→(∑-{►,︺})*是函数，若对所有ω∈(∑-{►,︺})*，下列两个条件成立：

(a)存在N，依赖于M和ω，使得不存在任何格局C满足(s,►︺ω)├NMC(b)(s,►︺ω)├*M（h,uav）当且仅当ua=►︺,并且v=f(ω)。则我们说M计算f。存在非确定型Turing机等价的确定型Turing机：定理4.5.1

如果非确定型Turing机M半判定或判定语言L，或者计算函数f,那么，存在标准型Turing机M’半判定或判定语言L，或者计算函数f。证明：用多带Turing机可构造性证明之。略。4.6文法定义4.6.1

文法（或无限制文法，或改写系统）是四元组G=(V,∑,R,S）其中：V是字母表； ∑⊆

V是终结符集，V-∑称为非终结符集；

S∈V-∑是起始符；并且

R，即规则集，是（V*（V-∑

）V*

）╳V*

的有穷子集。若(u,v)∈R，则可写成uv；u=>Gv

当且仅当对于某些w1,w2∈V*以及某条规则u’v’∈R,u=w1u’w2并且v=w1v’w2。

=>*G是=>G的自反传递闭包。字符串w∈∑*是G生成的当且仅当S=>*Gw;G生成的语言L(G)是G生成的所有串的集合。

推导：形如w0=>Gw1=>G。。。

=>Gwn的序列。定理4.6.1

语言被文法生成当且仅当它是递归可枚举的。

证明：仅当---利用多带机模仿文法推导；当---用Turing机模仿归约。定义4.6.2(函数f与文法G可计算)

设G=(V,∑,R,S)是文法，并设f:∑*|->∑*是函数。若对所有w,v∈∑*

，下列关系为真

SwS=>G*v当且仅当v=f(w)

即，包括输入w和两侧的G的起始符的字符串恰好生成∑*里一个字符串：f(w)的正确值，则我们说G计算f

。函数f:∑*|->∑*称为是文法可计算的当且仅当存在计算它的文法G定理4.6.2函数f:∑*|->∑*是递归的当且仅当它是文法可计算的。4.7数值函数（数值函数的构造）原始递归函数

定义4.7.1

对任意k≥0，定义从Nk到N的基本函数如下：

a）对任意k≥0，k元零函数定义为:

对所有n1,…,nk∈N，zerok(n1,…,nk)=0;b）对任意k≥j>0，第j个k元恒等函数定义为:

对所有n1,…,nk∈N，idk,j(n1,…,nk)=nj;c）后继函数定义为:

对所有n∈N，succ(n)=n+1两个简单的组合方法：(把函数组合成稍微复杂的函数)(1)设k,l≥0，g:Nk-->N是k元函数，h1,…,hl都是l元函数，则g与h1,…,hl的合成是由

f(n1,…,nl)=g(h1(n1,…,nl),…,hk(n