《有限自动机理论CH》PPT课件.ppt

《《有限自动机理论CH》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《有限自动机理论CH》PPT课件.ppt（330页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章图灵机图灵机接收能力最强的自动机接收能力最强的自动机图灵机图灵机(即即TuringM-TM)。由由A.Turing于于1936年提出。年提出。TM是可计算性的数学模型是可计算性的数学模型研究可计算性研究可计算性(可计算的特点是可计算的特点是有穷、离散、机械执行、停机有穷、离散、机械执行、停机)。为计算机的发展奠定了为计算机的发展奠定了理论基础理论基础。图灵机可以模拟现代的计算机的图灵机可以模拟现代的计算机的计算能力计算能力。使用图灵机可以解决计算机程序使用图灵机可以解决计算机程序的的可计算问题可计算问题。图灵机的图灵机的构造技术构造技术类似于计算机类似于计算机的的编程编程(设计指令

2、设计指令)技术技术。6.1图灵机的基本模型图灵机的基本模型6.1.1图灵机的定义图灵机的定义图灵机的图灵机的物理模型物理模型a1a2a3 aj anan+1FSC一个有限状态控制器一个有限状态控制器(FSC)一个外部的存储设备一个外部的存储设备可以向右扩展的无限长度带可以向右扩展的无限长度带带上具有带上具有左端点左端点，使用，使用“”表示表示l图图灵灵机机直直接接扫扫描描输输入入带带上上左左端端点点右右边边的的第一个符号第一个符号。带分解为单元，每个单元可以为带分解为单元，每个单元可以为空空(B)或存放字母表上的字母符号或存放字母表上的字母符号有限状态控制器通过一个有限状态控制器通过一个读读/

3、写头写头与带进行耦合。与带进行耦合。带的右边用带的右边用B标记带的标记带的右期间右期间。在在某某个个时时刻刻，有有限限状状态态控控制制器器处处于于某某个个状状态态，读读/写写头头将将扫扫描描带带上上的的一个单元一个单元依依照照状状态态和和扫扫描描到到的的带带上上符符号号，图灵机将有一个图灵机将有一个动作动作如下：如下：有限状态控制器的有限状态控制器的状态状态进行进行改变改变；把把刚刚刚刚扫扫描描过过的的单单元元上上符符号号擦擦除除掉掉，并并印印刷刷上上一一个个新新的的符符号号（有有可可能能印印刷刷上上与原来符号相同的符号）；与原来符号相同的符号）；读读/写写头头向向左左或或者者向向右右移移动动

4、一一个个单单元元；或者读或者读/写头写头不移动不移动。五元式描述动作其中：其中：x，W图灵机处于状态图灵机处于状态q，扫描到符号，扫描到符号x，则，则状态变换为状态变换为q，印刷上新的符号，印刷上新的符号W，读读/写头写头向左向左、或、或向右向右或或不移动不移动。例例6-1用用TM接收接收语言语言a2n|n0图灵机带上符号串为：图灵机带上符号串为：aaaaaaB图图灵灵机机初初始始处处于于状状态态even，将将要要扫扫描描第一个第一个a，则，则/可省略可省略l若带上若带上a的个数为偶数，的个数为偶数，则则图图灵灵机机经经过过多多个个动动作作后后，处处于于接收状态接收状态accept；l若带上若

5、带上a的个数为奇数的个数为奇数，根根据据，图图灵灵机机将不会停机，可以永远继续下去将不会停机，可以永远继续下去这这与与其其它它的的自自动动机机不不同同，即即图图灵灵机机可能会可能会导致导致永不停止永不停止的计算。的计算。例例6-2语言为语言为a2n|n0定义定义6-1图灵机是一个五元式图灵机是一个五元式lTM=(Q，q0，q，)Q是有限状态集合；是有限状态集合；是带上字母表的有限集合是带上字母表的有限集合=BA；的的增增广广集集合合，即即输入带上符号的集合输入带上符号的集合q0Q，是开始状态，是开始状态qQ，是接收状态，是接收状态:QQL,R,N对于任意的对于任意的(q，x)Q(q，x)=(q

6、，W，L，R，N)将将记为一般形式：记为一般形式：或或图灵机是一个七元组图灵机是一个七元组TM=(Q，q0，B，F)F Q终止状态集合；终止状态集合；是带符号集合；是带符号集合；B 称为空白符；称为空白符；:Q Q R,L,N定义定义6-2图灵机的格局图灵机的格局IDw1qw2w1是读是读/写头左边带上的符号串写头左边带上的符号串q是图灵机当前所处的状态是图灵机当前所处的状态w2是还未扫描到的带上的符号串是还未扫描到的带上的符号串()*Q()*l图灵机在格局图灵机在格局w1qw2时停机时停机若若w1qw2=w1qxw对于对于无定义。无定义。(q，x)?定义6-3格局的转换l若若M在在w1qw2

