有限自动机理论CH.ppt

《有限自动机理论CH.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论CH.ppt（332页珍藏版）》请在三一办公上搜索。

1、第六章 图灵机,接收能力最强的自动机 图灵机(即TuringM-TM)。由A.Turing于1936年提出。,TM是可计算性的数学模型 研究可计算性(可计算的特点是 有穷、离散、机械执行、停机)。为计算机的发展奠定了理论基础。,图灵机可以模拟现代的计算机的计算能力。使用图灵机可以解决计算机程序的可计算问题。图灵机的构造技术类似于计算机的编程(设计指令)技术。,6.1 图灵机的基本模型,6.1.1 图灵机的定义,图灵机的物理模型,a1,a2,a3,aj,an,an+1,FSC,一个有限状态控制器(FSC)一个外部的存储设备 可以向右扩展的无限长度带 带上具有左端点，使用“”表示图灵机直接扫描输入

2、带上左端点右边的第一个符号。,带分解为单元，每个单元可以为空(B)或存放字母表上的字母符号 有限状态控制器通过一个读/写头与带进行耦合。带的右边用B标记带的右期间。,在某个时刻，有限状态控制器处于某个状态，读/写头将扫描带上的一个单元 依照状态和扫描到的带上符号，图灵机将有一个动作如下：,有限状态控制器的状态进行改变；把刚刚扫描过的单元上符号擦除掉，并印刷上一个新的符号（有可能印刷上与原来符号相同的符号）；读/写头向左或者向右移动一个单元；或者读/写头不移动。,五元式描述动作,其中：x，W 图灵机处于状态q，扫描到符号x，则状态变换为q，印刷上新的符号W，读/写头向左、或向右 或不移动。,例6

3、-1 用TM接收,语言a2n|n0,图灵机带上符号串为：aaaaaaB 图灵机初始处于状态even，将要扫描第一个a，则,/可省略,若带上a的个数为偶数，则图灵机经过多个动作后，处于接收状态accept；,若带上a的个数为奇数，根据，图灵机将不会停机，可以永远继续下去 这与其它的自动机不同，即图灵机可能会导致永不停止的计算。,例6-2 语言为a2n|n0,定义6-1 图灵机是一个五元式,TM=(Q，q0，q，)Q是有限状态集合；是带上字母表的有限集合=BA；的增广集合，即输入带上符号的集合,q0Q，是开始状态qQ，是接收状态,:QQL,R,N对于任意的(q，x)Q(q，x)=(q，W，L，R，

4、N)将记为一般形式：,或 图灵机是一个七元组,TM=(Q，q0，B，F)F Q 终止状态集合；是带符号集合；B 称为空白符；:Q Q R,L,N,定义6-2 图灵机的格局ID,w1qw2w1是读/写头左边带上的符号串q是图灵机当前所处的状态w2是还未扫描到的带上的符号串,()*Q()*,图灵机在格局w1qw2时停机若w1qw2=w1qxw对于 无定义。,(q，x),?,定义6-3 格局的转换,若M在w1qw2上不停机，则如下定义格局的转换：某个时刻，图灵机处于格局w1qw2=r1yqxr2，其中：r1y=w1，(若w1=，则y=B，r1=)xr2=w2，(若w2=，则r2=，x=B),使用=表

5、示图灵机的格局转换,若（q，x）=(q，x，L)，则 r1yqxr2=若（q，x）=(q，x，N)，则 r1yqxr2=若（q，x）=(q，x，R)，则 r1yqxr2=,r1qyxr2,r1yqxr2,r1y xqr2,使用=+代表格局的多次变换使用=*代表格局的任意次变换,定义6-4,图灵机M=（Q，q0，q，）在字母表上接收的语言为L(M)，则 L(M)=w|存在w1，w2()*有=*,q0w,w1qw2,定义6-5 完全的图灵机,如果图灵机对于一切输入串都能够停机-完全的图灵机。完全的图灵机接收的语言L称为递归语言(图灵可判定语言),6.1.2 图灵机的构造,例-接收仅有一个1的0、1

6、串TM=(q0，q1，q2,0，1,q0，q2,),=0，1，B,q1，B?,例6-4 构造图灵机,接收语言 anbn|n0,思路：,当图灵机遇到a时，将a改写为#向右寻找b，找到b，将b改写为#再向左找a 直到所有a都找完。(向左找的a是整个a串最左边的a),指令为,读到一个a，用#代替它，向右找b,处于状态del_b，扫描到b，用#代替它，向左寻找a，（从重复循环）/最右的a,seek_a状态时，没有再发现a(都已被#所代替)，还需要检查是否所有的b都已经被扫描过。,问题,该图灵机能接收anbn的所有串 但该图灵机也能接收aababb 等 原因：使用#代表已扫描的a和b 没有保证a和b的顺

