有限自动机理论06章图灵机-简化

1、 第六章第六章 图灵机图灵机 图灵机图灵机(即即TuringM-TM) 由由A.Turing于于1936年，在论文年，在论文可计算数字及其在判断性问题可计算数字及其在判断性问题中的应用中的应用里提出。里提出。 TM是可计算性的数学模型是可计算性的数学模型 可计算的特点是可计算的特点是: 有穷、离散、有穷、离散、机械执行、停机机械执行、停机。 为计算机的发展奠定了为计算机的发展奠定了理论基础理论基础。图灵图灵:计算机理论之父计算机理论之父冯诺依曼冯诺依曼:计算机体系结构之父计算机体系结构之父 图灵机可以模拟电子计算机的图灵机可以模拟电子计算机的计计算能力算能力。 使用图灵机可以解决计算机程序使用

2、图灵机可以解决计算机程序的的可计算问题可计算问题。 图灵机的图灵机的构造技术构造技术类似于计算机类似于计算机的的编程编程(设计指令设计指令)技术技术。6.1 图灵机的基本模型图灵机的基本模型 6.1.1 图灵机的定义图灵机的定义 图灵机的图灵机的物理模型物理模型a1a2a3 aj anan+1FSC一个有限状态控制器一个有限状态控制器(FSC)一个外部的存储设备一个外部的存储设备 可以向右扩展的无限长度带可以向右扩展的无限长度带 带上具有带上具有左端点左端点，使用，使用“”表示表示l图灵机直接扫描输入带上左端点右边图灵机直接扫描输入带上左端点右边的的第一个符号第一个符号。 带分解为单元，每个单

3、元可以为带分解为单元，每个单元可以为空或存放字母表上的字母符号空或存放字母表上的字母符号 带的空白单元标记为带的空白单元标记为B 有限状态控制器通过一个有限状态控制器通过一个读读/写头写头与带进行耦合。与带进行耦合。 在某个时刻，有限状态控制器处在某个时刻，有限状态控制器处于某个状态，读于某个状态，读/写头将扫描带上的写头将扫描带上的一个单元一个单元 依照依照状态状态和扫描到的带上和扫描到的带上符号符号，图灵机将有一个图灵机将有一个动作动作如下：如下： 有限状态控制器的有限状态控制器的状态状态进行进行改变改变； 把刚刚扫描过的单元上符号擦除掉，把刚刚扫描过的单元上符号擦除掉，并并印刷上一个新的

4、符号印刷上一个新的符号（有可能印刷上（有可能印刷上与原来符号相同的符号）；与原来符号相同的符号）； 读读/写头向左或者向右写头向左或者向右移动移动一个单元；一个单元；或者读或者读/写头写头不移动不移动。五元式描述动作 其中：其中：x，W （ 的的增广集合增广集合） 图灵机处于状态图灵机处于状态q，扫描到符号，扫描到符号x，则则状态变换为状态变换为q，印刷上新的符号，印刷上新的符号W，读读/写头写头向左向左、或、或向右向右 或或不移动不移动。例例6-1 用用TM接收接收 语言语言a2n |n0 图灵机带上符号串为：图灵机带上符号串为： aaaaaaB 图灵机初始处于状态图灵机初始处于状态even

5、，将要扫描，将要扫描第一个第一个a，则，则 /可省略可省略l若带上若带上a的个数为偶数，的个数为偶数， 则图灵机经过多个动作后，处于则图灵机经过多个动作后，处于接收状态接收状态accept；l若带上若带上a的个数为奇数的个数为奇数， 根据根据 ，图灵机，图灵机将不会停机，可以永远继续下去将不会停机，可以永远继续下去 这与其它的自动机不同，即图灵这与其它的自动机不同，即图灵机机可能会可能会导致导致永不停止永不停止的计算。的计算。例例6-2 语言为语言为a2n|n0定义定义6-1 图灵机是一个五元式图灵机是一个五元式lTM=(Q， q0， q，) Q是有限状态集合；是有限状态集合； 是字母表的有限

6、集合是字母表的有限集合 =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 图灵机的格局图灵机的格局ID w1qw2w1是读是读/写头左边带上的符号

7、串写头左边带上的符号串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=

