基本图灵机及图灵机的构造技术0分课件.ppt

第五章第五章 图灵机图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质n该模型的每个过程都是有穷可描述的；n过程必须是由离散的、可以机械执行的步骤组成图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力n通过研究TM来研究递归可枚举集和部分递归函数n为算法和可计算性研究提供了形式化描述工具1基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分主要内容主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点: TM的定义、TM的构造 n难点: TM的构造2基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分FinitecontrolX1BB...X2XnXi带（带（tape））单元格（单元格（cell））带符（带符（tape symbol））n 读写头在每一时刻扫描带上的一个单元读写头在每一时刻扫描带上的一个单元n 带有一个最左单元，向右则是无限的带有一个最左单元，向右则是无限的n 带的每个单元可容纳一个带符号带的每个单元可容纳一个带符号开始时，最左边开始时，最左边n个单元装着输入（个单元装着输入（n>＝＝0，，n为有限数），它是为有限数），它是一个字符串，符号都选自一个字符串，符号都选自““带符号带符号””的一个子集，即所谓的的一个子集，即所谓的““输输入符号集合入符号集合””。

余下的有穷个单元都存放空白符，它是一个特殊余下的有穷个单元都存放空白符，它是一个特殊的带符号，但的带符号，但不是不是输入符号输入符号图灵机的基本模型3基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分在在一一个个图图灵灵机机的的动动作作中中，，图图灵灵机机根根据据带带头头（（读读写写头）所扫描的符号和有限控制器的状态可能作头）所扫描的符号和有限控制器的状态可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.n将带头向左或者右移一个单元 * 图图灵灵机机和和双双向向有有限限自自动动机机的的区区别别：：图图灵灵机机能能改改变变它带上的符号它带上的符号 图灵机的工作机制4基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分图灵机的形式化描述图灵机的形式化描述 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0   Q T     B     – T F   Q转移函数转移函数  : Q      Q       { L,R } ² 形式定义形式定义 一个图灵机一个图灵机 TM (Turing machine) 是一个七元组是一个七元组 M = (Q, T,  ,  , q0 , B , F ). 5基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分nδδ函数示例：函数示例： Q×∑ → Q×∑×{L ,R} Q×∑ → Q×∑×{L ,R} δ(q,a δ(q,ai i)=(p,B,L) q, p ∈Q)=(p,B,L) q, p ∈Q δ(q,a δ(q,ai i)=(p,b,R) a)=(p,b,R) ai i∈∑ b∈∑∈∑ b∈∑ n格局格局用w1q w2描述图灵机的瞬间工作状态q为M的当前状态， w1w2∈ ∑*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。

约定：约定：w w1 1q wq w2 2表示读写头正扫描表示读写头正扫描w w2 2的最左字符的最左字符w w2 2＝＝  则表示表示读写写头正正扫描一个空白字符描一个空白字符图灵机的函数与格局6基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分图灵机的格局图灵机的格局² 给定图灵机给定图灵机 M = (Q, T,  ,  , q0 , B , F ) ，，定义格局之间定义格局之间的推导关系的推导关系├M 如下：如下：1. 设设  (q, Xi ) = (p, Y , L )，，则有则有 X1X2…Xi-1qXiXi+1…Xn ├M X1X2…Xi-2pXi-1Y…Xn ，， 但有如下两个例外但有如下两个例外 ：： （（1））i=1时，时， qX1X2…Xn ├M qYX2…Xn ，，和和 （（2））i=n及及 Y=B 时，时， X1X2…Xn-1qXn ├M X1X2…Xn-2pXn-1 B.2. 设设  (q, Xi ) = (p, Y , R )，，则有则有 X1X2…Xi-1 q XiXi+1…Xn ├M X1X2…Xi-1Y p Xi+1…Xn ，， 但有如下两个例外但有如下两个例外 ：： （（1））i=n时，时， X1X2…Xn-1q Xn ├M X1X2…Xn-1Y p B ，，和和 （（2））i=1及及 Y=B 时，时， q X1X2…Xn├M B p X2…Xn-1Xn.7基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分图灵机接受的语言图灵机接受的语言L(M) = {ω│ω∈Tω│ω∈T* *且且q q0 0ω├ω├* * αα1 1 p αp α2 2 ,p∈F, α ,p∈F, α1 1αα2 2∈∑∈∑* *} } 图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。