7、序。,为了区别原来的字母a和b 使用#和$分别代替字母a和b 当a和b都识别后，带上的串为#$B,例6-5 修改上例：,读到一个a，用#代替它，向右寻找b,处于状态del_b，扫描到b，用$代替它，向左寻找a，（从重复循环）,在seek_a状态时，没有再发现a（都已经被#所代替）需检查是否所有的b都已经被扫描过 还必须注意#与$的顺序。,例6-6 anbn|n0的第二种算法,当图灵机遇到a时，将a改写为#向右寻找b，找到b，将b改写为$再向左找a(此时的a是整个a串最左边的a)，直到所有a都找完。,指令,读到一个a，用#代替它，向右寻找b,处于状态del_b，扫描到b，用$代替，向左寻找a，（

8、从重复循环）/跳过a串/最右#/最左a,在seek_a状态时，没有再发现a，需检查是否所有的b都已经被扫描过。,思考,比较对于相同的输入串，两种算法的图灵机的指令数量、每条指令的执行次数（总次数）；能否给对图灵机的性能进行评价？,例6-7 anbn|n0第三种算法,思路:首先检查输入串是否为a+b+的格式；如果不是，则拒绝该串 如果是，检查a和b的个数是否相等。,指令,(扫描a)(扫描b),(开始检查a和b的个数是否相等),已经保证顺序,（检查是否有多余的b）,例6-8接收语言 anbncn|n0,TM=（Q，start，accept，）Q=start，del_b，del_c，seek_a，c

9、heck1，check2，check3，accept=a，b，c=a，b，c，B，#，$，!,指令,读到一个a，用#代替它，向右寻找b,处于状态del_b时,扫描到b，用$代替它，向右寻找c：,处于状态del_c时，扫描到c，用!代替它，向左找a，(从开始又重复循环),在seek_a状态时，没有再发现a（都已经被#所代替）还需要检查是否所有的b和c都已经被扫描过 注意#、$和！的顺序,识别第一个!跳过剩余!,类似地，图灵机接收语言 anbncn|n0，也有多种方法。,思考：,构造TM接收语言aibjci+j|i,j0构造TM接收语言aibjci*j|i，j0构造TM接收语言wcwT|w(a,b

10、)*,6.2 图灵机作为非负整数函数计算模型,设有k元函数f(n1，n2，nK)=m 如果TM接受输入串 0n110n2110nk而“输出”符号串 0m,则称TM计算k元函数f；或称f为TM计算的函数。也称f是图灵可计算的。但当f(n1，n2，nK)无定义时，TM 没有适当的输出。,自动机都具有识别语言的功能 图灵机还具有“计算”功能 可以规定非负整数的表示方法,从而实现非负整数的函数求值。,使用“一进制”方式表示一个非负整数，即 使用0m表示整数m。若需要计算f(m，n)，则可以在输入带上存放0m10n形式的串图灵机将串改写为0f(m，n)的形式，即表示出计算f(m，n)的结果。,加法图灵机

11、,对于非负整数n、m，计算n+m。,分析,图灵机输入0n10m 需要输出0n+m算法：将1改写为0，最后一个0改写为B(可能是1改写成的0),TM=（Q，,start，accept，）Q=start，q1，q2，accept=0，1=0，1，B,指令,串为1或10m 第1个0 跳过剩余的0 遇到1，改为0 遇到B，向左找0最后的0改为B,注意,扫描1左边和右边的0的工作都由 完成。整个串只允许一个1。,例6-16 构造TM,实现非负减法(真减法)m n=m-n mn=0 mn(即全是B),或,思路1,带上字符串的形式为0m10n寻找1左边的0，删除1右边的0 可能在寻找1左边的0时结束(mn)

12、或者在删除1右边的0时结束(mn),(1)扫描第1个0(2)/原标记的1(3)/将1后的第1个0变为1/后加的,strat,1,q2,B,(4)向左找0 读写头位置 转（1）重复上述动作,?,mn,(5)/遇到最右边的B，表示1右边已没有0 将1改写为B 补写1个0，结束,m n,(6)start将遇到第一个1 将后面1改写为B 将后面0改写为B 结束此时，输入带上全为，表示,mn,在第(5)步开始时，输入带上的字符串形式为：BBBB000011 11B m-n-1个 n个 左边B有n+1个。,mn,根据TM的动作，在左边消除一个0，再去1的右边找0 当发现1的右边已经没有0时，此时减法工作应