8、B )使用使用 = 表示图灵机的格局转换表示图灵机的格局转换l若若（q，x）=( q，x，L)，则，则 r1yqxr2=l若若（q，x）=( q，x，N)，则，则 r1yqxr2=l若若（q，x）=( q，x，R)，则，则 r1yqxr2= r1qyxr2r1yqxr2r1y xqr2使用使用=+ +代表格局的代表格局的多次多次变换变换使用使用=* *代表格局的代表格局的任意次任意次变换变换定义6-4l图灵机图灵机M=（Q， q0， q，）在字母表在字母表上接收的语言为上接收的语言为L(M)，则则 L(M)=w|存在存在w1，w2()* 有有 =* q0ww1qw2定义6-5 完全的图灵机 如

9、果图灵机对于如果图灵机对于一切输入串一切输入串都能够停都能够停机机-完全的图灵机。完全的图灵机。 完全的图灵机接收的语言完全的图灵机接收的语言L称为称为递归递归语言语言(图灵可判定语言图灵可判定语言) 6.1.2 图灵机的构造图灵机的构造例例-接收仅有一个接收仅有一个1的的0、1串串TM=(q0，q1，q2,0，1, q0，q2,)=0，1，B例例6-4 构造图灵机构造图灵机 接收语言接收语言 anbn|n0思路思路1：l当图灵机遇到当图灵机遇到a时，将时，将a改写为改写为# 向右寻找向右寻找b，找到，找到b，将，将b改写为改写为# 再向左找再向左找a 直到所有直到所有a都找完。都找完。 (向

10、左找的向左找的a是整个是整个a串串最左边的最左边的a)指令为指令为读到一个读到一个a，用，用#代替它，向右找代替它，向右找b 处于状态处于状态del_b，扫描到，扫描到b，用，用#代替代替它，向左寻找它，向左寻找a，（从重复循环），（从重复循环） /最右的最右的a seek_a状态时，没有再发现状态时，没有再发现a(都已被都已被#所代替所代替)，还需要，还需要检查检查是否所有的是否所有的b都已经被扫描过。都已经被扫描过。问题问题l该图灵机能接收该图灵机能接收anbn的所有串的所有串 但该图灵机也能接收但该图灵机也能接收aababb 等等 原因：使用原因：使用#代表已扫描的代表已扫描的a和和b

11、没有保证没有保证a和和b的的顺序顺序。l为了区别原来的字母为了区别原来的字母a和和b 使用使用#和和$分别代替字母分别代替字母a和和b 当当a和和b都识别后，带上的串为都识别后，带上的串为 #$B例例6-5 修改上例：修改上例：读到一个读到一个a，用，用#代替它，向右寻找代替它，向右寻找b处于状态处于状态del_b，扫描到，扫描到b，用，用$代替代替它，向左寻找它，向左寻找a，（从重复，（从重复循环循环）在在seek_a状态时，没有再发现状态时，没有再发现a（都（都已经被已经被#所代替）所代替） 需检查是否所有的需检查是否所有的b都已经被扫描过都已经被扫描过 还还必须注意必须注意#与与$的顺序

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

13、否所有的b都已经被扫描过。都已经被扫描过。 某些不需要定义的规则某些不需要定义的规则 /无无a /无无a 无无b /b少少 /无无b /不可能不可能 /b多多思考思考l能否给对图灵机的能否给对图灵机的性能性能进行评价？进行评价？l对于相同的输入串，比较两种算法的对于相同的输入串，比较两种算法的 图灵机的图灵机的指令数量指令数量 每条每条指令的执行次数指令的执行次数（总次数）（总次数） 新印刷符号的数量新印刷符号的数量； 读读/写头移动的次数写头移动的次数例例6-7 anbn|n0第三种算法第三种算法思路思路: 首先检查输入串是否为首先检查输入串是否为a+b+的格式；的格式； 如果不是，则拒绝该

14、串如果不是，则拒绝该串 如果是，检查如果是，检查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时时,扫描

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

16、接收语言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是图灵可计算的是图灵可计算的。l自动机都具有识别语言的功能自动机都具有识别语言的功能 图灵机还具有图灵机还具有“计算计算”功能功能 可以规定非负整数的可