7、上上不不停停机机，则则如如下下定定义义格局的转换：格局的转换：l某某 个个 时时 刻刻，图图 灵灵 机机 处处 于于 格格 局局w1qw2=r1yqxr2，其中：，其中：r1y=w1，(若若w1=，则，则y=B，r1=)xr2=w2，(若若w2=，则，则r2=，x=B)使用使用=表示图灵机的格局转换表示图灵机的格局转换l若若（q，x）=(q，x，L)，则，则r1yqxr2=l若若（q，x）=(q，x，N)，则，则r1yqxr2=l若若（q，x）=(q，x，R)，则，则r1yqxr2=r1qyxr2r1yqxr2r1yxqr2使用使用=+代表格局的代表格局的多次多次变换变换使用使用=*代表格局的

8、代表格局的任意次任意次变换变换定义6-4l图图灵灵机机M=（Q，q0，q，）在在字字母母表表上上接接收收的的语语言言为为L(M)，则，则L(M)=w|存在存在w1，w2()*有有=*q0ww1qw2定义6-5完全的图灵机如如果果图图灵灵机机对对于于一一切切输输入入串串都都能能够够停停机机-完全的图灵机。完全的图灵机。完完全全的的图图灵灵机机接接收收的的语语言言L称称为为递递归归语言语言(图灵可判定语言图灵可判定语言)6.1.2图灵机的构造图灵机的构造例例-接收仅有一个接收仅有一个1的的0、1串串TM=(q0，q1，q2,0，1,q0，q2,)=0，1，B0思路：l当图灵机遇到当图灵机遇到a时，

9、将时，将a改写为改写为#向右寻找向右寻找b，找到，找到b，将，将b改写为改写为#再向左找再向左找a直到所有直到所有a都找完。都找完。(向左找的向左找的a是整个是整个a串串最左边的最左边的a)指令为指令为读到一个读到一个a，用，用#代替它，向右找代替它，向右找b处处于于状状态态del_b，扫扫描描到到b，用用#代代替替它，向左寻找它，向左寻找a，（从，（从重复循环）重复循环）/最右的最右的aseek_a状状态态时时，没没有有再再发发现现a(都都已已被被#所所代代替替)，还还需需要要检检查查是是否否所所有有的的b都已经被扫描过。都已经被扫描过。问题问题l该图灵机能接收该图灵机能接收anbn的所有串

10、的所有串但该图灵机也能接收但该图灵机也能接收aababb等等原因：使用原因：使用#代表已扫描的代表已扫描的a和和b没有保证没有保证a和和b的的顺序顺序。l为了区别原来的字母为了区别原来的字母a和和b使用使用#和和$分别代替字母分别代替字母a和和b当当a和和b都识别后，带上的串为都识别后，带上的串为#$B例例6-5修改上例：修改上例：读到一个读到一个a，用，用#代替它，向右寻找代替它，向右寻找b处处于于状状态态del_b，扫扫描描到到b，用用$代代替替它，向左寻找它，向左寻找a，（从，（从重复重复循环循环）在在seek_a状状态态时时，没没有有再再发发现现a（都都已经被已经被#所代替）所代替）需

11、检查是否所有的需检查是否所有的b都已经被扫描过都已经被扫描过还还必须注意必须注意#与与$的顺序的顺序。例6-6anbn|n0的第二种算法l当图灵机遇到当图灵机遇到a时，将时，将a改写为改写为#l向右寻找向右寻找b，找到，找到b，将，将b改写为改写为$再向左找再向左找a(此时的此时的a是整个是整个a串串最左边的最左边的a)，直到所有，直到所有a都找完。都找完。指令指令读到一个读到一个a，用，用#代替它，向右寻找代替它，向右寻找b处处于于状状态态del_b，扫扫描描到到b，用用$代代替替，向左寻找向左寻找a，（从，（从重复循环）重复循环）/跳过跳过a串串/最右最右#/最左最左a在在seek_a状状