13、该结束,mn,但左边多消除了一个0 因此，第（5）步，在q4的的控制下除了将1改写为B外 还应该将一个0补写回来，才能结束减法工作。,mn,此时，输入带上的字符串形式为：BBBB0000 B m-n个,m=n时，整个减法的结果应该为0输入带全为,B,特殊：m=n=0，则串为1BB 结束,思路2 自学,图灵机反复进行下面的工作：先用B替换1左边领头的0 向右搜寻1右边的第一个0，并将这个0替换为X，然后左移到B。重新开始循环。,退出循环的条件有两种：1)1的左边找不到0，说明mn 输出0，应将所有非B符号改写为B；2)1的右边找不到0，说明mn 输出0m-n，应将1换为0，将X换为B。,状态转换

14、函数为：(1)开始循环，用B替换1左边领头的0(2)向右搜寻1。,(3)向右寻1右边的第一个0,并将这个0替换为X,(4)左移到B，重新开始循环。,(5)符合退出条件1)，即1的左边找不到0，用状态q4向右扫描将所有非B符号改写为B，并进入终止状态q6,(6)符合退出条件2)，即1的右边找不到0，用状态q5向左扫描将所有X改写为B，将1替换为0，并进入终态q6/1换为0,6.3 图灵机的构造技术,构造TM，就相当于编写一个程序(指令或规则的组合)。本节介绍的图灵机的一些构造技术，这些技术具有一般性，对于图灵机的构造(程序设计)具有较大的意义。,6.3.1 图灵机的存储技术,例6-12 构造TM

15、，识别字母表 a,b,c上的语言L：每个字符串的第一个符号在该串中仅仅出现一次。,思路：,要求：第一个符号仅仅出现一次 图灵机可以“记住”输入带上的第一个符号（a或b或者c）。,使用二元式表示状态 第一个分量仍然表示原来的状态；第二个分量存储带上的第一个符号。q，a、q，b和q，c分别代表输入串的第一个符号为a、b和c的状态。,(1)扫描第一个符号，并存储,(2)第一个符号是a,(3)第一个符号是b,(4)第一个符号是c,结束,(5)遇到最右的B，接收该串,注意,直接运用规则（1）和（5）可以接收 仅仅只有一个符号的输入串。,例6-13 构造TM，识别,a，b，c上的语言L：每个句子的最后一个

16、符号在该串中仅仅出现一次。,思路1：,最后个符号仅仅出现一次 TM先将读/写头移动到带的最后“记住”输入带上的最后一个符号 向左扫描输入带上的其他符号 与最后一个符号进行比较,x=a,b,c,(1)将读/写头移动到带的最后,start,B?,(2)存储最后的符号,向左扫描输入带上的其他符号遇到结束,思路2：,TM需要存储已经出现过的符号 为了识别输入带上的最后一个符号，图灵机还需要存储当前扫描的符号，以便确定最后一个符号。,使用三元组表示单个状态,第一个分量仍然表示原来的状态；第二个分量是已经出现过的符号的串(ab、ac或bc)第三个分量表示上一次扫描的符号。,如q，ab，a 代表输入带上的字

17、符已经出现过a和b上一次扫描的符号为a。具体指令 略,思考：构造TM,该语言的每个句子的(倒数)第n个符号 在该串中仅仅出现K次。n=1，2，3，；K=1，2，3，,图灵机的移动技术,在解决比较复杂的问题时 TM需要将输入带上一组连续的非空符号左移或者右移若干个单元。使用n元式存储多个符号 直到某个阶段再将这些符号印刷到需要的位置上。,例6-14构造TM,=a,b,c，将输入串右移两个单元 使用三元组q，a1，a2表示状态 q表示原来的状态；a1、a2可以代表a、b、c。,设串长度=3,(1)扫描第一个符号，并存储(2)扫描第二个符号，并存储(3)将a1放在a3位置,将a3存储,(4)将倒数第

18、二个符号放在右边空白单元，将最后一个符号存储在状态中(5)将最后一个符号放在带上,其中规则(3)需要重复多次使用。,本例使用三元组表示特殊状态 也可以使用二元组表示特殊状态 如q，a1，a2可以记为q，a1a2（n元组也可以表示为二元组）,对带上符号进行移动,一般只是比较复杂的TM的识别任务中的一部分工作 移动本身不会涉及到串的接收或拒绝问题 复杂的TM可以继续从end_move状态开始其他的工作,思考：构造TM,将整个输入串前两个符号删除。,思路,将带上符号从右向左移动两个单元。,例6-15构造TM,输入字母表为0，1 在输入串的开始处添加子串10。略。,例6-16构造TM,=a，b，c 将