假定：假定： 当输入被接受时，图灵机将停止，没有下一个动作8基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 任给图灵机任给图灵机 M = (Q, T,  ,  , q0 , B , F ) ，，以及输入字符串以及输入字符串w T*. 试问：对于试问：对于w，，M 是否停机是否停机？？ 停机是指图灵机不存在停机是指图灵机不存在下一个移动步（下一个移动步（move））.² 结论结论 图灵机的停机问题是不可解的（即不可判定的）图灵机的停机问题是不可解的（即不可判定的）.² 结论结论 任给图灵机任给图灵机 M ，，很容易构造一个图灵机很容易构造一个图灵机 M ，，使得使得L(M)= L(M  )，，并满足：如果并满足：如果w L(M) ，，则对于则对于 w，，M  接接受受w并一定停机并一定停机. 如果没有特别指出，总是假定图灵机到达终态（接受态）如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机后一定停机. 但是但是 ，，对不能接受的字符串，图灵机可能永不停止对不能接受的字符串，图灵机可能永不停止.（只（只要要M还在某个输入上运行，我们无法知道是因为运行的时间不还在某个输入上运行，我们无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）够长而没有被接受，还是根本就不会停机） 图灵机的停机问题图灵机的停机问题 9基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分图灵机举例图灵机举例例例1 1：设语言：设语言 L={aL={an n b bn n│n>=1}│n>=1}，，设计图灵机接受设计图灵机接受L L 。

思路：最初带上为思路：最初带上为 a aa a … … a b b… b B B B ……a b b… b B B B …… n n个个a na n个个b b首先用首先用x x替换替换M M最左边的最左边的a a，，再右移至最左边的再右移至最左边的b b用用y y替换之，左移替换之，左移寻找最右的寻找最右的x x，，然后右移一单元到最左的然后右移一单元到最左的a a，，重复循环重复循环如果如果（（1 1）当在搜寻）当在搜寻b b时，时，M M找到了空白符找到了空白符B B，，则则M M停止，不接受该串停止，不接受该串 （此时，（此时，a a的个数大于的个数大于b b的个数）的个数）（（2 2）） 当将当将b b改为改为y y后，左边再也找不到后，左边再也找不到a a，，此时此时, ,若右边再无若右边再无b b，，接受；若仍有接受；若仍有b b，，则则b b的个数大于的个数大于a a的个数，不接受的个数，不接受 10基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例例1 L={an bn│n>=1}δ(q0 ,a)=(q1 ,x,R)δ(q0 ,y)=(q3 ,y,R)δ(q1 ,a)=(q1 ,a,R)δ(q1 ,y)=(q1 ,y,R)δ(q1 ,b)=(q2 ,y,L)δ(q2 ,a)=(q2 ,a,L)δ(q2 ,y)=(q2 ,y,L)δ(q2 ,x)=(q0 ,x,R)δ(q3 ,y)=(q3 ,y,R)δ(q3 ,B)=(q4 ,B,R) 例：例：aabbaabb的接收格局序列的接收格局序列q q0 0aabb├ xqaabb├ xq1 1abb├ xaqabb├ xaq1 1bb├ xqbb├ xq2 2ayb├ qayb├ q2 2xayb├xqxayb├xq0 0ayb├xxqayb├xxq1 1ybyb├ xxyq├ xxyq1 1b├xxqb├xxq2 2yy├xqyy├xq2 2xyy├xxqxyy├xxq0 0yy├xxyqyy├xxyq3 3y├xxyyqy├xxyyq3 3B├xxyyqB├xxyyq4 4 11基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分对于输入字符串对于输入字符串001122，，该图灵机可以有如下推导该图灵机可以有如下推导步：步：q0001122├MXq101122 ├MX0q11122├MX0Yq2122├MX0Y1q222├MX0Yq31Z2 ├*Mq3X0Y1Z2├MXq00Y1Z2├*MXXYYZq22├MXXYYq3ZZ├*MXq3XYYZZ├MXXq0YYZZ├*MXXYYq4ZZ├MXXYYZq5Z├MXXYYZZq5B├MXXYYZZBq6B例例2 L =   0n1n2n   n   1 .12基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 转移图与转移表转移图与转移表13基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 作为整数函数计算机的图灵机作为整数函数计算机的图灵机n预预备备知知识识：：图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。