12、态态时时，没没有有再再发发现现a，需需检查是否所有的检查是否所有的b都已经被扫描过。都已经被扫描过。思考思考l比较对于相同的输入串，两种算法的比较对于相同的输入串，两种算法的图灵机的指令数量、每条指令的执行图灵机的指令数量、每条指令的执行次数（总次数）；次数（总次数）；l能否给对图灵机的性能进行评价？能否给对图灵机的性能进行评价？例例6-7anbn|n0第三种算法第三种算法思路思路:首先检查输入串是否为首先检查输入串是否为a+b+的格式；的格式；如果不是，则拒绝该串如果不是，则拒绝该串如果是，检查如果是，检查a和和b的个数是否相等。的个数是否相等。指令指令(扫描扫描a)(扫描扫描b)(开始检查

13、开始检查a和和b的个数是否相等的个数是否相等)已经保证顺序已经保证顺序（检查是否有多余的（检查是否有多余的b）例6-8接收语言接收语言anbncn|n0lTM=（Q，start，accept，）Q=start，del_b，del_c，seek_a，check1，check2，check3，accept=a，b，c=a，b，c，B，#，$，!指令指令读到一个读到一个a，用，用#代替它，向右寻找代替它，向右寻找b处处于于状状态态del_b时时,扫扫描描到到b，用用$代代替替它，向右寻找它，向右寻找c：处处于于状状态态del_c时时，扫扫描描到到c，用用!代代替替它，向左找它，向左找a，(从从开始又

14、重复循环开始又重复循环)在在seek_a状状态态时时，没没有有再再发发现现a（都都已经被已经被#所代替）所代替）还还需需要要检检查查是是否否所所有有的的b和和c都都已已经经被被扫描过扫描过注意注意#、$和！的顺序和！的顺序识别第一个识别第一个!跳过剩余跳过剩余!l类类 似似 地地，图图 灵灵 机机 接接 收收 语语 言言 anbncn|n0，也有多种方法。，也有多种方法。思考：构造构造TM接收语言接收语言aibjci+j|i,j0构造构造TM接收语言接收语言aibjci*j|i，j0构造构造TM接收语言接收语言wcwT|w(a,b)*6.2图灵机作为非负整数函数计算模型图灵机作为非负整数函数计

15、算模型l设有设有k元函数元函数f(n1，n2，nK)=m如果如果TM接受输入串接受输入串0n110n2110nk而而“输出输出”符号串符号串0m则称则称TM计算计算k元函数元函数f；或称或称f为为TM计算的函数。计算的函数。也称也称f是图灵可计算的是图灵可计算的。但当但当f(n1，n2，nK)无定义时，无定义时，TM没有适当的输出。没有适当的输出。l自动机都具有识别语言的功能自动机都具有识别语言的功能图灵机还具有图灵机还具有“计算计算”功能功能可可以以规规定定非非负负整整数数的的表表示示方方法法,从从而实现而实现非负整数的函数求值非负整数的函数求值。l使使用用“一一进进制制”方方式式表表示示一

16、一个个非非负负整整数，即数，即使用使用0m表示整数表示整数m。l若若需需要要计计算算f(m，n)，则则可可以以在在输输入入带上存放带上存放0m10n形式的串形式的串l图图灵灵机机将将串串改改写写为为0f(m，n)的的形形式式，即即表示出计算表示出计算f(m，n)的结果。的结果。加法图灵机加法图灵机l对于非负整数对于非负整数n、m，计算，计算n+m。分析分析图灵机输入图灵机输入0n10m需要输出需要输出0n+m算法：算法：将将1改写为改写为0，最后一个，最后一个0改写为改写为B(可能是可能是1改写成的改写成的0)lTM=（Q，,start，accept，）Q=start，q1，q2，accept