19、整个串包含的第一个abc子串删除。,思路,存储技术寻找到第1个abc子串的位置 将后面的符号向左移动三个单元。略。,例6-18,构造TM，输入字母表为0，1，要求M接收语言L：该语言的每个字符串包含且仅只能包含一个101子串(有且仅有一个101，不可以没有101子串）,思路,当识别出第一个101后，检查输入带上剩余的串 不能再包含10110101,？,TM=（Q，start，accept，）Q=start，q，0，q，1，q，10，check，check，0，check，1，check，10，refuse，accept=0，1=0，1，B,(1)扫描第一符号 空串,(2),(3)已经扫描到“1

20、”，等待可能的“0”(4)已经扫描到“10”，等待可能的“1”,(5)已扫描到101，检查串的剩余部分,(6)(7),（8）的第2条指令与（9）可以省略,(8)(9)整个输入串中没有101,结束,(10)整个输入串只有一个101,思考,构造TM，接收语言L：该语言的每个句子必须包含两个101,例6-19,构造TM，接收语言L：该语言的每个句子最多只能包含一个100子串（可以没有100子串）。,思路,接收1个100子串的所有串；接收没有100子串的所有串。,例6-23 构造TM,接收语言L：该语言的每个句子不包含子串100。,思路,当识别出第一个100后，就拒绝。,6.3.3 图灵机扫描多个符号

21、技术,略,图灵机的多道技术,为了能够保存和处理更复杂的数据，可以将TM的输入带划分为若干道在各道上可以存放不同的符号。,没有改变图灵机的基本模型，只是将带上符号当做一个向量的组合每个符号可以是一个K维向量（将输入带划分为K道）。,单带K道的图灵机,状态转换函数,一般形式为 对于K道图灵机一次需要扫描一个符号的多道,思考,二进制的加法考查第3题,例6-24:构造图灵机,字母表为a 接收语言L：an|n=0，且n为完全平方数,基本数学公式：(n+1)2=n2+2n+1,思路,使用三道的图灵机 第一道存放输入串；第二、三两道作为“运算器”使用。,初始时,从i=0开始 在第二道上放i2个a 比较第一道

22、与第二道上a的个数 如果相等，就接收；,不相等，则在第三道上设置(计算)出 2*i+1个a，将第三道上的a加入到第二道上去，从而，在第二道上形成(i+1)2个a 再与第一道上a的个数进行比较。,初始 i=0 第2道a个数为02,aaa aB n个aBBBB 02=0BBBB,第3道设置为2*0+1,aaa aBBBBB 02aBBB 2*0+1,第2道设置为12 i=1,aaa aBaBBB 12aBBB,第3道设置为2*1+1,aaa aB naBBB 12aaaBB 2*1+1,第2道设置为22 i=2,aaa aB naaaaB B 22aaaBB,第3道设置为2*2+1,aaa aB

23、naaaaB.B 22aaaaaBB 2*2+1,第2道设置为32 i=3,aaa aB naaaaaaaaaB.B 32aaaaaBB,第3道设置为2*3+1,aaa aB naaaaaaaaaBB 32aaaaaaaBB 2*3+1,第2道设置为42 i=4,aaa.aB naaaaaaaaaaaaaaaaBB 42aaaaaaaB.B,上述动作一直重复下去，直到第一、二道上a的个数相等，则接收；或者第一、二道上a的个数不相等则拒绝该输入串。,从i=2过渡i=3到时，图灵机输入带为：,TM=（Q，start，accept，）Q=start，q1，,q9,refuse,accept=a=a，

24、B,(1)对于两种特殊情况：n=0或者n=1，进行处理,(2)i=0：准备工作 在第三道上放一个a,(3)计算(i+1)2其中：x，ya，B,将第道的a复制第2道的a的后面向左找复制标志b或,建立新标志(i=0)/在第三道上放b为新标志,其中：xa，B,在第二道上复制一个a,其中：xa，B,(4)计算2(i+1)+1，为下次做准备(实际上,在第3道每次增加2个a)仅当输入串为a4和 a9时(i2=2*i),其中：x，ya，B,(5)比较第一道和第二道上a的个数/第一道上a的已经查完,其中：x a，B,仅当输入串为a4和 a9时(i2小于2i)第二道的a少于第一道的a，继续扫描,(6)拒绝情况(

25、可省略)第二道的a多于第一道上的a，停机 第一道上已经没有a，停机,图灵机的查讫技术,在TM的工作中，有时需要对已经扫描过的符号进行检查。为了区分带上的某个符号是否已经检查过，可以使用查讫符号“”进行标记 需要使用多道技术存储查讫符号,初始时，所有带上符号的查讫标记都标记为“B”。,例6-25 构造TM,L(M)=w2w|w0，1+,分析,依次比较2前后的符号 将带分成两条道 第一条道上存放输入符号串 第二条道上存放检查标记。,初始,输入带上的符号情况为：a1a2 an 2 b1 b2 bm B B B B B B B B B,比较时，使用存储技术，将符号“2”前面的待比较符号存储，再与2后面

26、相应位置的符号进行比较。,某个时刻，输入带上的符号情况 a1a2 an 2 b1 b2 bm B B B B B B,M的初始状态为start令a=0或1，b=0或1,记录待比较符号：,读头右移到2的后面：找到要比较的位置：,比较后相同则继续：2个a必须同为0或1,读头左移到2前：,读头左移过2后有两种情况,未比较完 已比较完,未比较完时读头左移到待比较符号：,已比较完则看右边是否处理完：,图灵机的子程序技术,与通常的程序设计技术相似 子程序的思想在TM的构造中也是十分重要的技术。,子程序技术的使用，可以将复杂的问题进行分解（化简），同时，也可以将TM的构造“模块化”TM的子程序技术的基本思想

27、是将TM中需要重复使用的功能分解出来，作为一个子程序。,完成整个功能的图灵机为M（作为主程序对待）完成某个特定功能的图灵机为M（即子程序作为某个小的图灵机）,图灵机M从状态q开始到一个固定的状态f结束状态q、f是图灵机M的两个一般状态,当图灵机M进入状态q时，就启动M（相当于调用子程序）；当M进入状态f时就返回到M（相当于子程序结束）。,注意：,图灵机M中可以有多个状态 但仅有两个状态（即M的开始状态q和接收状态f）是与主程序的图灵机M共用的 图灵机M的其他状态是私有的，不能被主程序的图灵机M所使用。,例6-26,构造TM，完成正整数的乘法运算。正整数的乘法运算的数学公式：mn=(1+1+1)

28、n m个1,使用TM实现正整数的乘法运算 TM的输入带上存放串0m10n，运算后，使得带上的串变为0m*n形式,TM处理该问题的最一般的方法为：当从1的左边消去一个0后，应该在0n的后面增加n个0(补1作为分隔标记)；当1左边的所有的0（共有m个）消完后，再消去多余的符号（两个1和原来的0n），就得到了0m*n形式。,在0n后面添加n个0的过程是重复的，可以使用子程序技术。,在某个时刻，TM输入带上的符号为：Bh0m-h10n10h*n完成(1+1+1+1)*n h个,M的状态函数分为3部分：,1)初始化：将第一个0变为B，并在最后一个0后面设置标记为1 该标记表明了增加0的开始位置 使得增加