17、以规定非负整数的表示方法表示方法,从而实现从而实现非负整数的函数求值非负整数的函数求值。K元函数可以转换为多个二元函数元函数可以转换为多个二元函数仅考虑二元函数仅考虑二元函数l使用使用“一进制一进制”方式表示一个非负整方式表示一个非负整数，即数，即 使用使用0m表示整数表示整数m。l若需要计算若需要计算f(m，n)，则可以在输入，则可以在输入带上存放带上存放0m10n形式的串形式的串l图灵机将串改写为图灵机将串改写为0f(m，n)的形式，即的形式，即表示出计算表示出计算f(m，n)的结果。的结果。加法图灵机加法图灵机l对于非负整数对于非负整数m、n，计算，计算m+n。分析分析 图灵机输入图灵机

18、输入0m10n 需要输出需要输出0m+n算法：算法：将将1改写为改写为0，最后一个，最后一个0改写为改写为B(可能是可能是1改写成的改写成的0)lTM=（Q，,start， accept，）Q=start，q1，q2，accept=0，1=0，1，Bstart 可以是一般状态可以是一般状态遇到遇到B，向左找，向左找0最后的最后的0改为改为Bstart 仅为开始状态仅为开始状态 串为串为1或或10n 第第1个个0 跳过剩余的跳过剩余的0 遇到遇到1，改为，改为0 遇到遇到B，向左找，向左找0最后的最后的0改为改为B注意注意l扫描扫描1左边和右边的左边和右边的0的工作都由的工作都由 完成。完成。

19、整个串整个串只允许一个只允许一个1。例例6-16 构造构造TMl实现非负减法实现非负减法(真减法真减法)m n = m-n mn = 0 mn (即全是即全是B)或或思路思路1带上字符串的形式为带上字符串的形式为0m10n寻找寻找1左边的左边的0，删除，删除1右边的右边的0 可能在寻找可能在寻找1左边的左边的0时结束时结束(mn) 或者在删除或者在删除1右边的右边的0时结束时结束(mn)(1)扫描第扫描第1个个0(2) /原标记的原标记的1 (3) /将将1后的第后的第1个个0变为变为1 /后加的后加的 start,1 del_0,B (4) 向左找向左找B 读写头位置读写头位置 转（转（1）

20、 重复上述动作重复上述动作?mn(5)n，B，L /遇到最右边的遇到最右边的B，表示，表示1右边已没有右边已没有0 n，1，mn ，B，L 将将1改写为改写为B n ，0， mn ，0，L n ，B，accept，0，N 补写补写1个个0，结束，结束 m n(6) start将遇到第一个将遇到第一个1 此时，输入带上全为，表示此时，输入带上全为，表示mnl在第在第(5)步开始时，输入带上的字符串步开始时，输入带上的字符串形式为：形式为： BBBBB000011 11B m-n-1 n 左边左边B有有n+1个个mn根据根据TM的动作，的动作， 在左边消除一个在左边消除一个0，再去，再去1的右边找

21、的右边找0 当发现当发现1的右边已经没有的右边已经没有0时，此时减时，此时减法工作应该结束法工作应该结束mn 但但左边多消除了一个左边多消除了一个0 因此，第（因此，第（5）步，在）步，在mn的的控制下的的控制下除了将除了将1改写为改写为B外外 还应该将一个还应该将一个0补写补写回来，才能结束减回来，才能结束减法工作。法工作。mnl此时，输入带上的字符串形式为：此时，输入带上的字符串形式为： BBBB0000 B m-n个个 lm=n时，整个减法的结果应该为时，整个减法的结果应该为0l输入带全为输入带全为Bl特殊：特殊：m=n=0，则串为，则串为1BB 结束结束思路思路2 自学自学l图灵机反复

22、进行下面的工作：图灵机反复进行下面的工作： 先用先用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)向右

23、搜寻向右搜寻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，就相当

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

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

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

27、符号 向向左左扫描输入带上的其他符号扫描输入带上的其他符号遇到遇到结束结束思考：构造TM 识别语言 1）该语言每个句子的）该语言每个句子的(倒数倒数)第第n个符号个符号 在该句子中仅仅出现在该句子中仅仅出现K次。次。n=1，2，3，m；K=1，2，3，L2）该语言每个句子的）该语言每个句子的(倒数倒数)第第n个符号个符号 在该句子中出现次数在该句子中出现次数不多于不多于(不少于不少于)K次。次。n=1，2，3， ，m ；K=1，2，3，L6.3.2图灵机的移动技术图灵机的移动技术在解决比较复杂的问题时在解决比较复杂的问题时 TM可能需要将输入带上一组连续的可能需要将输入带上一组连续的非空符号非