17、=0，1=0，1，B指令指令串为串为1或或10m第第1个个0跳过剩余的跳过剩余的0遇到遇到1，改为，改为0遇到遇到B，向左找，向左找0最后的最后的0改为改为B注意注意l扫描扫描1左边和右边的左边和右边的0的工作都由的工作都由完成。完成。整个串整个串只允许一个只允许一个1。例例6-16构造构造TMl实现非负减法实现非负减法(真减法真减法)mn=m-nmn=0mn(即全是即全是B)或或思路思路1带上字符串的形式为带上字符串的形式为0m10n寻找寻找1左边的左边的0，删除，删除1右边的右边的0可能在寻找可能在寻找1左边的左边的0时结束时结束(mn)或者在删除或者在删除1右边的右边的0时结束时结束(m

18、n)(1)扫描第扫描第1个个0(2)/原标记的原标记的1(3)/将将1后的第后的第1个个0变为变为1/后加的后加的strat,1q2,B(4)向左找向左找0读写头位置读写头位置转（转（1）重复上述动作重复上述动作?mn(5)/遇到最右边的遇到最右边的B，表示，表示1右边已没有右边已没有0将将1改写为改写为B补写补写1个个0，结束，结束mn(6)start将遇到第一个将遇到第一个1将后面将后面1改写为改写为B将后面将后面0改写为改写为B结束结束此时，输入带上全为，表示此时，输入带上全为，表示mnl在在第第(5)步步开开始始时时，输输入入带带上上的的字字符符串串形式为：形式为：BBBB000011

19、11Bm-n-1个个n个个左边左边B有有n+1个。个。mn根据根据TM的动作，的动作，在左边消除一个在左边消除一个0，再去，再去1的右边找的右边找0当当发发现现1的的右右边边已已经经没没有有0时时，此此时时减减法工作应该结束法工作应该结束mn但但左边多消除了一个左边多消除了一个0因因此此，第第（5）步步，在在q4的的的的控控制制下下除除了将了将1改写为改写为B外外还还应应该该将将一一个个0补补写写回回来来，才才能能结结束束减减法工作。法工作。mnl此时，输入带上的字符串形式为：此时，输入带上的字符串形式为：BBBB0000Bm-n个个lm=n时，整个减法的结果应该为时，整个减法的结果应该为0l

20、输入带全为输入带全为 Bl特殊：特殊：m=n=0，则串为，则串为1BB结束结束思路思路2自学自学l图灵机反复进行下面的工作：图灵机反复进行下面的工作：先用先用B替换替换1左边领头的左边领头的0向向右右搜搜寻寻1右右边边的的第第一一个个0，并并将将这这个个0替换为替换为X，然后左移到然后左移到B。重新开始循环。重新开始循环。l退出循环的条件有两种：退出循环的条件有两种：1)1的左边找不到的左边找不到0，说明，说明mn输出输出0，应将所有非，应将所有非B符号改写为符号改写为B；2)1的右边找不到的右边找不到0，说明，说明mn输出输出0m-n，应将应将1换为换为0，将，将X换为换为B。状态转换函数为