29、的0在第二个1的后面；并将读/写头移动到n个0中的第一个处。,则格局变换为：q00m10n=*B0m-11q10n1,注意,此时，只是消去了第一个0 设置标记1；但还没有在后面增加0 即将扫描原来0n的第一个0,2)主控程序：初始化后，状态变为q1。q1相当于子程序图灵机的开始状态，进入子程序，将n个0增加到第二个1的后面。,当退出子程序时，状态为q5（q5也就是子程序图灵机的结束状态）此时需要将读/写头移动到前面m个0中剩余0的第一个处 并将这个0改为B，准备进入下次循环,对应的格局转换为：,Bhq00m-h10n10(h-1)*n=*Bh0m-h1q10n10(h-1)*n 进入子程序=*

30、Bh0m-h1q50n10h*n=*Bh+1q00m-h-110n10h*n,当找不到前面m个0中剩余的0时，表示乘法计算工作已经结束，需要消去多余的符号（两个1和原来的0n），得到最后的结果串。对应的格局转换 Bmq810n10m*n=*Bm+n+1+1q140m*n其中，状态q14是接收状态,3)子程序：将n个0增加到原来0n的后面。子程序TM从它的开始状态q1启动，进入接收状态q5时完成一次工作，并返回到主控程序。,进入图灵机子程序时，输入带上符号串的形式情况及读/写头位置为：Bh0m-h1000010(h-1)*n q1 读/写头指向0n的第一个0,子程序对应的格局转换为：Bh0m-h

31、1q10n10(h-1)*n=*Bh0m-h1q50n10h*n,整个图灵机的格局转换情况：初始化：q00m10n=*B0m-11q10n1,主程序和子程序：,Bhq00m-h10n10(h-1)*n=*Bh0m-h1q10n10(h-1)*n 主程序消除0Bh0m-h1q10n10(h-1)*n=*Bh0m-h1q50n10h*n 子程序增加0nBh0m-h1q50n10h*n=*Bh+1q00m-h-110n10h*n 主程序消除0,Bmq810n10m*n=*Bm+n+1+1q140m*n 主程序消除多余符号,初始化(不止执行一次)：,/在最后增加标记1,控制在串的最后只能放一个1 此时

32、，将扫描原来0n的第一个0,子程序：,将0标记为2，以方便复制0n 向右寻找B 遇到标记1（第二个1）复制一个0,向左寻找0n中剩余的0（寻找标记2）准备复制下一个0 n个0都已复制,将2恢复为0 子程序结束，读/写头仍然在0n的第一个0处,主程序：,上一次循环结束，本次循环开始,m个0都消完，循环结束,消去多余串10n1:,此时，图灵机带上的符号形式为：Bm+n+1+10mn,图灵机共有15个状态，其中：子程序图灵机使用了5个状态：q1、q2、q3、q4、q5 主程序图灵机使用了12个状态：q0、q1、q5、q6、q7、q8、q9、q10、q11、q12、q13、q14,教学活动结束,谢谢！