n传统方法把整数表示成一进制传统方法把整数表示成一进制整数 i  0 用字符串 0i 表示n如果一个函数有k个自变量，i1,i2 ,…ik，那么这些整数开始时被放在带上，并用1把他们分隔开形如 0i1 1 0i2 1 0i3… 1 0ikn如果图灵机停止(不论是否在一个接受状态上)且带上为 0m，则 f(i1,i2,…,ik)= m f是被图灵机计算的k元函数n如果f（i1,i2…,ik）对所有i1,i2…,ik有定义, 那么称f是一个全递归函数全递归函数对应于递归语言，因为它总是被能停下来的图灵机所计算n所有常用的整数算术函数都是全递归函数14基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例例3 3：设计图灵机求真减法：设计图灵机求真减法n思路：思路： 1. 用空白符B代替带上的最左端的02．右移至紧跟1后的0,将其改为13．左移找到B，将B之后的0改为B4．重复上述过程如果如果（1）右移找0时，遇到B，意味着m>nBB…B 0 m-(n+1) 1 11…1 n+1 n个将后面n+1个1变为B，将左侧最后一个B变0，形如BB…B 0 0 m-(n+1) BB…B n个 n+1个 这时，带上留下m-n个0，即结果为m-nn 初始带 0m 10n15基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分求真减法（续）求真减法（续）(2) M左移找不到0，意味着 n  m，形如 BB…B 1 11…1 0…0 m个 m个 n-m个 此时, 用B替换所有剩余的1 和016基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例例4 4：：L=L=  0 0 m m   m=2 m=2n n, n , n   0 0 n设计思路：对输入串设计思路：对输入串w w 1. 从左到右扫描带，隔一个消一个0；2．若带上只剩唯一一个0,接受；3．若带上不止一个0,且个数为奇数，拒绝；4．让读写头返回带的最左端；5. 转第一步。

17基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分Startq4q2q10 / #,RqrejectX /X,RB/B,Rq3B/B,Raccept5# / #,RB/B,LX /X,L0 /0,L0 / X,RX /X,RX /X,R0 / X,R0 /0,R识别识别 L=L=  0 0 m m   m=2 m=2n n, n , n   0 0 的的图灵机图灵机18基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分课堂练习课堂练习n设设计计一一个个状状态态数数不不超超过过3 3的的图图灵灵机机，，它它能能够够接接受受语语言言L=a(a+b)L=a(a+b)* * ，，若若假假定定T={a,b},T={a,b},两两个个状状态态的的图图灵灵机机能能否接受该语言？否接受该语言？19基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分5.2 图灵机的构造技术 在设计图灵机的过程中，写出δ函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具目的：设计时方便，但这些构造技术并未增加图灵机的功能。