21、：状态转换函数为：(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

22、/1换为换为06.3图灵机的构造技术图灵机的构造技术构造构造TM，就相当于，就相当于编写一个程序编写一个程序(指令或规则的组合指令或规则的组合)。本节介绍的图灵机的一些构造技术，本节介绍的图灵机的一些构造技术，这些技术具有一般性，对于图灵机的这些技术具有一般性，对于图灵机的构造构造(程序设计程序设计)具有较大的意义。具有较大的意义。6.3.1图灵机的图灵机的存储技术存储技术例例6-12构构造造TM，识识别别字字母母表表a,b,c上上的语言的语言L：每每个个字字符符串串的的第第一一个个符符号号在在该该串串中中仅仅仅出现一次仅出现一次。思路：要求：第一个符号仅仅出现一次要求：第一个符号仅仅出现一次

23、图图灵灵机机可可以以“记记住住”输输入入带带上上的的第第一一个符号个符号（a或或b或者或者c）。）。使用使用二元式二元式表示表示状态状态第一个分量仍然表示原来的状态；第一个分量仍然表示原来的状态；第二个分量存储带上的第一个符号。第二个分量存储带上的第一个符号。q，a、q，b和和q，c分分别别代代表表输输入入串的第一个符号为串的第一个符号为a、b和和c的状态。的状态。(1)扫描第一个符号，并存储扫描第一个符号，并存储(2)第一个符号是第一个符号是a(3)第一个符号是第一个符号是b(4)第一个符号是第一个符号是c结束结束(5)遇到最右的遇到最右的B，接收该串，接收该串注意注意直接运用规则（直接运用

24、规则（1）和（）和（5）可以接收）可以接收仅仅仅仅只有一个符号只有一个符号的输入串。的输入串。例6-13构造TM，识别a，b，c上的语言上的语言L：每每个个句句子子的的最最后后一一个个符符号号在在该该串串中中仅仅仅出现一次。仅出现一次。思路1：最后个符号仅仅出现一次最后个符号仅仅出现一次TM先将读先将读/写头移动到带的最后写头移动到带的最后“记住记住”输入带上的输入带上的最后一个符号最后一个符号向左扫描输入带上的其他符号向左扫描输入带上的其他符号与最后一个符号进行比较与最后一个符号进行比较x=a,b,c(1)将读将读/写头移动到带的最后写头移动到带的最后start,B?(2)存储最后的符号存储

25、最后的符号向向左左扫描输入带上的其他符号扫描输入带上的其他符号遇到遇到结结束束思路思路2：TM需要存储需要存储已经出现过的符号已经出现过的符号为了识别输入带上的最后一个符号，为了识别输入带上的最后一个符号，图灵机还需要图灵机还需要存储当前扫描的符号，存储当前扫描的符号，以便确定最后一个符号。以便确定最后一个符号。使用三元组表示单个状态使用三元组表示单个状态第一个分量仍然表示原来的状态；第一个分量仍然表示原来的状态；第第二二个个分分量量是是已已经经出出现现过过的的符符号号的的串串(ab、ac或或bc)第三个分量表示上一次扫描的符号。第三个分量表示上一次扫描的符号。如如q，ab，a代表输入带上的字

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

27、TM=a,b,c，将输入串，将输入串右右移两个单元移两个单元使用三元组使用三元组q，a1，a2表示状态表示状态q表示原来的状态；表示原来的状态；a1、a2可以代表可以代表a、b、c。设串长度设串长度=3(1)扫描第一个符号，并存储扫描第一个符号，并存储(2)扫描第二个符号，并存储扫描第二个符号，并存储(3)将将a1放在放在a3位置位置,将将a3存储存储(4)将将倒倒数数第第二二个个符符号号放放在在右右边边空空白白单单元元，将最后一个符号存储在状态中将最后一个符号存储在状态中(5)将最后一个符号放在带上将最后一个符号放在带上其中规则其中规则(3)需要需要重复多次使用。重复多次使用。本例使用三元组

28、表示特殊状态本例使用三元组表示特殊状态也可以使用二元组表示特殊状态也可以使用二元组表示特殊状态如如q，a1，a2可以记为可以记为q，a1a2（n元组也可以表示为二元组）元组也可以表示为二元组）对带上符号进行移动一一般般只只是是比比较较复复杂杂的的TM的的识识别别任任务务中的一部分工作中的一部分工作移移动动本本身身不不会会涉涉及及到到串串的的接接收收或或拒拒绝绝问题问题复复杂杂的的TM可可以以继继续续从从end_move状状态态开始其他的工作开始其他的工作思考：构造TM将整个输入串前两个符号将整个输入串前两个符号删除删除。思路思路将带上符号将带上符号从右向左从右向左移动两个单元。移动两个单元。例

29、6-15构造构造TM输入字母表为输入字母表为0，1在输入串的开始处添加子串在输入串的开始处添加子串10。略。略。例6-16构造构造TM=a，b，c将整个串包含的第一个将整个串包含的第一个abc子串子串删除删除。思路思路存储技术寻找到第存储技术寻找到第1个个abc子串的位置子串的位置将后面的符号将后面的符号向左向左移动三个单元。移动三个单元。略。略。例6-18构构造造TM，输输入入字字母母表表为为0，1，要要求求M接收语言接收语言L：该该语语言言的的每每个个字字符符串串包包含含且且仅仅只只能能包包含含一一个个101子子串串(有有且且仅仅有有一一个个101，不不可可以没有以没有101子串）子串）思

30、路思路当识别出第一个当识别出第一个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”，等等 待待 可可 能能 的的“0”(4)已已经经扫扫描描到到“10”，等等待待可可能能的的“1”(5)已扫描到已扫描到101，检查串的剩余部分，检查串的剩余部分(6)(7)（8）的第）的第2条指令与

31、（条指令与（9）可以省略）可以省略(8)(9)整个输入串中没有整个输入串中没有101结束结束(10)整个输入串只有一个整个输入串只有一个101思考思考构造构造TM，接收语言，接收语言L：该语言的每个句子必须包含该语言的每个句子必须包含两个两个101例6-19构造构造TM，接收语言，接收语言L：该该语语言言的的每每个个句句子子最最多多只只能能包包含含一一个个100子串（子串（可以没有可以没有100子串子串）。）。思路思路接收接收1个个100子串的所有串；子串的所有串；接收没有接收没有100子串的所有串。子串的所有串。例例6-23构造构造TM接收语言接收语言L：该语言的每个句子该语言的每个句子不包

32、含不包含子串子串100。思路思路当识别出第一个当识别出第一个100后，就拒绝。后，就拒绝。6.3.3图灵机扫描多个符号技术图灵机扫描多个符号技术l略略图灵机的多道技术图灵机的多道技术为了能够保存和处理更复杂的数据，为了能够保存和处理更复杂的数据，可以将可以将TM的输入带划分为若干道的输入带划分为若干道在各道上可以存放不同的符号。在各道上可以存放不同的符号。没有改变图灵机的基本模型，没有改变图灵机的基本模型，只是将带上符号当做一个向量的组合只是将带上符号当做一个向量的组合每每个个符符号号可可以以是是一一个个K维维向向量量（将将输输入入带划分为带划分为K道）。道）。单带单带K道的图灵机道的图灵机状

33、态转换函数一般形式为一般形式为对于对于K道图灵机道图灵机一次需要扫描一个符号的多道一次需要扫描一个符号的多道思考思考l二进制的加法二进制的加法l考查第考查第3题题例6-24:构造图灵机字母表为字母表为a接收语言接收语言L：an|n=0，且，且n为完全平方数为完全平方数基本数学公式：基本数学公式：(n+1)2=n2+2n+1思路使用三道的图灵机使用三道的图灵机第一道存放输入串；第一道存放输入串；第二、三两道作为第二、三两道作为“运算器运算器”使用。使用。初始时初始时从从i=0开始开始在第二道上放在第二道上放i2个个a比较第一道与第二道上比较第一道与第二道上a的个数的个数如果相等，就接收；如果相等

34、，就接收；不相等，则在第三道上设置不相等，则在第三道上设置(计算计算)出出2*i+1个个a，将第三道上的将第三道上的a加入到第二道上去，加入到第二道上去，从而，在第二道上形成从而，在第二道上形成(i+1)2个个a再与第一道上再与第一道上a的个数进行比较。的个数进行比较。初始初始i=0第第2道道a个数为个数为02aaaaBn个个aBBBB02=0BBBB第第3道设置为道设置为2*0+1aaaaBBBBB02aBBB2*0+1第第2道设置为道设置为12i=1aaaaBaBBB12aBBB第第3道设置为道设置为2*1+1aaaaBnaBBB12aaaBB2*1+1第第2道设置为道设置为22i=2aa

35、aaBnaaaaBB22aaaBB第第3道设置为道设置为2*2+1aaaaBnaaaaB.B22aaaaaBB2*2+1第第2道设置为道设置为32i=3aaaaBnaaaaaaaaaB.B32aaaaaBB第第3道设置为道设置为2*3+1aaaaBnaaaaaaaaaBB32aaaaaaaBB2*3+1第第2道设置为道设置为42i=4aaa.aBnaaaaaaaaaaaaaaaaBB42aaaaaaaB.B上上述述动动作作一一直直重重复复下下去去，直直到到第第一一、二道上二道上a的个数相等，则接收；的个数相等，则接收；或者第一、二道上或者第一、二道上a的个数不相等的个数不相等则拒绝该输入串。则

36、拒绝该输入串。从从i=2过渡过渡i=3到时，图灵机输入带为：到时，图灵机输入带为：lTM=（Q，start，accept，）Q=start，q1，,q9,refuse,accept=a=a，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

37、其中：xa，B(4)计算计算2(i+1)+1，为下次做准备，为下次做准备(实际上实际上,在第在第3道每次增加道每次增加2个个a)仅当仅当输输入串入串为为a4和和a9时时(i2=2*i)其中：x，ya，B(5)比较第一道和第二道上比较第一道和第二道上a的个数的个数/第一道上第一道上a的已经查完的已经查完其中：xa，B仅当仅当输输入串入串为为a4和和a9时时(i2小于小于2i)第二道的第二道的a少于第一道的少于第一道的a，继续扫描，继续扫描(6)拒绝情况拒绝情况(可省略可省略)第二道的第二道的a多于第一道上的多于第一道上的a，停机，停机第一道上已经没有第一道上已经没有a，停机，停机图灵机的查讫技术

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

39、始初始输入带上的符号情况为：输入带上的符号情况为：a1a2an2b1b2bmBBBBBBBBB比较时，使用存储技术，比较时，使用存储技术，将符号将符号“2”前面的待比较符号前面的待比较符号存储存储，再与再与2后面后面相应位置相应位置的符号进行比较。的符号进行比较。某个时刻，输入带上的符号情况某个时刻，输入带上的符号情况a1a2an2b1b2bmB BB BBBM的初始状态为的初始状态为start令令a=0或或1，b=0或或1记录待比较符号：记录待比较符号：读头右移到读头右移到2的后面：的后面：找到要比较的位置：找到要比较的位置：比较后相同则继续：比较后相同则继续：2个个a必须同为必须同为0或或

40、1读头左移到读头左移到2前：前：读头左移过读头左移过2后有两种情况后有两种情况未比较完未比较完已比较完已比较完未比较完时读头左移到待比较符号：未比较完时读头左移到待比较符号：已比较完则看右边是否处理完：已比较完则看右边是否处理完：图灵机的子程序技术图灵机的子程序技术与通常的与通常的程序设计技术程序设计技术相似相似子程序的思想在子程序的思想在TM的构造中的构造中也是十分重要的技术。也是十分重要的技术。子子程程序序技技术术的的使使用用，可可以以将将复复杂杂的的问问题题进进行行分分解解（化化简简），同同时时，也也可可以以将将TM的构造的构造“模块化模块化”TM的的子子程程序序技技术术的的基基本本思思

41、想想是是将将TM中中需需要要重重复复使使用用的的功功能能分分解解出出来来，作为一个作为一个子程序子程序。完成整个功能的图灵机为完成整个功能的图灵机为M（作为主（作为主程序对待）程序对待）完成某个特定功能的图灵机为完成某个特定功能的图灵机为M（即（即子程序作为某个小的图灵机）子程序作为某个小的图灵机）图灵机图灵机M从状态从状态q开始开始到一个固定的状态到一个固定的状态f结束结束状态状态q、f是图灵机是图灵机M的两个的两个一般状态一般状态当图灵机当图灵机M进入状态进入状态q时，就启动时，就启动M（相当于（相当于调用调用子程序）；子程序）；当当M进入状态进入状态f时就时就返回返回到到M（相当（相当于

42、子程序结束）。于子程序结束）。注意：图灵机图灵机M中可以有多个状态中可以有多个状态但仅有两个状态（即但仅有两个状态（即M的的开始状态开始状态q和和接收状态接收状态f）是与主程序的图灵机）是与主程序的图灵机M共用的共用的图灵机图灵机M的其他状态是的其他状态是私有的私有的，不能，不能被主程序的图灵机被主程序的图灵机M所使用。所使用。例6-26构造构造TM，完成正整数的乘法运算。，完成正整数的乘法运算。正整数的乘法运算的数学公式：正整数的乘法运算的数学公式：mn=(1+1+1)nm个个1使用使用TM实现正整数的乘法运算实现正整数的乘法运算TM的输入带上存放串的输入带上存放串0m10n，运算后，使得带

43、上的串变为运算后，使得带上的串变为0m*n形式形式TM处理该问题的最一般的方法为：处理该问题的最一般的方法为：当当从从1的的左左边边消消去去一一个个0后后，应应该该在在0n的后面增加的后面增加n个个0(补补1作为分隔标记作为分隔标记)；当当1左左边边的的所所有有的的0（共共有有m个个）消消完完后后，再再消消去去多多余余的的符符号号（两两个个1和和原原来来的的0n），就得到了），就得到了0m*n形式。形式。在在0n后面添加后面添加n个个0的过程是重复的，的过程是重复的，可以使用子程序技术。可以使用子程序技术。在某个时刻，在某个时刻，TM输入带上的输入带上的符号符号为：为：Bh0m-h10n10h

44、*n完成完成(1+1+1+1)*nh个个M的状态函数分为3部分：l1)初始化：初始化：将将第第一一个个0变变为为B，并并在在最最后后一一个个0后后面设置面设置标记为标记为1该标记表明了该标记表明了增加增加0的开始位置的开始位置使使得得增增加加的的0在在第第二二个个1的的后后面面；并并将将读读/写头移动到写头移动到n个个0中的第一个处。中的第一个处。则格局变换为：则格局变换为：q00m10n=*B0m-11q10n1注意注意此时，只是消去了第一个此时，只是消去了第一个0设置标记设置标记1；但还没有在后面增加但还没有在后面增加0即将扫描原来即将扫描原来0n的的第一个第一个0l2)主控程序：主控程序