33、,丘奇-图灵论题,在研究可计算性问题时一种观点认为：对于任何输入，算法都应该能够终止 否则，只能称其为(计算)过程。,根据这个观点，对于某些输入不能够停机的图灵机就不能够称为算法，也就是说，如果某个图灵机使用永不停机的方式表示对某个输入串不能够接收的话，该图灵机就不是算法；而只有对任何输入都必定停机的图灵机，才称为算法。,或者说，接收递归语言的图灵机是算法，接收递归可枚举语言的图灵机不一定是算法。另一种观点则忽略停机问题，从而扩大了可计算问题的范围。,丘奇图灵论点是递归论中最重要的基本结论。递归论又称可计算性理论，它是研究计算的一般性质的数学理论。,其中心问题是：计算的本质是什么?哪些问题是可

34、计算的?哪些问题是不可计算的?不可解的程度如何?这些问题经过长期的探索，终于在本世纪30年代由于递归论的建立而得到了确切地解决。,递归论的建立首先得益于哥德尔等人关于原始递归函数的提出。所谓原始递归函数是指由初始函数出发，经过有限次的代入与原始递归式而做出的函数。,1934年哥德尔在他人的启示下，又提出了一般递归函数的概念。一般递归函数就是由初始函数出发，经过有穷次使用代入、原始递归式和m算子而做成的可定义函数。,同时，数学家丘奇、克林也提出了一类可计算的叫做l可定义的函数。事隔不久，丘奇、克林就分别证明了l可定义函数正好就是一般递归函数，即这两类可计算函数是等价的、一致的。,在这一有力的证据

35、基础之上，丘奇公开发表了他早在1934年就孕育过的一个论点 即著名的丘奇论点：每个能行可计算的函数是一般递归的。,也就在1936年，数学家图灵定义了另一类可计算函数图灵可计算函数，并且提出了图灵论点：能行可计算的函数都是用图灵机可计算的函数。一年后，图灵进一步证明了图灵可计算函数与l可定义函数是等价的,当然也和一般递归函数是等价的。于是这三类可计算函数实际上就是一种。这样一来，丘奇论点和图灵论点也就是一回事了。现统称为丘奇图灵论点。,至此，人们便把直观的能行可计算函数归结为一般递归函数了。对可计算性的实质有了清楚的认识。,丘奇-图灵论题（又称为丘奇假说）：对于任何可以用有效算法解决的问题，都存

36、在解决此问题的图灵机。,对于计算机科学，丘奇图灵论点的意义是很直接的，它明确刻画了计算机的本质或计算机的计算能力，确定了计算机只能计算一般递归函数。对于一般递归函数以外的函数，计算机是无法计算的。可以说，递归性是使用计算机的前提。,丘奇图灵论点常常又被说成：凡可计算的函数都可用计算机计算。当然，这是从理论意义上来讲的。从现实意义上讲，计算机还有一个现实可计算性的问题。不过这是由另一门学科计算复杂性理论来研究的。,描述算法有三种基本方式：形式描述、实现描述和高水平描述。形式描述需要详细给出图灵机的状态定义，转换函数的定义，是最详细程度的算法描述；,实现描述通常使用自然语言来描述图灵机的动作，如读

37、/写头的移动，怎样存储数据等，不需要给出具体的状态转换函数的描述；高水平描述采用自然语言描述，忽略了图灵机的实现模型，即通常意义上的算法描述。,6.5 通用图灵机,图灵机是一个算法的实现装置。直观地，一台通用的计算机，如果不受存储空间和运行时间的限制的话，它应该能够实现所有的有效算法。按照丘奇-图灵论题，图灵机应该是现代计算机的形式化的模型。,6.4 图灵机变型(略),上面介绍了最基本的图灵机极其图灵机的构造技术，本节从不同的方面对图灵机进行扩充，包括双向无穷带图灵机、多带多读写头图灵机、不确定图灵机和多维图灵机等。为了区别扩展的图灵机，上面介绍的单向无穷带图灵机，称为基本图灵机。,与基本的图

38、灵机相比，它们都在不同的方面进行了扩展，但它们仍然与基本的图灵机是等价的。对基本的图灵机进行扩展，使得构造复杂的图灵机变得更加简便和容易。,由于这些扩展实际上都是技术上的一些改进，而且它们的基本描述相对都比较复杂，在本书中，将致力于基本思想和基本方法的介绍，而忽略那些比较烦琐的描述，包括一些形式化的描述。,这与本书前面的较为严格的论述不同。但是，根据基本思想和基本方法的介绍，读者较容易给出相应的形式化的描述和严格的证明，只不过这些形式化的描述和严格的证明，比较烦琐而已。,6.4.1 双向无穷带图灵机基本的图灵机的模型中，输入带上规定有左端点。所以，对于基本的图灵机，读/写头是不能够向左移动出该