20基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分5.2.1. 利用带存储区的状态利用带存储区的状态（（storage in the state））此类此类图灵机图灵机 M = (Q,  ,  ,  , q0 , B , F ) 中，状态中可以包含中，状态中可以包含一个具有有限个取值的存储单元，即状态集合为一个具有有限个取值的存储单元，即状态集合为 Q = S T = { [q,a] | q S   a T }，，其中其中 q S 通常表示控制状态，而通常表示控制状态，而 a T 通常表示数据元素通常表示数据元素.一般情况下，有限控制器内允许存储一般情况下，有限控制器内允许存储n个字符，即状态的第个字符，即状态的第2个元素可存储个元素可存储n个字符21基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视整个带，若找不到与第一个相同的字符，则整个带，若找不到与第一个相同的字符，则M接受该字符串，否则不接受。

接受该字符串，否则不接受构造构造M=(Q,{a,b},{a,b,B},δ,q0,B,F)其中其中Q={q0,q1}×{a,b,B}={[q0,a],[q0,b],[q0,B][q1,a][q1,b][q1,B]}初态初态[q0,B]终态终态F={[q1,B]} δ函数：函数：δ([q0,B],a)=([ q1,a],a,R)δ([q0,B],b)=([ q1,b],b,R) 存第一个字符存第一个字符δ([q1,a],b)=([ q1,a],b,R)δ([q1,b],a)=([ q1,b],a,R) 后面符号与第一个不等，继续右移后面符号与第一个不等，继续右移δ([q1,a],B)=([ q1,B],B,L)δ([q1,b],B)=([ q1,B],B,L) 进入终态进入终态[q1,B]δ([q1,a],a)=Фδ([q1,b],b)=Ф 遇到相同符号，遇到相同符号，δ无定义无定义 M停机，不接受停机，不接受22基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分5.2.2 多道多道（（multiple tracks）图灵机）图灵机把图灵机的输入带分成两层或多层，这样，原来的每一单把图灵机的输入带分成两层或多层，这样，原来的每一单元变成了上下两个或多个单元。

元变成了上下两个或多个单元对含有对含有n层的输入带来说，读写头一次可同时读出并改写层的输入带来说，读写头一次可同时读出并改写n个单元的字符，这样的图灵机称为个单元的字符，这样的图灵机称为n道机 23基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例：例： 多道多道图灵机图灵机例：用三道机，检查某个数例：用三道机，检查某个数n（（n>2）是否为素数书）是否为素数书p196））思路：将被检查的数思路：将被检查的数n以二进制形式写在输入带的第一道上，数的两端分以二进制形式写在输入带的第一道上，数的两端分别用￥和别用￥和Ф定界定界允许的输入符号为允许的输入符号为[￥￥,B,B],[0,B,B],[1,B,B],[Ф,B,B][…]分别代表分别代表1，，2，，3带上的内容带上的内容检查方法：检查方法：在第二道上写下一个二进制数在第二道上写下一个二进制数2把第一道上的数复制到第三道上把第一道上的数复制到第三道上将第三道上的数减去第二道上的数，余数留在第三道上将第三道上的数减去第二道上的数，余数留在第三道上若余数为若余数为0，被检查的数不是素数，被检查的数不是素数若余数不为若余数不为0，将第二道数加，将第二道数加1，将第一道数复制到第三道，重复上述，将第一道数复制到第三道，重复上述1，，2，，3，，4过程过程当一，二道数相等时，该数时素数。

当一，二道数相等时，该数时素数 24基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 5.2.3 核对符核对符 当用图灵机识别语言时，如果语言中存在有重复性或可当用图灵机识别语言时，如果语言中存在有重复性或可逆性等类型的句子时，为了判定某个字符串是否属于语句中逆性等类型的句子时，为了判定某个字符串是否属于语句中的句子，可以使用一个核对符，以此增加图灵机的灵活性的句子，可以使用一个核对符，以此增加图灵机的灵活性 考虑用一个双道机，在第二道上使用核对符考虑用一个双道机，在第二道上使用核对符““ ””，在，在第一道上放要被检查的字符串第一道上放要被检查的字符串, ,当字符串中某个字符一旦被核当字符串中某个字符一旦被核对以后对以后, ,可以在第二道上对应位置写上核对符可以在第二道上对应位置写上核对符““ ””25基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例：例： 核对符核对符例：设计一个图灵机例：设计一个图灵机M M，能够识别语言，能够识别语言{wtw│w∈{a,b}*}{wtw│w∈{a,b}*}思路：以思路：以t t为分界符，一个一个比较。