45、：初始化初始化后，状态变为后，状态变为q1。q1相当于子程序图灵机的开始状态，相当于子程序图灵机的开始状态，进进入入子子程程序序，将将n个个0增增加加到到第第二二个个1的后面。的后面。当当退退出出子子程程序序时时，状状态态为为q5（q5也也就就是子程序图灵机的结束状态）是子程序图灵机的结束状态）此此时时需需要要将将读读/写写头头移移动动到到前前面面m个个0中剩余中剩余0的第一个处的第一个处并将这个并将这个0改为改为B，准备进入下次循环，准备进入下次循环对应的格局转换为：Bhq00m-h10n10(h-1)*n=*Bh0m-h1q10n10(h-1)*n进入子程序进入子程序=*Bh0m-h1q5

46、0n10h*n=*Bh+1q00m-h-110n10h*n当当找找不不到到前前面面m个个0中中剩剩余余的的0时时，表表示示乘乘法法计计算算工工作作已已经经结结束束，需需要要消消去去多多余的符号（两个余的符号（两个1和原来的和原来的0n），），得到最后的结果串。对应的格局转换得到最后的结果串。对应的格局转换Bmq810n10m*n=*Bm+n+1+1q140m*n其中，状态其中，状态q14是接收状态是接收状态l3)子程序：子程序：将将n个个0增加到原来增加到原来0n的后面。的后面。子程序子程序TM从它的开始状态从它的开始状态q1启动，启动，进进入入接接收收状状态态q5时时完完成成一一次次工工作作