39、左端点的。,对基本图灵机取消左端点的限制，得到双向无穷带图灵机，双向无穷带图灵机的输入带向左和向右都是无限的。输入带上所有空单元（包括左边和右边，全部标记为B）。,双向无穷带图灵机，读写头可以向左或向右任意移动，其他定义与基本图灵机的一致。,定理6-2 如果语言L能够被一个双向无穷带图灵机所接收，则该语言L也能够被一个单向无穷带图灵机（即基本图灵机）所接收。,6.4.2 多带多读/写头图灵机 基本图灵机的另一个重要的扩展是双向多带多读/写头图灵机。这种双向的多输入带图灵机具有多条双向的无穷输入带，每一个输入带都有自己的读/写头。,在每一个动作中，图灵机根据当前的状态以及每个读/写头正在扫描的带

40、上符号确定图灵机的下一个状态，并且各个读/写头可以相互独立地向各自希望的方向进行移动。,双向多带多读/写头图灵机简称为多带图灵机(multi-tape Turing machine)。将具有K条输入带的图灵机简称为K带图灵机(K-tape Turing machine)。,多带图灵机的一个动作可以描述为：1)改变图灵机当前的状态；2)在各自的输入带上印刷一个符号；3)各个读/写头向各自希望的方向进行移动。,K带图灵机的状态转换函数的形式为：(p，(X1，X2，X3，Xk)=(q，Y1，D1，Y2，D2，Y3，D3，Yk，Dk),定理6-3,多带图灵机与基本图灵机等价。证明：由于基本图灵机是多带

41、图灵机的一个特例，所以，只需要证明：对于任意一个多带图灵机，都有一个与之等价的基本图灵机。略。,6.4.3 不确定图灵机,对于前面介绍的图灵机是一个五元式，TM=(Q，q0，q，）；其中：是QQL，R，N的状态转换函数：（q，x）=(q，W，L，R，N)称该图灵机是确定的图灵机。,对于一个给定的状态和读入符号，确定的图灵机只能有一种可选动作。确定有限状态自动机DFA可以向非确定有限状态自动机NFA的进行扩展，类似地，确定的图灵机也能够扩展为非确定的图灵机。,定义6-7,图灵机M称为不确定的图灵机（或非确定的图灵机），除状态转换函数的定义外，它的其余部分的定义同确定的图灵机。即对于某个状态q和扫

42、描到的带上符号x，图灵机可能有多个动作（即M的状态转换函数可能将Q映射到QL，R，N的一个子集上）。,不确定的图灵机是一个五元式，TM=（Q，q0，q，）；其中：Q是有限状态集合；是带上字母表的有限集合，用=UB代表的增广集合；q0Q，是开始状态；qQ，是接收状态；,是Q2QL，R，N的状态转换函数，即对于任意的：（q，X）Q，（q，X）=(q1，Y1，D1)，(q2，Y2，D2)，(qn，Yn，Dn),定义6-8,不确定图灵机M=（Q，q0，q，）在字母表上接收的语言为L(M)，则L(M)=w|w*，且存在w1，w2()*，有q0w=*w1qw2。,对于不确定图灵机M，一方面可以认为，对于给

43、定的输入串，M能够自动地选择一系列正确的动作，使得M能够最终进入接收状态，即不确定的图灵机M具有具有一定的“智能”。,另一方面，由于处理一个输入串的所有可能的动作系列都是可以逐个列举的，所以，对于任意的输入串，可以让不确定的图灵机M逐一地按照当前列举出的动作系列去处理该输入串，,如果该输入串是不确定图灵机M所能够识别的串（即该输入串是不确定图灵机M接收语言的句子），则M最终能够执行接收该输入串的动作系列，不确定图灵机与确定图灵机的等价性证明就是基于这一思想的。,定理6-4,若语言L能被不确定的图灵机所识别，则存在确定的图灵机M，有L(M)=L。证明：需要证明，对于任意一个不确定的图灵机，都存在

44、一个与之等价的确定的基本图灵机。,定理6-5不确定的图灵机和确定的图灵机是等价的。证明：略。,6.4.4 多维图灵机前面接触过的图灵机的输入带都是一维的。也就是说，图灵机的输入带要么是只可以向右无限延长的，要么是只可以向左或向右无限延长的，因而，图灵机的读/写头只能够向前或向后进行移动。,现在，将图灵机的输入带扩展为多维的，这种图灵机的读/写头可以沿着多个维移动，该图灵机称为多维图灵机（multi-demensional Turing machine）。,如果图灵机的读/写头可以沿着k维移动，该图灵机称为k维图灵机（k-demensional Turing machine）。k维图灵机可以转换

45、为一维图灵机。,6.4.5 其他图灵机1 多头图灵机多头图灵机(multi-head Turing machine)是指图灵机只有一条输入带，但有多个读/写头。,多头图灵机的多个读/写头，统一地受图灵机的状态控制器的控制。多头图灵机根据当前的状态和多个读/写头当前扫描的多个字符，确定当前多头图灵机的一个动作。,在多头图灵机的一个动作中，各个读/写头在输入带上所印刷的新符号和所移动的方向都可以是相互独立的。如果多头图灵机有K个读/写头，该图灵机称为k头图灵机（k-head Turing machine）。,定理6-6 多头图灵机与基本图灵机等价。证明：,2离线图灵机离线图灵机(off-line

46、Turing machine)是一种多带图灵机，但对于其中一条输入带，只能读，不能印刷上符号（即不能写）。,通常使用符号和标记离线图灵机的只读输入带的左、右端点，只允许离线图灵机的读/写头在和标记的区域内来回进行移动。,离线图灵机实际上是多带图灵机的一个特例。如果只允许离线图灵机的读/写头从左向右进行移动，称这种离线图灵机为在线图灵机(on-line Turing machine)。虽然离线图灵机是多带图灵机的一个特例，但离线图灵机却能够模拟任何一个图灵机。,定理6-7离线图灵机与基本图灵机等价。,证明：对于基本图灵机M，构造离线图灵机M模拟M。最简单的方法是让离线图灵机M比基本图灵机M多一条

47、输入带，用以复制基本图灵机的输入串，然后将该输入带当作是基本图灵机的输入带，模拟基本图灵机进行相应的处理。具体证明过程略。,3 作为枚举器的图灵机图灵机是递归可枚举语言的识别器和非负整函数的计算器。出此之外，图灵机还可以作为语言的产生模型。,产生语言的图灵机称为作为枚举器的图灵机，是一个特殊的多带（多头）的图灵机，其中一个带专门作为输出带，并且规定，一旦一个字符被印刷在输出带上，就不能再被更改。,如果输出带的读/写头的正常移动方向是向右的话，则输出带的读/写头不允许向左移动。,基本的图灵机每次启动后，只处理输入带的一个输入串（即对于多个串，需要多次启动）；而作为枚举器的图灵机，在启动之后，在输

48、出带上将产生相应语言的每一个句子。为了区别每个句子，每次产生一个句子，就在该句子后面印刷一个分隔符号（如“#”）。,注意：如果作为枚举器的图灵机产生的语言是一个无穷的语言，则作为枚举器的图灵机将永不停机。,4多栈机下推自动机实际上相当于非确定的多带图灵机，具有一条只读输入带和一条存储带（模拟堆栈）。,多栈机(multi-stack machine)具有一条只读输入带，和多条模拟堆栈的存储带；输入带上的读/写头不能够向左移动，存储带上可以印刷上规定的符号，并且存储带上的读/写头可以向左或向右进行移动。,需要注意的是，存储带上的读/写头在向左移动时，必须在当前扫描的带单元中印刷上空白符号B，因此，

49、存储带上的读/写头在向左移动时，该读/写头的右部全是空白符号B（将当前的单元作为了栈顶）。,另外，存储带上的读/写头在向右移动时，一般情况下，应该在当前扫描的带单元印刷上一个非空白符号（在特殊情况下，也可以印刷上一个空白B，如下面介绍的计数机图灵机）。,一个确定的双栈机(double stack machine)是一个确定的图灵机，具有一条只读输入带和两条模拟堆栈的存储带；存储带上的读/写头向左移动时，只能印刷上空白符号B。,定理6-8 一个任意的单带图灵机可以被一个确定的双栈机模拟。,5计数机计数机(counter machine)是一种离线图灵机，具有一条只读输入带，和多条用于计数的单向无

50、穷带（存储带），用带上读头到最左边符号的距离（即单元的个数）表示所计的数。,一个具有n条用于计数的带的计数机称为n计数机。,用于计数的单向无穷带上只能有两种字符，一个为相当于作为栈底符号的Z，该字符也当作是记数带的首字符，它仅仅出现在记数带的最左端；另一个就是空白字符B，一条记数带上所记的数就是该记数带从Z开始到该记数带的读/写头当前位置所包括的空白符号符号B的个数。,定理6-9 一个任意的图灵机可以被一个记数机模拟。证明：略。,6 丘奇-图灵论题与随机存取机在研究可计算性问题时，一种观点认为：对于任何的输入，算法都应该能够终止，否则，只能称其为(计算)过程。,根据这个观点，对于某些输入不能够