28、空符号左移左移或者或者右移右移若干个单元。若干个单元。 使用使用n元式元式存储存储多个符号多个符号 合适的时候合适的时候再将这些符号印刷到需要再将这些符号印刷到需要的位置上。的位置上。例6-14构造TM=a,b,c，将输入串，将输入串右右移两个单元移两个单元 使用三元组使用三元组q，a1，a2表示状态表示状态 q表示原来的状态；表示原来的状态； a1、a2可以代表可以代表a、b、c设串长度设串长度=2(1)扫描第一个符号，并存储扫描第一个符号，并存储 (2)扫描第二个符号，并存储扫描第二个符号，并存储 (3)将将a1放在放在a3位置位置,将将a3存储存储 (4) 将倒数第二个符号放在右边空白单

29、元，将倒数第二个符号放在右边空白单元，将最后一个符号存储在状态中将最后一个符号存储在状态中(5) 将最后一个符号放在带上将最后一个符号放在带上其中规则其中规则(3) 需要需要重复多次使用。重复多次使用。思考：思考：l当串当串 长度为长度为0 时时l当串当串 长度为长度为1 时时 本例使用三元组表示特殊状态本例使用三元组表示特殊状态 也可以使用二元组表示特殊状态也可以使用二元组表示特殊状态 如如q，a1，a2可以记为可以记为q，a1a2 （n元组也可以表示为二元组）元组也可以表示为二元组）对带上符号进行移动 一般只是比较复杂的一般只是比较复杂的TM的识别任务的识别任务中的一部分工作中的一部分工作

30、 移动本身移动本身不会涉及不会涉及到串的接收或拒绝到串的接收或拒绝问题问题 复杂的复杂的TM可以继续从可以继续从end_move状态状态开始其他的工作开始其他的工作思考：构造TM 将整个输入串前两个符号将整个输入串前两个符号删除删除。思路思路将带上符号将带上符号从右向左从右向左移动两个单元。移动两个单元。例6-15构造构造TM 输入字母表为输入字母表为0，1 在输入串的开始处添加子串在输入串的开始处添加子串10。略。略。例6 -16构造构造TM =a，b，c 将输入串包含的第一个将输入串包含的第一个abc子串子串删除删除。思路思路 存储技术寻找到第存储技术寻找到第1个个abc子串的位置子串的位