47、，并并返回到主控程序。返回到主控程序。l进进入入图图灵灵机机子子程程序序时时，输输入入带带上上符符号号串的形式情况及读串的形式情况及读/写头位置为：写头位置为：Bh0m-h1000010(h-1)*nq1读读/写头指向写头指向0n的第一个的第一个0l子程序对应的格局转换为：子程序对应的格局转换为：Bh0m-h1q10n10(h-1)*n=*Bh0m-h1q50n10h*nl整个图灵机的格局转换情况：整个图灵机的格局转换情况：初始化：初始化：q00m10n=*B0m-11q10n1主程序和子程序：Bhq00m-h10n10(h-1)*n=*Bh0m-h1q10n10(h-1)*n主程序消除主程序

48、消除0Bh0m-h1q10n10(h-1)*n=*Bh0m-h1q50n10h*n子程序增加子程序增加0nBh0m-h1q50n10h*n=*Bh+1q00m-h-110n10h*n主程序消除主程序消除0Bmq810n10m*n=*Bm+n+1+1q140m*n主程序消除多余符号主程序消除多余符号初始化(不止执行一次)：/在最后增加标记在最后增加标记1控制在串的控制在串的最后只能放一个最后只能放一个1此时，将扫描原来此时，将扫描原来0n的第一个的第一个0子程序：将将0标记为标记为2，以方便复制，以方便复制0n向右寻找向右寻找B遇到标记遇到标记1（第二个（第二个1）复制一个复制一个0向左寻找向左

