第六章第六章图灵机图灵机接收能力最强的自动机接收能力最强的自动机图灵机图灵机(即即TuringM-TM)。由由A.Turing于于1936年提出。年提出。TM是可计算性的数学模型是可计算性的数学模型研究可计算性研究可计算性(可计算的特点是可计算的特点是有穷、离散、机械执行、停机有穷、离散、机械执行、停机)。为计算机的发展奠定了为计算机的发展奠定了理论基础理论基础。图灵机可以模拟现代的计算机的图灵机可以模拟现代的计算机的计算能力计算能力。使用图灵机可以解决计算机程序使用图灵机可以解决计算机程序的的可计算问题可计算问题。图灵机的图灵机的构造技术构造技术类似于计算机类似于计算机的的编程编程(设计指令设计指令)技术技术。6.1图灵机的基本模型图灵机的基本模型6.1.1图灵机的定义图灵机的定义图灵机的图灵机的物理模型物理模型a1a2a3 aj anan+1FSC一个有限状态控制器一个有限状态控制器(FSC)一个外部的存储设备一个外部的存储设备可以向右扩展的无限长度带可以向右扩展的无限长度带带上具有带上具有左端点左端点，使用，使用“”表示表示l图图灵灵机机直直接接扫扫描描输输入入带带上上左左端端点点右右边边的的第一个符号第一个符号。带分解为单元，每个单元可以为带分解为单元，每个单元可以为空空(B)或存放字母表上的字母符号或存放字母表上的字母符号有限状态控制器通过一个有限状态控制器通过一个读读/写头写头与带进行耦合。与带进行耦合。带的右边用带的右边用B标记带的标记带的右期间右期间。在在某某个个时时刻刻，有有限限状状态态控控制制器器处处于于某某个个状状态态，读读/写写头头将将扫扫描描带带上上的的一个单元一个单元依依照照状状态态和和扫扫描描到到的的带带上上符符号号，图灵机将有一个图灵机将有一个动作动作如下：如下：有限状态控制器的有限状态控制器的状态状态进行进行改变改变；把把刚刚刚刚扫扫描描过过的的单单元元上上符符号号擦擦除除掉掉，并并印印刷刷上上一一个个新新的的符符号号（有有可可能能印印刷刷上上与原来符号相同的符号）；与原来符号相同的符号）；读读/写写头头向向左左或或者者向向右右移移动动一一个个单单元元；或者读或者读/写头写头不移动不移动。五元式描述动作其中：其中：x，W图灵机处于状态图灵机处于状态q，扫描到符号，扫描到符号x，则，则状态变换为状态变换为q，印刷上新的符号，印刷上新的符号W，读读/写头写头向左向左、或、或向右向右或或不移动不移动。例例6-1用用TM接收接收语言语言a2n|n0图灵机带上符号串为：图灵机带上符号串为：aaaaaaB图图灵灵机机初初始始处处于于状状态态even，将将要要扫扫描描第一个第一个a，则，则/可省略可省略l若带上若带上a的个数为偶数，的个数为偶数，则则图图灵灵机机经经过过多多个个动动作作后后，处处于于接收状态接收状态accept；l若带上若带上a的个数为奇数的个数为奇数，根根据据，图图灵灵机机将不会停机，可以永远继续下去将不会停机，可以永远继续下去这这与与其其它它的的自自动动机机不不同同，即即图图灵灵机机可能会可能会导致导致永不停止永不停止的计算。的计算。例例6-2语言为语言为a2n|n0定义定义6-1图灵机是一个五元式图灵机是一个五元式lTM=(Q，q0，q，)Q是有限状态集合；是有限状态集合；是带上字母表的有限集合是带上字母表的有限集合=BA；的的增增广广集集合合，即即输入带上符号的集合输入带上符号的集合q0Q，是开始状态是开始状态qQ，是接收状态是接收状态:QQL,R,N对于任意的对于任意的(q，x)Q(q，x)=(q，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上上不不停停机机，则则如如下下定定义义格局的转换：格局的转换：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使用使用=+ +代表格局的代表格局的多次多次变换变换使用使用=* *代表格局的代表格局的任意次任意次变换变换定义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时，将时，将a改写为改写为#向右寻找向右寻找b，找到，找到b，将，将b改写为改写为#再向左找再向左找a直到所有直到所有a都找完。都找完。(向左找的向左找的a是整个是整个a串串最左边的最左边的a)指令为指令为读到一个读到一个a，用用#代替它，向右找代替它，向右找b处处于于状状态态del_b，扫扫描描到到b，用用#代代替替它，向左寻找它，向左寻找a，（，（从从重复循环）重复循环）/最右的最右的aseek_a状状态态时时，没没有有再再发发现现a(都都已已被被#所所代代替替)，还还需需要要检检查查是是否否所所有有的的b都已经被扫描过。都已经被扫描过。问题问题l该图灵机能接收该图灵机能接收anbn的所有串的所有串但该图灵机也能接收但该图灵机也能接收aababb等等原因：使用原因：使用#代表已扫描的代表已扫描的a和和b没有保证没有保证a和和b的的顺序顺序。l为了区别原来的字母为了区别原来的字母a和和b使用使用#和和$分别代替字母分别代替字母a和和b当当a和和b都识别后，带上的串为都识别后，带上的串为#$B例例6-5修改上例：修改上例：读到一个读到一个a，用用#代替它，向右寻找代替它，向右寻找b处处于于状状态态del_b，扫扫描描到到b，用用$代代替替它，向左寻找它，向左寻找a，（从，（从重复重复循环循环）在在seek_a状状态态时时，没没有有再再发发现现a（都都已经被已经被#所代替）所代替）需检查是否所有的需检查是否所有的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状状态态时时，没没有有再再发发现现a，需需检查是否所有的检查是否所有的b都已经被扫描过。都已经被扫描过。思考思考l比较对于相同的输入串，两种算法的比较对于相同的输入串，两种算法的图灵机的指令数量、每条指令的执行图灵机的指令数量、每条指令的执行次数（总次数）；次数（总次数）；l能否给对图灵机的性能进行评价？能否给对图灵机的性能进行评价？例例6-7anbn|n0第三种算法第三种算法思路思路:首先检查输入串是否为首先检查输入串是否为a+b+的格式；的格式；如果不是，则拒绝该串如果不是，则拒绝该串如果是，检查如果是，检查a和和b的个数是否相等。的个数是否相等。指令指令(扫描扫描a)(扫描扫描b)(开始检查开始检查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，(从从开始又重复循环开始又重复循环)在在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图灵机作为非负整数函数计算模型图灵机作为非负整数函数计算模型l设有设有k元函数元函数f(n1，n2，nK)=m如果如果TM接受输入串接受输入串0n110n2110nk而而“输出输出”符号串符号串0m则称则称TM计算计算k元函数元函数f；或称或称f为为TM计算的函数。计算的函数。也称也称f是图灵可计算的是图灵可计算的。但当但当f(n1，n2，nK)无定义时，无定义时，TM没有适当的输出。没有适当的输出。l自动机都具有识别语言的功能自动机都具有识别语言的功能图灵机还具有图灵机还具有“计算计算”功能功能可可以以规规定定非非负负整整数数的的表表示示方方法法,从从而实现而实现非负整数的函数求值非负整数的函数求值。l使使用用“一一进进制制”方方式式表表示示一一个个非非负负整整数，即数，即使用使用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=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时结束时结束(mn)(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)步步开开始始时时，输输入入带带上上的的字字符符串串形式为：形式为：BBBB00001111Bm-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输入带全为输入带全为 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。状态转换函数为：状态转换函数为：(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换为换为06.3图灵机的构造技术图灵机的构造技术构造构造TM，就相当于，就相当于编写一个程序编写一个程序(指令或规则的组合指令或规则的组合)。本节介绍的图灵机的一些构造技术，本节介绍的图灵机的一些构造技术，这些技术具有一般性，对于图灵机的这些技术具有一般性，对于图灵机的构造构造(程序设计程序设计)具有较大的意义。具有较大的意义。6.3.1图灵机的图灵机的存储技术存储技术例例6-12构构造造TM，识识别别字字母母表表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：每每个个句句子子的的最最后后一一个个符符号号在在该该串串中中仅仅仅出现一次。仅出现一次。思路1：最后个符号仅仅出现一次最后个符号仅仅出现一次TM先将读先将读/写头移动到带的最后写头移动到带的最后“记住记住”输入带上的输入带上的最后一个符号最后一个符号向左扫描输入带上的其他符号向左扫描输入带上的其他符号与最后一个符号进行比较与最后一个符号进行比较x=a,b,c(1)将读将读/写头移动到带的最后写头移动到带的最后start,B?(2)存储最后的符号存储最后的符号向向左左扫描输入带上的其他符号扫描输入带上的其他符号遇到遇到结结束束思路思路2：TM需要存储需要存储已经出现过的符号已经出现过的符号为了识别输入带上的最后一个符号，为了识别输入带上的最后一个符号，图灵机还需要图灵机还需要存储当前扫描的符号，存储当前扫描的符号，以便确定最后一个符号。以便确定最后一个符号。使用三元组表示单个状态使用三元组表示单个状态第一个分量仍然表示原来的状态；第一个分量仍然表示原来的状态；第第二二个个分分量量是是已已经经出出现现过过的的符符号号的的串串(ab、ac或或bc)第三个分量表示上一次扫描的符号。第三个分量表示上一次扫描的符号。如如q，ab，a代表输入带上的字符已经出现过代表输入带上的字符已经出现过a和和b上一次上一次扫描的符号为扫描的符号为a。具体指令具体指令略略思考：构造TM该语言的每个句子的该语言的每个句子的(倒数倒数)第第n个符号个符号在该串中仅仅出现在该串中仅仅出现K次。次。n=1，2，3，；K=1，2，3，6.3.2图灵机的移动技术图灵机的移动技术在解决比较复杂的问题时在解决比较复杂的问题时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)将将倒倒数数第第二二个个符符号号放放在在右右边边空空白白单单元元，将最后一个符号存储在状态中将最后一个符号存储在状态中(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将整个串包含的第一个将整个串包含的第一个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”， 等等 待待 可可 能能 的的“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图灵机扫描多个符号技术图灵机扫描多个符号技术l略略6.3.4图灵机的多道技术图灵机的多道技术为了能够保存和处理更复杂的数据，为了能够保存和处理更复杂的数据，可以将可以将TM的输入带划分为若干道的输入带划分为若干道在各道上可以存放不同的符号。在各道上可以存放不同的符号。没有改变图灵机的基本模型，没有改变图灵机的基本模型，只是将带上符号当做一个向量的组合只是将带上符号当做一个向量的组合每每个个符符号号可可以以是是一一个个K维维向向量量（将将输输入入带划分为带划分为K道）。道）。单带单带K道的图灵机道的图灵机状态转换函数一般形式为一般形式为对于对于K道图灵机道图灵机一次需要扫描一个符号的多道一次需要扫描一个符号的多道思考思考l二进制的加法二进制的加法l考查第考查第3题题例6-24:构造图灵机字母表为字母表为a接收语言接收语言L：an|n=0，且，且n为完全平方数为完全平方数基本数学公式：基本数学公式：(n+1)2=n2+2n+1思路使用三道的图灵机使用三道的图灵机第一道存放输入串；第一道存放输入串；第二、三两道作为第二、三两道作为“运算器运算器”使用。使用。初始时初始时从从i=0开始开始在第二道上放在第二道上放i2个个a比较第一道与第二道上比较第一道与第二道上a的个数的个数如果相等，就接收；如果相等，就接收；不相等，则在第三道上设置不相等，则在第三道上设置(计算计算)出出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=2aaaaBnaaaaBB22aaaBB第第3道设置为道设置为2*2+1aaaaBnaaaaB.B22aaaaaBB2*2+1第第2道设置为道设置为32i=3aaaaBnaaaaaaaaaB.B32aaaaaBB第第3道设置为道设置为2*3+1aaaaBnaaaaaaaaaBB32aaaaaaaBB2*3+1第第2道设置为道设置为42i=4aaa.aBnaaaaaaaaaaaaaaaaBB42aaaaaaaB.B上上述述动动作作一一直直重重复复下下去去，直直到到第第一一、二道上二道上a的个数相等，则接收；的个数相等，则接收；或者第一、二道或者第一、二道上上a的个数不相等的个数不相等则拒绝该输入串。则拒绝该输入串。从从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其中：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，停机停机6.3.5图灵机的查讫技术图灵机的查讫技术在在TM的的工工作作中中，有有时时需需要要对对已已经经扫扫描过的符号进行检查。描过的符号进行检查。为为了了区区分分带带上上的的某某个个符符号号是是否否已已经经检检查查过过，可可以以使使用用查查讫讫符符号号“”进进行行标标记记需要使用多道技术存储查讫符号需要使用多道技术存储查讫符号初始时，所有带上符号的查讫标记初始时，所有带上符号的查讫标记都标记为都标记为“B”。例6-25构造构造TML(M)=w2w|w0，1+分析分析依次比较依次比较2前后的符号前后的符号将带分成两条道将带分成两条道第一条道上存放输入符号串第一条道上存放输入符号串第二条道上存放检查标记第二条道上存放检查标记。初始初始输入带上的符号情况为：输入带上的符号情况为：a1a2an2b1b2bmBBBBBBBBB比较时，使用存储技术，比较时，使用存储技术，将符号将符号“2”前面的待比较符号前面的待比较符号存储存储，再与再与2后面后面相应位置相应位置的符号进行比较。的符号进行比较。某个时刻，输入带上的符号情况某个时刻，输入带上的符号情况a1a2an2b1b2bmB BB BBBM的初始状态为的初始状态为start令令a=0或或1，b=0或或1记录待比较符号：记录待比较符号：读头右移到读头右移到2的后面：的后面：找到要比较的位置：找到要比较的位置：比较后相同则继续：比较后相同则继续：2个个a必须同为必须同为0或或1读头左移到读头左移到2前：前：读头左移过读头左移过2后有两种情况后有两种情况未比较完未比较完已比较完已比较完未比较完时读头左移到待比较符号：未比较完时读头左移到待比较符号：已比较完则看右边是否处理完：已比较完则看右边是否处理完：6.3.5图灵机的子程序技术图灵机的子程序技术与通常的与通常的程序设计技术程序设计技术相似相似子程序的思想在子程序的思想在TM的构造中的构造中也是十分重要的技术。也是十分重要的技术。子子程程序序技技术术的的使使用用，可可以以将将复复杂杂的的问问题题进进行行分分解解（化化简简），同同时时，也也可可以以将将TM的构造的构造“模块化模块化”TM的的子子程程序序技技术术的的基基本本思思想想是是将将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)nm个个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)*nh个个M的状态函数分为3部分：l1)初始化：初始化：将将第第一一个个0变变为为B，并并在在最最后后一一个个0后后面设置面设置标记为标记为1该标记表明了该标记表明了增加增加0的开始位置的开始位置使使得得增增加加的的0在在第第二二个个1的的后后面面；并并将将读读/写头移动到写头移动到n个个0中的第一个处。中的第一个处。则格局变换为：则格局变换为：q00m10n=*B0m-11q10n1注意注意此时，只是消去了第一个此时，只是消去了第一个0设置标记设置标记1；但还没有在后面增加但还没有在后面增加0即将扫描原来即将扫描原来0n的的第一个第一个0l2)主控程序：主控程序：初始化初始化后，状态变为后，状态变为q1。q1相当于子程序图灵机的开始状态，相当于子程序图灵机的开始状态，进进入入子子程程序序，将将n个个0增增加加到到第第二二个个1的后面。的后面。当当退退出出子子程程序序时时，状状态态为为q5（q5也也就就是子程序图灵机的结束状态）是子程序图灵机的结束状态）此此时时需需要要将将读读/写写头头移移动动到到前前面面m个个0中剩余中剩余0的第一个处的第一个处并将这个并将这个0改为改为B，准备进入下次循环，准备进入下次循环对应的格局转换为：Bhq00m-h10n10(h-1)*n=*Bh0m-h1q10n10(h-1)*n进入子程序进入子程序=*Bh0m-h1q50n10h*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时时完完成成一一次次工工作作，并并返回到主控程序。返回到主控程序。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主程序消除主程序消除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向左寻找向左寻找0n中剩余的中剩余的0（寻找标记（寻找标记2）准备复制下一个准备复制下一个0n个个0都已复制都已复制将将2恢复为恢复为0子子程程序序结结束束，读读/写写头头仍仍然然在在0n的的第第一一个个0处处主程序：主程序：上一次循环结束，本次循环开始上一次循环结束，本次循环开始m个个0都消完，循环结束都消完，循环结束消去多余串消去多余串10n1:此时，图灵机带上的符号形式为：此时，图灵机带上的符号形式为：Bm+n+1+10mnl图灵机共有图灵机共有15个状态，其中：个状态，其中：子程序图灵机使用了子程序图灵机使用了5个状态：个状态：q1、q2、q3、q4、q5主程序图灵机使用了主程序图灵机使用了12个状态：个状态：q0、q1、q5、q6、q7、q8、q9、q10、q11、q12、q13、q14教学活动结束谢谢！谢谢！丘奇丘奇-图灵论题图灵论题在研究可计算性问题时在研究可计算性问题时一种观点认为：一种观点认为：对于任何输入，对于任何输入，算法算法都应该能够终止都应该能够终止否则，只能称其为否则，只能称其为(计算计算)过程过程。l根根据据这这个个观观点点，对对于于某某些些输输入入不不能能够够停停机机的的图图灵灵机机就就不不能能够够称称为为算算法法，也也就就是是说说，如如果果某某个个图图灵灵机机使使用用永永不不停停机机的的方方式式表表示示对对某某个个输输入入串串不不能能够够接接收的话，该图灵机就不是算法；收的话，该图灵机就不是算法；l而而只只有有对对任任何何输输入入都都必必定定停停机机的的图图灵灵机，才称为算法。机，才称为算法。l或或者者说说，接接收收递递归归语语言言的的图图灵灵机机是是算算法法，接接收收递递归归可可枚枚举举语语言言的的图图灵灵机机不不一定是算法。一定是算法。l另另一一种种观观点点则则忽忽略略停停机机问问题题，从从而而扩扩大了可计算问题的范围。大了可计算问题的范围。l丘奇丘奇图灵论点是递归论中最重要图灵论点是递归论中最重要的基本结论。的基本结论。l递归论又称可计算性理论，它是研究递归论又称可计算性理论，它是研究计算的一般性质的数学理论。计算的一般性质的数学理论。l其中心问题是：计算的本质是什么其中心问题是：计算的本质是什么?哪些问题是可计算的哪些问题是可计算的?哪些问题是不哪些问题是不可计算的可计算的?不可解的程度如何不可解的程度如何?l这些问题经过长期的探索，终于在本这些问题经过长期的探索，终于在本世纪世纪30年代由于递归论的建立而得到年代由于递归论的建立而得到了确切地解决。了确切地解决。l递归论的建立首先得益于递归论的建立首先得益于哥德尔哥德尔等人等人关于原始递归函数的提出。关于原始递归函数的提出。l所谓原始递归函数是指由初始函数出所谓原始递归函数是指由初始函数出发，经过有限次的代入与原始递归式发，经过有限次的代入与原始递归式而做出的函数。而做出的函数。l1934年哥德尔在他人的启示下，又提年哥德尔在他人的启示下，又提出了出了一般递归函数一般递归函数的概念。的概念。l一般递归函数就是由初始函数出发，一般递归函数就是由初始函数出发，经过有穷次使用代入、原始递归式和经过有穷次使用代入、原始递归式和m m算子而做成的可定义函数。算子而做成的可定义函数。l同时，数学家丘奇、克林也提出了一同时，数学家丘奇、克林也提出了一类可计算的叫做类可计算的叫做l l可定义的函数。可定义的函数。l事隔不久，丘奇、克林就分别证明了事隔不久，丘奇、克林就分别证明了l l可定义函数正好就是一般递归函数，可定义函数正好就是一般递归函数，即这两类可计算函数是等价的、一致即这两类可计算函数是等价的、一致的。的。l在这一有力的证据基础之上，丘奇公在这一有力的证据基础之上，丘奇公开发表了他早在开发表了他早在1934年就孕育过的一年就孕育过的一个论点个论点 即著名的丘奇论点：即著名的丘奇论点： 每个能行可计算的函数是一般递归的。每个能行可计算的函数是一般递归的。l也就在也就在1936年，数学家图灵定义了另年，数学家图灵定义了另一类可计算函数一类可计算函数图灵可计算函数，图灵可计算函数，并且提出了图灵论点：并且提出了图灵论点： 能行可计算的函数都是用图灵机可计能行可计算的函数都是用图灵机可计算的函数。算的函数。l一年后，图灵进一步证明了图灵可计一年后，图灵进一步证明了图灵可计算函数与算函数与l l可定义函数是等价的可定义函数是等价的l当然也和一般递归函数是等价的。于当然也和一般递归函数是等价的。于是这三类可计算函数实际上就是一种。是这三类可计算函数实际上就是一种。 这样一来，丘奇论点和图灵论点也就这样一来，丘奇论点和图灵论点也就是一回事了。现统称为丘奇是一回事了。现统称为丘奇图灵图灵论点。论点。l至此，人们便把直观的能行可计算函至此，人们便把直观的能行可计算函数归结为一般递归函数了。数归结为一般递归函数了。l对可计算性的实质有了清楚的认识。对可计算性的实质有了清楚的认识。l丘奇丘奇-图灵论题（又称为丘奇假说）：图灵论题（又称为丘奇假说）：对于任何可以用有效算法解决的问题，对于任何可以用有效算法解决的问题，都存在解决此问题的图灵机。都存在解决此问题的图灵机。l对于计算机科学，丘奇对于计算机科学，丘奇图灵论点图灵论点的意义是很直接的，它明确刻画了计的意义是很直接的，它明确刻画了计算机的本质或计算机的计算能力，确算机的本质或计算机的计算能力，确定了计算机只能计算一般递归函数。定了计算机只能计算一般递归函数。l对于一般递归函数以外的函数，计算对于一般递归函数以外的函数，计算机是无法计算的。可以说，递归性是机是无法计算的。可以说，递归性是使用计算机的前提。使用计算机的前提。l丘奇丘奇图灵论点常常又被说成：凡图灵论点常常又被说成：凡可计算的函数都可用计算机计算。当可计算的函数都可用计算机计算。当然，这是从理论意义上来讲的。然，这是从理论意义上来讲的。l从现实意义上讲，计算机还有一个现从现实意义上讲，计算机还有一个现实可计算性的问题。不过这是由另一实可计算性的问题。不过这是由另一门学科门学科计算复杂性理论来研究的。计算复杂性理论来研究的。l描述算法有三种基本方式：形式描述、描述算法有三种基本方式：形式描述、实现描述和高水平描述。实现描述和高水平描述。l形式描述需要详细给出图灵机的状态形式描述需要详细给出图灵机的状态定义，转换函数的定义，是最详细程定义，转换函数的定义，是最详细程度的算法描述；度的算法描述；l实实现现描描述述通通常常使使用用自自然然语语言言来来描描述述图图灵灵机机的的动动作作，如如读读/写写头头的的移移动动，怎怎样样存存储储数数据据等等，不不需需要要给给出出具具体体的的状状态态转换函数的描述；转换函数的描述；l高高水水平平描描述述采采用用自自然然语语言言描描述述，忽忽略略了了图图灵灵机机的的实实现现模模型型，即即通通常常意意义义上上的算法描述。的算法描述。6.5通用图灵机l图灵机是一个算法的实现装置。直观图灵机是一个算法的实现装置。直观地，一台通用的计算机，如果不受存地，一台通用的计算机，如果不受存储空间和运行时间的限制的话，它应储空间和运行时间的限制的话，它应该能够实现所有的有效算法。按照丘该能够实现所有的有效算法。按照丘奇奇-图灵论题，图灵机应该是现代计算图灵论题，图灵机应该是现代计算机的形式化的模型。机的形式化的模型。6.4图灵机变型(略)l上上面面介介绍绍了了最最基基本本的的图图灵灵机机极极其其图图灵灵机机的的构构造造技技术术，本本节节从从不不同同的的方方面面对对图图灵灵机机进进行行扩扩充充，包包括括双双向向无无穷穷带带图图灵灵机机、多多带带多多读读写写头头图图灵灵机机、不不确确定定图灵机和多维图灵机等。图灵机和多维图灵机等。l为为了了区区别别扩扩展展的的图图灵灵机机，上上面面介介绍绍的的单向无穷带图灵机，称为基本图灵机。单向无穷带图灵机，称为基本图灵机。l与与基基本本的的图图灵灵机机相相比比，它它们们都都在在不不同同的的方方面面进进行行了了扩扩展展，但但它它们们仍仍然然与与基基本本的的图图灵灵机机是是等等价价的的。对对基基本本的的图图灵灵机机进进行行扩扩展展，使使得得构构造造复复杂杂的的图图灵灵机机变得更加简便和容易。变得更加简便和容易。l由由于于这这些些扩扩展展实实际际上上都都是是技技术术上上的的一一些些改改进进，而而且且它它们们的的基基本本描描述述相相对对都都比比较较复复杂杂，在在本本书书中中，将将致致力力于于基基本本思思想想和和基基本本方方法法的的介介绍绍，而而忽忽略略那那些些比比较较烦烦琐琐的的描描述述，包包括括一一些些形形式式化化的的描述。描述。l这这与与本本书书前前面面的的较较为为严严格格的的论论述述不不同同。但但是是，根根据据基基本本思思想想和和基基本本方方法法的的介介绍绍，读读者者较较容容易易给给出出相相应应的的形形式式化化的的描描述述和和严严格格的的证证明明，只只不不过过这这些些形形式式化化的的描描述述和和严严格格的的证证明明，比比较较烦烦琐琐而而已。已。l6.4.1双向无穷带图灵机双向无穷带图灵机l基基本本的的图图灵灵机机的的模模型型中中，输输入入带带上上规规定定有有左左端端点点。所所以以，对对于于基基本本的的图图灵灵机机，读读/写写头头是是不不能能够够向向左左移移动动出出该该左左端点的。端点的。l对基本图灵机取消左端点的限制，得对基本图灵机取消左端点的限制，得到双向无穷带图灵机，双向无穷带图到双向无穷带图灵机，双向无穷带图灵机的输入带向左和向右都是无限的。灵机的输入带向左和向右都是无限的。输入带上所有空单元（包括左边和右输入带上所有空单元（包括左边和右边，全部标记为边，全部标记为B）。）。l双双向向无无穷穷带带图图灵灵机机，读读写写头头可可以以向向左左或或向向右右任任意意移移动动，其其他他定定义义与与基基本本图图灵机的一致。灵机的一致。l定理定理6-2l如如果果语语言言L能能够够被被一一个个双双向向无无穷穷带带图图灵灵机机所所接接收收，则则该该语语言言L也也能能够够被被一一个个单单向向无无穷穷带带图图灵灵机机（即即基基本本图图灵灵机）所接收。机）所接收。l6.4.2多带多读多带多读/写头图灵机写头图灵机l基基本本图图灵灵机机的的另另一一个个重重要要的的扩扩展展是是双双向向多多带带多多读读/写写头头图图灵灵机机。这这种种双双向向的的多多输输入入带带图图灵灵机机具具有有多多条条双双向向的的无无穷穷输输入入带带，每每一一个个输输入入带带都都有有自自己己的的读读/写头。写头。l在在每每一一个个动动作作中中，图图灵灵机机根根据据当当前前的的状状态态以以及及每每个个读读/写写头头正正在在扫扫描描的的带带上上符符号号确确定定图图灵灵机机的的下下一一个个状状态态，并并且且各各个个读读/写写头头可可以以相相互互独独立立地地向向各各自自希希望的方向进行移动。望的方向进行移动。l双双向向多多带带多多读读/写写头头图图灵灵机机简简称称为为多多带带图图灵灵机机(multi-tapeTuringmachine)。将将具具有有K条条输输入入带带的的图图灵灵机机简简称称为为K带图灵机带图灵机(K-tapeTuringmachine)。l多带图灵机的一个动作可以描述为：多带图灵机的一个动作可以描述为：l1)改变图灵机当前的状态；改变图灵机当前的状态；l2)在各自的输入带上印刷一个符号；在各自的输入带上印刷一个符号；l3)各各个个读读/写写头头向向各各自自希希望望的的方方向向进进行行移动。移动。lK带图灵机的状态转换函数的形式为：带图灵机的状态转换函数的形式为：l(p，(X1，X2，X3，Xk)=(q，Y1，D1，Y2，D2，Y3，D3，Yk，Dk)定理6-3l多带图灵机与基本图灵机等价。多带图灵机与基本图灵机等价。l证明：证明：l由由于于基基本本图图灵灵机机是是多多带带图图灵灵机机的的一一个个特特例例，所所以以，只只需需要要证证明明：对对于于任任意意一一个个多多带带图图灵灵机机，都都有有一一个个与与之之等等价的基本图灵机。价的基本图灵机。l略。略。6.4.3不确定图灵机l对对于于前前面面介介绍绍的的图图灵灵机机是是一一个个五五元元式式，TM=(Q，q0，q，）；）；l其中：其中：l是是QQL，R，N的的状状态态转换函数：转换函数：l（q，x）=(q，W，L，R，N)l称该图灵机是确定的图灵机。称该图灵机是确定的图灵机。l对对于于一一个个给给定定的的状状态态和和读读入入符符号号，确确定的图灵机只能有一种可选动作。定的图灵机只能有一种可选动作。l确确定定有有限限状状态态自自动动机机DFA可可以以向向非非确确定定有有限限状状态态自自动动机机NFA的的进进行行扩扩展展，类类似似地地，确确定定的的图图灵灵机机也也能能够够扩扩展展为为非确定的图灵机。非确定的图灵机。定义6-7l图图灵灵机机M称称为为不不确确定定的的图图灵灵机机（或或非非确确定定的的图图灵灵机机），除除状状态态转转换换函函数数的的定定义义外外，它它的的其其余余部部分分的的定定义义同同确确定定的的图图灵灵机机。即即对对于于某某个个状状态态q和和扫扫描描到到的的带带上上符符号号x，图图灵灵机机可可能能有有多多个个动动作作（即即M的的状状态态转转换换函函数数可可能能将将Q映映射射到到QL，R，N的的一一个子集上）。个子集上）。l不不确确定定的的图图灵灵机机是是一一个个五五元元式式，TM=（Q，q0，q，）；）；l其中：其中：lQ是有限状态集合；是有限状态集合；l是是 带带 上上 字字 母母 表表 的的 有有 限限 集集 合合 ， 用用=UB代表代表的增广集合；的增广集合；lq0Q，是开始状态；是开始状态；lqQ，是接收状态；是接收状态；l是是Q2QL，R，N的的状状态态转转换换函函数数，即即对对于于任任意意的的：（q，X）Q，l（q，X）=(q1，Y1，D1)，(q2，Y2，D2)，(qn，Yn，Dn)定义6-8l不不确确定定图图灵灵机机M=（Q，q0，q，）在在字字母母表表上上接接收收的的语语言言为为L(M)，则则lL(M)=w|w*， 且且 存存 在在 w1，w2()*，有，有q0w=*w1qw2。l对对于于不不确确定定图图灵灵机机M，一一方方面面可可以以认认为为，对对于于给给定定的的输输入入串串，M能能够够自自动动地地选选择择一一系系列列正正确确的的动动作作，使使得得M能能够够最最终终进进入入接接收收状状态态，即即不不确确定定的的图图灵机灵机M具有具有一定的具有具有一定的“智能智能”。l另另一一方方面面，由由于于处处理理一一个个输输入入串串的的所所有有可可能能的的动动作作系系列列都都是是可可以以逐逐个个列列举举的的，所所以以，对对于于任任意意的的输输入入串串，可可以以让让不不确确定定的的图图灵灵机机M逐逐一一地地按按照照当当前前列举出的动作系列去处理该输入串，列举出的动作系列去处理该输入串，l如如果果该该输输入入串串是是不不确确定定图图灵灵机机M所所能能够够识识别别的的串串（即即该该输输入入串串是是不不确确定定图图灵灵机机M接接收收语语言言的的句句子子），则则M最最终终能能够够执执行行接接收收该该输输入入串串的的动动作作系系列列，不不确确定定图图灵灵机机与与确确定定图图灵灵机机的的等等价价性性证明就是基于这一思想的。证明就是基于这一思想的。定理6-4l若若语语言言L能能被被不不确确定定的的图图灵灵机机所所识识别别，则存在确定的图灵机则存在确定的图灵机M，有，有L(M)=L。l证明：证明：l需需要要证证明明，对对于于任任意意一一个个不不确确定定的的图图灵灵机机，都都存存在在一一个个与与之之等等价价的的确确定定的的基本图灵机。基本图灵机。l定理定理6-5l不不确确定定的的图图灵灵机机和和确确定定的的图图灵灵机机是是等等价的。价的。l证明：证明：l略。略。l6.4.4多维图灵机多维图灵机l前前面面接接触触过过的的图图灵灵机机的的输输入入带带都都是是一一维维的的。也也就就是是说说，图图灵灵机机的的输输入入带带要要么么是是只只可可以以向向右右无无限限延延长长的的，要要么么是是只只可可以以向向左左或或向向右右无无限限延延长长的的，因因而而，图图灵灵机机的的读读/写写头头只只能能够够向向前前或或向向后后进进行移动。行移动。l现现在在，将将图图灵灵机机的的输输入入带带扩扩展展为为多多维维的的，这这种种图图灵灵机机的的读读/写写头头可可以以沿沿着着多多个个维维移移动动，该该图图灵灵机机称称为为多多维维图图灵灵机机（multi-demensionalTuringmachine）。）。l如如果果图图灵灵机机的的读读/写写头头可可以以沿沿着着k维维移移动动，该该图图灵灵机机称称为为k维维图图灵灵机机（k-demensionalTuringmachine）。）。lk维图灵机可以转换为一维图灵机。维图灵机可以转换为一维图灵机。l6.4.5其他图灵机其他图灵机l1多头图灵机多头图灵机l多多 头头 图图 灵灵 机机 (multi-headTuringmachine)是是指指图图灵灵机机只只有有一一条条输输入入带带，但有多个读但有多个读/写头。写头。l多多头头图图灵灵机机的的多多个个读读/写写头头，统统一一地地受受图图灵灵机机的的状状态态控控制制器器的的控控制制。多多头头图图灵灵机机根根据据当当前前的的状状态态和和多多个个读读/写写头头当当前前扫扫描描的的多多个个字字符符，确确定定当当前前多多头头图图灵机的一个动作。灵机的一个动作。l在在多多头头图图灵灵机机的的一一个个动动作作中中，各各个个读读/写写头头在在输输入入带带上上所所印印刷刷的的新新符符号号和和所所移动的方向都可以是相互独立的。移动的方向都可以是相互独立的。l如如果果多多头头图图灵灵机机有有K个个读读/写写头头，该该图图灵灵机机称称为为k头头图图灵灵机机（k-headTuringmachine）。）。l定理定理6-6l多头图灵机与基本图灵机等价。多头图灵机与基本图灵机等价。l证明：证明：l2离线图灵机离线图灵机l离离线线图图灵灵机机(off-lineTuringmachine)是是一一种种多多带带图图灵灵机机，但但对对于于其其中中一一条条输输入入带带，只只能能读读，不不能能印印刷刷上上符符号号（即不能写）。（即不能写）。l通通常常使使用用符符号号和和标标记记离离线线图图灵灵机机的的只只读读输输入入带带的的左左、右右端端点点，只只允允许许离离线线图图灵灵机机的的读读/写写头头在在和和标标记记的的区域内来回进行移动。区域内来回进行移动。l离离线线图图灵灵机机实实际际上上是是多多带带图图灵灵机机的的一一个特例。个特例。l如如果果只只允允许许离离线线图图灵灵机机的的读读/写写头头从从左左向向右右进进行行移移动动，称称这这种种离离线线图图灵灵机机为为在线图灵机在线图灵机(on-lineTuringmachine)。l虽虽然然离离线线图图灵灵机机是是多多带带图图灵灵机机的的一一个个特特例例，但但离离线线图图灵灵机机却却能能够够模模拟拟任任何何一个图灵机。一个图灵机。l定理定理6-7l离线图灵机与基本图灵机等价。离线图灵机与基本图灵机等价。l证明：证明：l对对于于基基本本图图灵灵机机M，构构造造离离线线图图灵灵机机M模模拟拟M。最最简简单单的的方方法法是是让让离离线线图图灵灵机机M比比基基本本图图灵灵机机M多多一一条条输输入入带带，用用以以复复制制基基本本图图灵灵机机的的输输入入串串，然然后后将将该该输输入入带带当当作作是是基基本本图图灵灵机机的的输输入入带带，模模拟拟基基本本图图灵灵机机进行相应的处理。进行相应的处理。l具体证明过程略。具体证明过程略。l3作为枚举器的图灵机作为枚举器的图灵机l图图灵灵机机是是递递归归可可枚枚举举语语言言的的识识别别器器和和非非负负整整函函数数的的计计算算器器。出出此此之之外外，图图灵机还可以作为语言的产生模型。灵机还可以作为语言的产生模型。l产产生生语语言言的的图图灵灵机机称称为为作作为为枚枚举举器器的的图图灵灵机机，是是一一个个特特殊殊的的多多带带（多多头头）的的图图灵灵机机，其其中中一一个个带带专专门门作作为为输输出出带带，并并且且规规定定，一一旦旦一一个个字字符符被被印印刷刷在输出带上，就不能再被更改。在输出带上，就不能再被更改。l如如果果输输出出带带的的读读/写写头头的的正正常常移移动动方方向向是是向向右右的的话话，则则输输出出带带的的读读/写写头头不不允允许向左移动。许向左移动。l基基本本的的图图灵灵机机每每次次启启动动后后，只只处处理理输输入入带带的的一一个个输输入入串串（即即对对于于多多个个串串，需需要要多多次次启启动动）；而而作作为为枚枚举举器器的的图图灵灵机机，在在启启动动之之后后，在在输输出出带带上上将将产产生生相相应应语语言言的的每每一一个个句句子子。为为了了区区别别每每个个句句子子，每每次次产产生生一一个个句句子子，就就在在该该句句子子后后面面印印刷刷一一个个分分隔隔符符号号（如如“#”）。）。l注意：注意：l如如果果作作为为枚枚举举器器的的图图灵灵机机产产生生的的语语言言是是一一个个无无穷穷的的语语言言，则则作作为为枚枚举举器器的图灵机将永不停机。的图灵机将永不停机。l4多栈机多栈机l下下推推自自动动机机实实际际上上相相当当于于非非确确定定的的多多带带图图灵灵机机，具具有有一一条条只只读读输输入入带带和和一一条存储带（模拟堆栈）。条存储带（模拟堆栈）。l多多栈栈机机(multi-stackmachine)具具有有一一条条只只读读输输入入带带，和和多多条条模模拟拟堆堆栈栈的的存存储储带带；输输入入带带上上的的读读/写写头头不不能能够够向向左左移移动动，存存储储带带上上可可以以印印刷刷上上规规定定的的符符号号，并并且且存存储储带带上上的的读读/写写头头可可以以向向左左或或向向右进行移动。右进行移动。l需需要要注注意意的的是是，存存储储带带上上的的读读/写写头头在在向向左左移移动动时时，必必须须在在当当前前扫扫描描的的带带单单元元中中印印刷刷上上空空白白符符号号B，因因此此，存存储储带带上上的的读读/写写头头在在向向左左移移动动时时，该该读读/写写头头的的右右部部全全是是空空白白符符号号B（将将当当前前的单元作为了栈顶）。的单元作为了栈顶）。l另另外外，存存储储带带上上的的读读/写写头头在在向向右右移移动动时时，一一般般情情况况下下，应应该该在在当当前前扫扫描描的的带带单单元元印印刷刷上上一一个个非非空空白白符符号号（在在特特殊殊情情况况下下，也也可可以以印印刷刷上上一一个个空空白白B，如下面介绍的计数机图灵机）。，如下面介绍的计数机图灵机）。l一一 个个 确确 定定 的的 双双 栈栈 机机 (double stackmachine)是是一一个个确确定定的的图图灵灵机机，具具有有一一条条只只读读输输入入带带和和两两条条模模拟拟堆堆栈栈的的存存储储带带；存存储储带带上上的的读读/写写头头向向左左移移动动时时，只能印刷上空白符号只能印刷上空白符号B。l定理定理6-8l一一个个任任意意的的单单带带图图灵灵机机可可以以被被一一个个确确定的双栈机模拟。定的双栈机模拟。l5计数机计数机l计计数数机机(countermachine)是是一一种种离离线线图图灵灵机机，具具有有一一条条只只读读输输入入带带，和和多多条条用用于于计计数数的的单单向向无无穷穷带带（存存储储带带），用用带带上上读读头头到到最最左左边边符符号号的的距距离离（即即单元的个数）表示所计的数。单元的个数）表示所计的数。l一一个个具具有有n条条用用于于计计数数的的带带的的计计数数机机称为称为n计数机。计数机。l用用于于计计数数的的单单向向无无穷穷带带上上只只能能有有两两种种字字符符，一一个个为为相相当当于于作作为为栈栈底底符符号号的的Z，该该字字符符也也当当作作是是记记数数带带的的首首字字符符，它它仅仅仅仅出出现现在在记记数数带带的的最最左左端端；另另一一个个就就是是空空白白字字符符B，一一条条记记数数带带上上所所记记的的数数就就是是该该记记数数带带从从Z开开始始到到该该记记数数带带的的读读/写写头头当当前前位位置置所所包包括的空白符号符号括的空白符号符号B的个数。的个数。l定理定理6-9l一一个个任任意意的的图图灵灵机机可可以以被被一一个个记记数数机机模拟。模拟。l证明：证明：l略。略。l6丘奇丘奇-图灵论题与随机存取机图灵论题与随机存取机l在在研研究究可可计计算算性性问问题题时时，一一种种观观点点认认为为：对对于于任任何何的的输输入入，算算法法都都应应该该能能够够终终止止，否否则则，只只能能称称其其为为(计计算算)过过程。程。l根根据据这这个个观观点点，对对于于某某些些输输入入不不能能够够停停机机的的图图灵灵机机就就不不能能够够称称为为算算法法，也也就就是是说说，如如果果某某个个图图灵灵机机使使用用永永不不停停机机的的方方式式表表示示对对某某个个输输入入串串不不能能够够接接收收的的话话，该该图图灵灵机机就就不不是是算算法法；而而只只有有对对任任何何输输入入都都必必定定停停机机的的图图灵灵机机，才称为算法。才称为算法。l或或者者说说，接接收收递递归归语语言言的的图图灵灵机机是是算算法法，接接收收递递归归可可枚枚举举语语言言的的图图灵灵机机不不一一定定是是算算法法。另另一一种种观观点点则则忽忽略略停停机机问题，从而扩大了可计算问题的范围。问题，从而扩大了可计算问题的范围。l1934年，丘奇使用称为年，丘奇使用称为-演算的记号演算的记号系统来定义算法；系统来定义算法；1936年图灵使用计年图灵使用计算模型算模型图灵机来描述（定义）算法。图灵机来描述（定义）算法。l丘奇丘奇-图灵论题（又称为丘奇假说）：图灵论题（又称为丘奇假说）：对于任何可以用有效算法解决的问题，对于任何可以用有效算法解决的问题，都存在解决此问题的图灵机。都存在解决此问题的图灵机。该论题该论题还没有被严格的证明。还没有被严格的证明。l对于计算机科学，丘奇丘奇图灵论点的意义是很直接的，它明确刻画了计算机的本质或计算机的计算能力，确定了计算机只能计算一般递归函数。对于一般递归函数以外的函数，计算机是无法计算的。可以说，递归性是使用计算机的前提。l因此，丘奇因此，丘奇图灵论点常常又被说图灵论点常常又被说成：凡可计算的函数都可用计算机计成：凡可计算的函数都可用计算机计算。当然，这是从理论意义上来讲的。算。当然，这是从理论意义上来讲的。从现实意义上讲，计算机还有一个现从现实意义上讲，计算机还有一个现实可计算性的问题。不过这是由另一实可计算性的问题。不过这是由另一门学科门学科计算复杂性理论来研究的。计算复杂性理论来研究的。l需要说明的是，丘奇需要说明的是，丘奇图灵论点并图灵论点并不象哥德尔不完备性定理那样能给出不象哥德尔不完备性定理那样能给出一个严格的数学证明。因为这一论点一个严格的数学证明。因为这一论点原本就不是一条定理，其中包含了一原本就不是一条定理，其中包含了一个数学上意义不明确的概念个数学上意义不明确的概念能行能行可计算。即一面是直观的日常概念，可计算。即一面是直观的日常概念，另一面是明确的数学概念另一面是明确的数学概念(一般递归函一般递归函数数)，要证明二者是一致的，这是不可，要证明二者是一致的，这是不可能的。能的。l后来人们实际上是把这一论点看作是后来人们实际上是把这一论点看作是对直观概念能行可计算的数学定义。对直观概念能行可计算的数学定义。既然是对一个不明确的概念给以明确既然是对一个不明确的概念给以明确的定义，这就无所谓正确与否，的定义，这就无所谓正确与否，因因此用不着证明也无法证明。此用不着证明也无法证明。l因为，只能列出算法的有限性、机械可执因为，只能列出算法的有限性、机械可执行性、确定性、终止性等特征，即有效算行性、确定性、终止性等特征，即有效算法说明的可解性概念是非形式化的、不严法说明的可解性概念是非形式化的、不严格的，而图灵机的概念却是形式化的和严格的，而图灵机的概念却是形式化的和严格的。但是，图灵机作为人们普遍接受的格的。但是，图灵机作为人们普遍接受的计算模型，使得将算法集中在可以用图灵计算模型，使得将算法集中在可以用图灵机描述的计算上，因此，可以认为，可计机描述的计算上，因此，可以认为，可计算问题可以等同于图灵机的可计算问题。算问题可以等同于图灵机的可计算问题。l丘奇丘奇图灵论点是递归论中最重要图灵论点是递归论中最重要的基本结论。递归论又称可计算性理的基本结论。递归论又称可计算性理论，它是研究计算的一般性质的数学论，它是研究计算的一般性质的数学理论。理论。l其中心问题是：计算的本质是什么其中心问题是：计算的本质是什么?哪些问题是可计算的哪些问题是可计算的?哪些问题是不哪些问题是不可计算的可计算的?不可解的程度如何不可解的程度如何?这些问这些问题经过长期的探索，终于在本世纪题经过长期的探索，终于在本世纪30年代由于递归论的建立而得到了确切年代由于递归论的建立而得到了确切地解决。地解决。l递归论的建立首先得益于哥德尔等人递归论的建立首先得益于哥德尔等人关于原始递归函数的提出。所谓原始关于原始递归函数的提出。所谓原始递归函数是指由初始函数出发，经过递归函数是指由初始函数出发，经过有限次的代入与原始递归式而做出的有限次的代入与原始递归式而做出的函数。函数。1934年哥德尔在他人的启示下，年哥德尔在他人的启示下，又提出了一般递归函数的概念。一般又提出了一般递归函数的概念。一般递归函数就是由初始函数出发，经过递归函数就是由初始函数出发，经过有穷次使用代入、原始递归式和有穷次使用代入、原始递归式和m m算算子而做成的可定义函数。子而做成的可定义函数。l同时，数学家丘奇、克林也提出了一同时，数学家丘奇、克林也提出了一类可计算的叫做类可计算的叫做l l可定义的函数。事可定义的函数。事隔不久，丘奇、克林就分别证明了隔不久，丘奇、克林就分别证明了l l可定义函数正好就是一般递归函数，可定义函数正好就是一般递归函数，即这两类可计算函数是等价的、一致即这两类可计算函数是等价的、一致的。在这一有力的证据基础之上，丘的。在这一有力的证据基础之上，丘奇公开发表了他早在奇公开发表了他早在1934年就孕育过年就孕育过的一个论点，即著名的丘奇论点：每的一个论点，即著名的丘奇论点：每个能行地可计算的函数都是一般递归个能行地可计算的函数都是一般递归的。的。l也就在也就在1936年，数学家图灵定义了另年，数学家图灵定义了另一类可计算函数一类可计算函数图灵可计算函数，图灵可计算函数，并且提出了图灵论点：能行可计算的并且提出了图灵论点：能行可计算的函数都是用图灵机可计算的函数。一函数都是用图灵机可计算的函数。一年后，图灵进一步证明了图灵可计算年后，图灵进一步证明了图灵可计算函数与函数与l l可定义函数是等价的可定义函数是等价的l当然也和一般递归函数是等价的。于当然也和一般递归函数是等价的。于是这三类可计算函数实际上就是一种。是这三类可计算函数实际上就是一种。这样一来，丘奇论点和图灵论点也就这样一来，丘奇论点和图灵论点也就是一回事了。现统称为丘奇是一回事了。现统称为丘奇图灵图灵论点。至此，人们便把直观的能行可论点。至此，人们便把直观的能行可计算函数归结为一般递归函数了。从计算函数归结为一般递归函数了。从而对可计算性的实质有了清楚的认识。而对可计算性的实质有了清楚的认识。l随随机机存存取取机机(randomaccessmachine-RAM)是是更更接接近近现现代代数数字字计计算算机机的的（图灵机）模型。（图灵机）模型。l随随机机存存取取机机含含有有无无穷穷多多个个存存储储单单元元，这这些些存存储储单单元元按按照照0，1，2，进进行行编编号号，每每个个存存储储单单元元可可以以存存放放一一个个任任意意整整数数。随随机机存存取取机机还还包包含含有有穷穷个个能能保保存存任任意意整整数数的的算算术术寄寄存存器器，这这些些整整数可以译码成通常的各类计算机指令。数可以译码成通常的各类计算机指令。l显显然然，如如果果选选择择一一个个适适当当的的指指令令集集合合，随随机机存存取取机机RAM就就可可以以用用来来模模拟拟任任何的现代数字计算机。何的现代数字计算机。l图图灵灵机机与与随随机机存存取取机机RAM具具有有相相同同的能力。的能力。l定定理理：如如果果随随机机存存取取机机RAM的的基基本本指指令令都都能能够够用用图图灵灵机机来来实实现现，那那么么，就就可可以以用用图图灵灵机机实实现现随随机机存存取取机机RAM。l证明：证明：l略。略。lTM等同于各种存储指令的计算机系等同于各种存储指令的计算机系统。统。l可以将可以将TM用作算法定义的精确模型。用作算法定义的精确模型。l描述算法有三种基本方式：形式描述、描述算法有三种基本方式：形式描述、实现描述和高水平描述。实现描述和高水平描述。l形式描述需要详细给出图灵机的状态形式描述需要详细给出图灵机的状态定义，转换函数的定义，是最详细程定义，转换函数的定义，是最详细程度的算法描述；度的算法描述；l实实现现描描述述通通常常使使用用自自然然语语言言来来描描述述图图灵灵机机的的动动作作，如如读读/写写头头的的移移动动，怎怎样样存存储储数数据据等等，不不需需要要给给出出具具体体的的状状态态转换函数的描述；转换函数的描述；l高高水水平平描描述述采采用用自自然然语语言言描描述述，忽忽略略了了图图灵灵机机的的实实现现模模型型，即即通通常常意意义义上上的算法描述。的算法描述。6.5通用图灵机l图灵机是一个算法的实现装置。直观图灵机是一个算法的实现装置。直观地，一台通用的计算机，如果不受存地，一台通用的计算机，如果不受存储空间和运行时间的限制的话，它应储空间和运行时间的限制的话，它应该能够实现所有的有效算法。按照丘该能够实现所有的有效算法。按照丘奇奇-图灵论题，图灵机应该是现代计算图灵论题，图灵机应该是现代计算机的形式化的模型。机的形式化的模型。l因此，应该存在一个图灵机，它可以因此，应该存在一个图灵机，它可以实现对所有图灵机的模拟，也就是说，实现对所有图灵机的模拟，也就是说，该图灵机可以实现所有有效的算法，该图灵机可以实现所有有效的算法，称该图灵机为通用图灵机（称该图灵机为通用图灵机（universalTuringmachine）。）。l定义定义6-9：通用图灵机。：通用图灵机。l通通用用图图灵灵机机就就是是能能够够模模拟拟所所有有的的图图灵灵机的图灵机。机的图灵机。6.5.1编码的目的l为为了了使使通通用用图图灵灵机机模模拟拟某某个个图图灵灵机机M，需需要要将将图图灵灵机机M作作为为通通用用图图灵灵机机的的输输入入信信息息对对待待。这这就就需需要要对对图图灵灵机机M有有一一个个统统一一的的、合合理理的的编编码码，便便于于通通用用图图灵灵机机识识别别该该图图灵灵机机的的动动作作。如如果果图图灵灵机机M接接收收给给定定的的输输入入串串，则则通通用用图图灵灵机机就就接接收收图图灵灵机机M和和它它所所接接收收的的输入串。输入串。l换换句句话话说说，为为了了使使通通用用图图灵灵机机模模拟拟某某个个图图灵灵机机M，需需要要设设计计一一个个编编码码系系统统，它它在在实实现现对对图图灵灵机机M的的表表示示的的同同时时，可可以以实实现现对对该该图图灵灵机机处处理理的的句句子子的的表表示，示，l当当考考察察一一个个输输入入串串是是否否被被一一个个给给定定的的图图灵灵机机接接收收时时，就就将将这这个个给给定定的的图图灵灵机机和和该该输输入入串串作作为为通通用用图图灵灵机机的的输输入入，再再由由通通用用图图灵灵机机去去模模拟拟该该图图灵灵机机M的的运行。运行。l由由于于通通用用图图灵灵机机需需要要模模拟拟所所有有的的图图灵灵机机，所所以以，通通用用图图灵灵机机的的字字母母表表有有可可能非常巨大，甚至可能是无穷的。能非常巨大，甚至可能是无穷的。l而而使使用用有有穷穷表表示示来来代代表表无无穷穷表表示示，正正是形式化方法的要求。是形式化方法的要求。l对对图图灵灵机机的的统统一一编编码码的的方方案案可可以以有有多多种种。一一种种最最简简单单的的思思路路是是：用用0、1对对图图灵灵机机的的符符号号进进行行编编码码。具具体体而而言言，就就是是用用0对对图图灵灵机机的的除除了了空空白白符符号号以以外的其他符号进行编码，外的其他符号进行编码，l这这样样，图图灵灵机机的的输输入入带带上上的的符符号号集集合合可可以以为为某某个个字字母母表表（可可能能包包含含多多个个字字母母），而而通通用用图图灵灵机机的的输输入入带带上上的的符符号号集集合合仅仅仅仅为为0，B，输输入入符符号号集集合合也也仅仅为为：0。同同时时，也也使使用用0对对图图灵灵机机的的状状态态转转换换函函数数进进行行编编码码。使使用用1表示编码之间的分隔。表示编码之间的分隔。6.5.2编码方法编码方法l设设TM=(Q，q0，q，)l其中其中lQ=q1，q2，qnl=x1，x2，xkl=x1，x2,xk，xk+1，xmlq0=qiq=qj是任意一个图灵机。是任意一个图灵机。l为为了了使使通通用用图图灵灵机机能能够够模模拟拟该该图图灵灵机机M，将该图灵机将该图灵机M进行编码。进行编码。l编编码码由由三三部部分分构构成成，编编码码开开始始部部分分+状状态态转转换换函函数数编编码码+输输入入带带上上的的符符号号串串w的编码。的编码。l编编码码开开始始部部分分表表示示了了整整个个图图灵灵机机M的的情况。情况。l编码步骤：编码步骤：l1）编码的开始部分：）编码的开始部分：l该该图图灵灵机机有有n个个状状态态q1，q2，qn，可以使用对应的编码分别表示为，可以使用对应的编码分别表示为lq1：0，q2：00，qn：0nl图图灵灵机机有有m个个带带上上符符号号（其其中中前前k个个为为输输入入符号），可以使用对应的编码分别表示为符号），可以使用对应的编码分别表示为lx1：0,x2：00，qk：0k，qm：0ml那么，该图灵机编码的开始部分为：那么，该图灵机编码的开始部分为：l0n10m10k10s10t10r10u10vl其中：其中：l0s，0t，0r，分分别别代代表表开开始始状状态态、接接收收状态和拒绝状态对应的编码；状态和拒绝状态对应的编码；l0u代代表表输输入入带带左左端端点点的的编编码码；此此处处，令令u=k+1；l0v代代表表输输入入带带空空白白符符号号B的的编编码码；此此处，令处，令v=m。l2）状态转换函数编码状态转换函数编码l同同样样，使使用用用用0，1对对图图灵灵机机的的动动作作函函数进行编码。数进行编码。l图图灵灵机机读读/写写头头的的移移动动方方向向为为，R，L，N，可可以以使使用用对对应应的的编编码码分分别别表表示示为为lR（D1）：01=0，L（D2）：02=00，N（D3）：）：03=000l图灵机的动作函数的一般形式为：图灵机的动作函数的一般形式为：l(qi，xj)=(qk，xl，Dm)l可以使用对应的编码分别表示为可以使用对应的编码分别表示为l0i10j10k10l10ml因此，可以使用因此，可以使用l11111121111r111l来来表表示示整整个个图图灵灵机机的的编编码码（使使用用11进进行行分分隔隔，使使用用111作作为为开开始始和和结结束束的的标标记记）。其其中中：r是是状状态态转转换换函函数数(qi，xj)=(qk，xl，Dm)对应的编码对应的编码l0i10j10k10l10m1l3）图灵机输入带上符号串编码图灵机输入带上符号串编码l图图灵灵机机输输入入带带上上符符号号串串为为y1y2yn，有有m个个带带上上符符号号（其其中中前前k个个为为输输入入符符号号），可可以以使使用用对对应应的的编编码码分分别别表表示为示为ly1：0z1，y2：0z2，qn：0znl其其中中：zi表表示示yi的的序序号号，0zi表表示示yi的的编编码。码。l那那么么，该该图图灵灵机机的的输输入入带带符符号号的的编编码码为：为：l0z110z2110znl最最后后，得得到到图图灵灵机机的的编编码码和和输输入入带带上上的的符符号串号串w的编码为：的编码为：l0n10m10k10s10t10r10u10v11111121111r111wl即即l0n10m10k10s10t10r10u10v11111121111r1110z10z20zn6.6图灵机与短语结构语言l实实际际上上，任任何何一一个个短短语语结结构构语语言言都都可可以被图灵机接收。以被图灵机接收。定理6-12l任任意意一一个个短短语语结结构构文文法法G，都都对对应应有有一个图灵机一个图灵机M，使得，使得L(G)=L(M)证明：证明：略。略。6.7线性有界图灵机与相关语言l定义定义6-10线性有界的图灵机的定义线性有界的图灵机的定义TM是线性有界的图灵机是线性有界的图灵机(LBAM)l所所有有操操作作都都局局限限于于带带上上预预先先设设置置的的区区间内间内(读读/写头不允许离开该区间写头不允许离开该区间)。l一般，用一般，用$和和来标记左、右边界。来标记左、右边界。教学活动结束谢谢！谢谢！