31、置 将后面的符号将后面的符号向左向左移动三个单元。移动三个单元。 略。略。例6-18 构造构造TM ，输入字母表为，输入字母表为0，1，要，要求求M接收语言接收语言L：该语言的每个字符串该语言的每个字符串包含包含且且仅只能包含仅只能包含一个一个101子串子串(有有且且仅有仅有一一个个101，不可不可以没有以没有101子串）子串） 思路思路当识别出第一个当识别出第一个101后，后， 检查输入带上剩余的串检查输入带上剩余的串 不能再包含不能再包含101 TM=（Q，start， accept，） Q=start，q，0，q，1，q，10，check，check，0，check，1，check，10

32、，refuse，accept=0，1=0，1，B(1)扫描第一符号扫描第一符号 空串空串(2)期待期待1的出现的出现 (3)已经扫描到已经扫描到“1”，等待可能的，等待可能的“0” (4)已经扫描到已经扫描到“10”，等待可能的，等待可能的“1” (5)已扫描到已扫描到101，检查串的剩余部分，检查串的剩余部分 (6) (7) （8）的第）的第2条指令与（条指令与（9）可以省略）可以省略(8) (9)整个输入串中没有整个输入串中没有101 结束结束(10)整个输入串只有一个整个输入串只有一个101 思考思考 构造构造TM ，接收语言，接收语言L： 该语言的每个句子必须包含该语言的每个句子必须包

33、含两个两个101例6-19 构造构造TM ，接收语言，接收语言L： 该语言的每个句子该语言的每个句子最多只能包含一个最多只能包含一个100子串（子串（可以没有可以没有100子串子串）。）。思路思路 接收接收1个个100子串的所有串；子串的所有串； 接收没有接收没有100子串的所有串。子串的所有串。例例6-23 构造构造TM接收语言接收语言L： 该语言的每个句子该语言的每个句子不包含不包含子串子串100。思路思路当识别出第一个当识别出第一个100后，就拒绝。后，就拒绝。6.3.4图灵机的多道技术图灵机的多道技术 为了能够保存和处理更复杂的数据，为了能够保存和处理更复杂的数据，可以将可以将TM的输

34、入带划分为若干道的输入带划分为若干道在各道上可以存放不同的符号。在各道上可以存放不同的符号。 没有改变图灵机的基本模型，没有改变图灵机的基本模型，只是将带上符号当做一个向量的组合只是将带上符号当做一个向量的组合每个符号可以是一个每个符号可以是一个K维向量（将输入维向量（将输入带划分为带划分为K道）。道）。单带单带K道的图灵机模型道的图灵机模型 a11 a21 ai1 an1 B a12 a22 ai2 an2 B a1k a2k aik ank B FSC状态转换函数状态转换函数一般形式为一般形式为 对于对于K道图灵机道图灵机一次需要扫描一个单元的多道一次需要扫描一个单元的多道3道道TM进行二

35、进制数加法运算进行二进制数加法运算l考虑考虑 3个基本加法规则个基本加法规则 ： 0+0 0+1 ( 1+0 ) 1+1 l还需要考虑还需要考虑进位进位情况情况(全加器）全加器）l第一、二道存放两个操作数第一、二道存放两个操作数l第三道存放计算结果第三道存放计算结果l第第2个单元存放个单元存放B（避免溢出）（避免溢出）l读写头已经在最低位读写头已经在最低位(最右端最右端)单元单元 没有进位没有进位 0+0 0+1 1+0 1+1进位进位 两个数长度不一致两个数长度不一致(左端补充左端补充B) 结束结束 思考思考l两个数长度不一致两个数长度不一致(左端补充左端补充0) l十进制的加法十进制的加法

36、l二进制的减法二进制的减法l十进制的减法十进制的减法l乘法与除法乘法与除法l软件计算机软件计算机例例6-24:构造图灵机构造图灵机 字母表为字母表为a，接收语言，接收语言L： an|n=0，且，且n为完全平方数为完全平方数基本数学公式：基本数学公式： (n+1)2=n2+2n+1思路使用三道的图灵机使用三道的图灵机 第一道存放输入串；第一道存放输入串； 第二、三两道作为第二、三两道作为“运算器运算器”使用：使用： 第二道存放第二道存放i2个个a 第三道存放第三道存放2*i+1个个a初始时初始时 a a a a B B B B B B B B B B B 原始算法原始算法从从i=0开始开始 在第

37、二道上放在第二道上放i2个个a 比较第一道与第二道上比较第一道与第二道上a的个数的个数 如果相等，就接收；如果相等，就接收；不相等，则在第三道上设置不相等，则在第三道上设置 2*i+1个个a， 将第三道上的将第三道上的a加入到第二道上去，加入到第二道上去， 从而，在第二道上形成从而，在第二道上形成(i+1)2个个a 再与第一道上再与第一道上a的个数进行比较。的个数进行比较。 初始初始 i=0 第第2道道a个数为个数为02 aaa aB n个个aBBBBB 02=0BBBBB 比较第一、二道上比较第一、二道上a的个数的个数如果相等，就接收；如果相等，就接收； 第第3道设置为道设置为2*0+1aa

38、a aBBBBBB 02aBB BB 2*0+1第第2道设置为道设置为12 i=1(3道道a加入加入2道道) aaa aBaBBBB 12aBBBB比较第一、二道上比较第一、二道上a的个数的个数如果相等，就接收；如果相等，就接收；二道二道a多，拒绝；多，拒绝；第第3道设置为道设置为2*1+1aaa aB naBBBB 12aaaBBB 2*1+1第第2道设置为道设置为22 i=2aaa aB naaaaB BB 22aaaBBB比较第一、二道上比较第一、二道上a的个数的个数如果相等，就接收；如果相等，就接收；二道二道a多，拒绝；多，拒绝；第第3道设置为道设置为2*2+1aaa aB naaaa

39、B.BB 22aaaaaBBB 2*2+1第第2道设置为道设置为32 i=3aaa aB naaaaaaaaaB.BB 32aaaaaBBB比较第一、二道上比较第一、二道上a的个数的个数如果相等，就接收；如果相等，就接收；二道二道a多，拒绝；多，拒绝；第第3道设置为道设置为2*3+1aaa aB naaaaaaaaaBBB 32aaaaaaaBBB 2*3+1第第2道设置为道设置为42 i=4aaa. aB naaaaaaaaaaaaaaaaBBB 42aaaaaaaB. BB比较第一、二道上比较第一、二道上a的个数的个数如果相等，就接收；如果相等，就接收；二道二道a多，拒绝；多，拒绝； 上述

40、动作一直重复，直到第一、二道上述动作一直重复，直到第一、二道上上a的个数相等，则接收；的个数相等，则接收； 或者第一道的或者第一道的a的个数小于第二道上的个数小于第二道上a的个数，则拒绝该输入串。的个数，则拒绝该输入串。从从i=2过渡过渡i=3到时，图灵机输入带为：到时，图灵机输入带为： a a a a a a a a a B a a a a B B a a a a a B B 改进算法改进算法准备工作：准备工作： 特殊情况：特殊情况： n=0或或n=1 进行处理进行处理； 二道存放二道存放aaaa；三道存放；三道存放aaa (1) 二道与一道的二道与一道的 a比较比较： 相等，接收；相等，接

41、收； 二道二道a多，拒绝；多，拒绝； 一道一道a多，转多，转(2) (2)三道三道增加增加aa (3) 三道的三道的a复制复制到二道；转到二道；转(1) 准备工作准备工作 n=0 二、三道存放二、三道存放a n=1 二、三道存放二、三道存放aa 二、三道存放二、三道存放aaa 二道再存二道再存a 此时，此时， 二道存放二道存放aaaa；三道；三道存放存放aaa（1）一道和二道进行比较）一道和二道进行比较 左移到左端点左移到左端点 开始比较开始比较 二道二道a多，拒绝多，拒绝 接收接收 二道二道a少少（2）三道增加）三道增加2个个a 左移找到第三道最后的左移找到第三道最后的a 增加增加1个个a

42、再增加再增加1个个a，三道，三道a准备复制到二道准备复制到二道(3)三道三道a复制到二道末尾复制到二道末尾 左移到左移到左端点左端点 开始复制开始复制 三道三道a改为改为b，向右寻找二道末尾，向右寻找二道末尾 复制复制1个个a，向左寻找三道，向左寻找三道b 跳过跳过3-B 跳过跳过3-a 将将b还原为还原为a 向右寻找三道是否还有向右寻找三道是否还有a需要复制需要复制 三道还有三道还有a，继续复制，继续复制 复制结束，继续比较一道和二道复制结束，继续比较一道和二道思考：一、二道比较的的第思考：一、二道比较的的第2种算法种算法l读写头在第二道的最后一个读写头在第二道的最后一个a处处 第一次第一次

43、 二道二道a少少 拒绝拒绝 接收接收思考：思考：三道三道a复制到二道复制到二道的第的第2种算法：种算法：从三道从三道最后的最后的a开始复开始复制制需要注意第一次复制的特殊性需要注意第一次复制的特殊性aaaaB aaaa.aBaaaaaB aaaaaB6.3.5图灵机的图灵机的查讫查讫技术技术 在在TM的工作中，有时需要对已经扫的工作中，有时需要对已经扫描过的符号进行检查。描过的符号进行检查。 为了区分带上的某个符号是否已检查为了区分带上的某个符号是否已检查过，可以使用查讫符号过，可以使用查讫符号“”进行标记进行标记 需要使用多道技术存储查讫符号需要使用多道技术存储查讫符号 初始时，所有带上符号

44、的查讫标记初始时，所有带上符号的查讫标记都标记为都标记为“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后面后面相应位置相应位置的符号进行比较。的符号进行比较。某个时刻，输入带上

45、的符号情况某个时刻，输入带上的符号情况 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后有两种情况后有两种情况未比较完未比较完 已比较完已比较完未比较完时读头左移到待比较符号：未比较完时读头左移到待比较符号： 已比较完则看右边是否处理完：已比较完则看右边是否处理完： 6.3.5图灵机

46、的子程序技术图灵机的子程序技术 与通常的与通常的程序设计技术程序设计技术相似相似 子程序的思想在子程序的思想在TM的构造中的构造中也十分重要。也十分重要。 子程序技术的使用，可以将复杂的问子程序技术的使用，可以将复杂的问题进行分解（化简），同时，也可以将题进行分解（化简），同时，也可以将TM的构造的构造“模块化模块化” TM的子程序技术的基本思想是将的子程序技术的基本思想是将TM中需要中需要重复重复使用的功能使用的功能分解分解出来，出来，使用一个使用一个子子TM实现该功能（子程序）实现该功能（子程序） 完成整个功能的图灵机为完成整个功能的图灵机为M（主程序）（主程序） 完成某个特定功能的子图灵

47、机为完成某个特定功能的子图灵机为M（子程序）（子程序）子图灵机子图灵机M 从状态从状态q开始开始 到一个状态到一个状态f结束结束状态状态q、f是图灵机是图灵机M的两个的两个一般状态一般状态 当图灵机当图灵机M进入状态进入状态q时，就启动时，就启动M（相当于（相当于调用调用子程序）；子程序）； 当当M进入状态进入状态f时就时就返回返回到到M（相当（相当于子程序结束）。于子程序结束）。注意： 子图灵机子图灵机M中可以有多个状态中可以有多个状态 但仅有两个状态（即但仅有两个状态（即M的的开始状态开始状态q和和接收状态接收状态f）是与主程序的图灵机）是与主程序的图灵机M共用的共用的 子图灵机子图灵机M

48、的其他状态是的其他状态是私有的私有的，不，不能被主程序的图灵机能被主程序的图灵机M所使用。所使用。例6-26构造构造TM ，完成正整数的乘法运算。，完成正整数的乘法运算。正整数的乘法运算的数学公式：正整数的乘法运算的数学公式： mn=(1+1+1) n m个个1使用使用TM实现正整数的乘法运算实现正整数的乘法运算 TM的输入带上存放串的输入带上存放串0m10n， 处理后，使得带上的串变为处理后，使得带上的串变为0m*n形式形式处理该问题的一般的方法为：处理该问题的一般的方法为： 当从当从1的左边消去一个的左边消去一个0后，在后，在0n的后的后面增加面增加n个个0(补补1作为分隔标记作为分隔标记

49、)； 当当1左边的所有的左边的所有的0（共有（共有m个）消完个）消完后，再消去后，再消去多余的符号多余的符号（两个两个1和原来和原来的的0n），就得到了），就得到了0m*n形式。形式。在在0n后面添加后面添加n个个0的过程是重复的，的过程是重复的， 可以使用子程序技术。可以使用子程序技术。在某个时刻，在某个时刻，TM输入带上的输入带上的符号符号为：为： Bh0m-h10n10h*n已经完成已经完成(1+1+1+1)*n h个个M的状态函数分为的状态函数分为3部分：部分：l1)初始化：初始化： 将第一个将第一个0变为变为B，并在最后一个，并在最后一个0后后面设置面设置标记为标记为1 该标记表明了

50、该标记表明了增加增加0的开始位置的开始位置 使得增加的使得增加的0在第二个在第二个1的后面；并将的后面；并将读读/写头移动到写头移动到n个个0中的第一个处。中的第一个处。则格局变换为：则格局变换为： q00m10n=* B0m-11sub_start0n1此时，只是消去了第一个此时，只是消去了第一个0 设置标记设置标记1； 但还没有在后面增加但还没有在后面增加0 即将扫描即将扫描0n的的第一个第一个0l2)主控程序：主控程序： 初始化初始化后，状态变为后，状态变为sub_start。 sub_start是是子程序图灵机的开始状态，子程序图灵机的开始状态， 调用子程序，将调用子程序，将n个个0增加到第二个增加到第二个1的后面。的后面。 当退出子程序时，状态为当退出子程序时，状态为sub_end sub_end就是子程序图灵机的结束状态就是子程序图灵机的结束状态 然后将读然后将读/写头移动到写