49、寻找0n中剩余的中剩余的0（寻找标记（寻找标记2）准备复制下一个准备复制下一个0n个个0都已复制都已复制将将2恢复为恢复为0子子程程序序结结束束，读读/写写头头仍仍然然在在0n的的第第一一个个0处处主程序：主程序：上一次循环结束，本次循环开始上一次循环结束，本次循环开始m个个0都消完，循环结束都消完，循环结束消去多余串消去多余串10n1:此时，图灵机带上的符号形式为：此时，图灵机带上的符号形式为：Bm+n+1+10mnl图灵机共有图灵机共有15个状态，其中：个状态，其中：子程序图灵机使用了子程序图灵机使用了5个状态：个状态：q1、q2、q3、q4、q5主程序图灵机使用了主程序图灵机使用了12个

50、状态：个状态：q0、q1、q5、q6、q7、q8、q9、q10、q11、q12、q13、q14丘奇丘奇-图灵论题图灵论题在研究可计算性问题时在研究可计算性问题时一种观点认为：一种观点认为：对于任何输入，对于任何输入，算法算法都应该能够终止都应该能够终止否则，只能称其为否则，只能称其为(计算计算)过程过程。l根根据据这这个个观观点点，对对于于某某些些输输入入不不能能够够停停机机的的图图灵灵机机就就不不能能够够称称为为算算法法，也也就就是是说说，如如果果某某个个图图灵灵机机使使用用永永不不停停机机的的方方式式表表示示对对某某个个输输入入串串不不能能够够接接收的话，该图灵机就不是算法；收的话，该图灵