为分界符，一个一个比较解：构造解：构造M=(Q,T, ∑, δ,qM=(Q,T, ∑, δ,q0 0，，B,F)B,F)其中其中Q={[qQ={[qi i,c] │i=1,2,…,9,c=a,b,c] │i=1,2,…,9,c=a,b或或B}B}状态第二元素可存储一个字符状态第二元素可存储一个字符T={[cT={[c，，B]} │c=a,bB]} │c=a,b或或t} t} 两道与一道不同的表示法两道与一道不同的表示法∑∑＝＝{[c{[c，，Y]} │c=a,b,tY]} │c=a,b,t或或B,Y=BB,Y=B或或  } }q q0 0=[q=[q1 1,B], F={[q,B], F={[q9 9,B]},B]}空白符空白符B B在二道机下表示为在二道机下表示为[B[B，，B]B]26基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例：例： 核对符核对符27基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分核对符例核对符例 ：： abtab的分析过程的分析过程[q1,B]abtab├a[q2,a]btab├ab[q2,a]tab├abt[q3,a]ab   ├ ab[q4,B]tab├a[q5,B]btab├[q6,B]abtab      ├a[q1,B]btab├ab[q2,b]tab├abt[q3,b]ab      ├abta[q3,b]b├abt[q4,B]ab├a[q5,B]btab       ├ab[q7,B]tab├abt[q8,B]ab├abta[q8,B]b…       28基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 5.2.4 移位移位 可以让图灵机具备移位的功能，即对输入带上的可以让图灵机具备移位的功能，即对输入带上的字符进行移位操作。

当需要在输入带上留出一部分空字符进行移位操作当需要在输入带上留出一部分空间时，可将输入带上的非空白符右移若干单元间时，可将输入带上的非空白符右移若干单元 假设需要输入带上的非空白字符右移假设需要输入带上的非空白字符右移n n个单元，个单元，则可让控制器状态的第二个元素具有存储则可让控制器状态的第二个元素具有存储n n单元的功单元的功能（能（n n是有限数）是有限数）29基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分例：例：构造图灵机构造图灵机M，要求它将带上非空白符向移动两个单元，要求它将带上非空白符向移动两个单元原带为原带为 a b c d B，， 移后为移后为 z z a b c d B设设M=(Q, T, ∑, δ, q0, B, F)；； Q={[q, D1, D2] │q=q0,q1,且且D1,D2,…Dn∈∈∑}初始：初始：[q0, B, B], 终态终态[q1, B, B]δ定义：定义：δ([q0, B, B], D1)=([q0, B, D1], Z, R)δ([q0, B, D1], D2)=([q0, D1, D2], Z, R)δ([q0, D1, D2], D3)=([q0, D2, D3], D1, R)δ([q0, Dn-1, Dn], B)=([q0, Dn, B], Dn-1, R)δ([q0, Dn, B], B)=([q1, B, B], Dn, L)对对D∈∈∑－－{ B, Z}:δ([q1, B, B],D)=([q1, B, B], D, L) 回到输入点回到输入点30基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分 5.2.5 子程序子程序（（subroutines）的设计）的设计 左上图的左上图的图灵机表示子程序图灵机表示子程序 copy ，右上图的，右上图的图灵机表图灵机表示可以调用示可以调用copy 的主程序的主程序 ，完成两个正整数的乘法，完成两个正整数的乘法. 初初始始时，带上的符号串形如时，带上的符号串形如 0m10n1，而结束时，带上的符号，而结束时，带上的符号串串变为变为0mn.31基本图灵机及图灵机的构造技术基本图灵机及图灵机的构造技术0分分。