《基本图灵机及图灵机的构造技术0分》由会员分享，可在线阅读，更多相关《基本图灵机及图灵机的构造技术0分（31页珍藏版）》请在金锄头文库上搜索。
1、第五章 图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质n该模型的每个过程都是有穷可描述的；n过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。n通过研究TM来研究递归可枚举集和部分递归函数n为算法和可计算性研究提供了形式化描述工具。1School of Computer Science & Technology, BUPT主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点: TM的定义、TM的构造。 n难点: TM的构造。2School of C
2、omputer Science & Technology, BUPTFinite controlX1BB.X2XnXi带（tape）单元格（cell）带符（tape symbol）n 读写头在每一时刻扫描带上的一个单元n 带有一个最左单元，向右则是无限的。n 带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输 入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊 的带符号，但不是输入符号。图灵机的基本模型3School of Computer Science & Technology, BUPT在一个
3、图灵机的动作中，图灵机根据带头（读写 头）所扫描的符号和有限控制器的状态可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替 原来写在该单元上的符号.n将带头向左或者右移一个单元。* 图灵机和双向有限自动机的区别：图灵机能改变 它带上的符号。 图灵机的工作机制4School of Computer Science & Technology, BUPT图灵机的形式化描述有限状态集有限输入符号集有限带符号集转移函数开始状态特殊带符:空白符终态集合q0 QT B TF Q转移函数 : Q Q L,R 形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T
4、, , , q0 , B , F ). 5School of Computer Science & Technology, BUPTn函数示例： Q QL ,R(q,ai)=(p,B,L) q, p Q(q,ai)=(p,b,R) ai b n格局用w1q w2描述图灵机的瞬间工作状态q为M的当前状态， w1w2 *w1w2是当前时刻从开始端（因为可写）到右边空白符号为止 的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：w1q w2表示读写头正扫描w2的最左字符w2 则则表示读读写头头正扫扫描一个空白字符。图灵机的函数与格局6School of Computer Scienc
5、e & Technology, BUPT图灵机的格局 给定图灵机 M = (Q, T, , , q0 , B , F ) ，定义格局之间 的推导关系M 如下： 1. 设 (q, Xi ) = (p, Y , L )，则有X1X2Xi-1qXiXi+1Xn M X1X2Xi-2pXi-1YXn ，但有如下两个例外 ：（1）i=1时， qX1X2Xn M qYX2Xn ，和（2）i=n及 Y=B 时， X1X2Xn-1qXn M X1X2Xn-2pXn-1 B. 2. 设 (q, Xi ) = (p, Y , R )，则有X1X2Xi-1 q XiXi+1Xn M X1X2Xi-1Y p Xi+1
6、Xn ，但有如下两个例外 ：（1）i=n时， X1X2Xn-1q Xn M X1X2Xn-1Y p B ，和（2）i=1及 Y=B 时， q X1X2XnM B p X2Xn-1Xn.7School of Computer Science & Technology, BUPT图灵机接受的语言L(M) = T*且q0* 1 p 2 ,pF, 12*图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：当输入被接受时，图灵机将停止，没有下一个动作。8School of Computer
7、Science & Technology, BUPT任给图灵机 M = (Q, T, , , q0 , B , F ) ，以及输入字符串 wT*. 试问：对于w，M 是否停机？ 停机是指图灵机不存在 下一个移动步（move）. 结论 图灵机的停机问题是不可解的（即不可判定的）. 结论 任给图灵机 M ，很容易构造一个图灵机 M，使得 L(M)= L(M )，并满足：如果wL(M) ，则对于 w，M 接受w 并一定停机.如果没有特别指出，总是假定图灵机到达终态（接受态） 后一定停机.但是 ，对不能接受的字符串，图灵机可能永不停止.（只 要M还在某个输入上运行，我们无法知道是因为运行的时间不够长而
8、没有被接受，还是根本就不会停机）图灵机的停机问题 9School of Computer Science & Technology, BUPT图灵机举例例1：设语言 L=an bnn=1，设计图灵机接受L 。思路：最初带上为 a a a b b b B B B n个a n个b首先用x替换M最左边的a，再右移至最左边的b用y替换之，左移寻找最右的x，然后右移一单元到最左的a，重复循环。如果（1）当在搜寻b时，M找到了空白符B，则M停止，不接受该串。（此时，a的个数大于b的个数）（2） 当将b改为y后，左边再也找不到a，此时,若右边再无b，接受；若仍有b，则b的个数大于a的个数，不接受。 10Sc
9、hool of Computer Science & Technology, BUPT例1 L=an bnn=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) 例：aabb的接收格局序列q0aabb xq1abb xaq1bb xq2ayb q2xaybxq0aybxxq1yb xxyq1bxxq2yyx
10、q2xyyxxq0yyxxyq3yxxyyq3Bxxyyq4 11School of Computer Science & Technology, BUPT对于输入字符串001122， 该图灵机可以有如下推导 步：q0001122MXq101122MX0q11122MX0Yq2122MX0Y1q222MX0Yq31Z2*Mq3X0Y1Z2MXq00Y1Z2*MXXYYZq22 MXXYYq3ZZ*MXq3XYYZZMXXq0YYZZ*MXXYYq4ZZ MXXYYZq5ZMXXYYZZq5BMXXYYZZBq6B例2 L = 0n1n2n n 1.12School of Computer Sc
11、ience & Technology, BUPT转移图与转移表13School of Computer Science & Technology, BUPT作为整数函数计算机的图灵机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
12、（i1,i2,ik）对所有i1,i2,ik有定义, 那么称f是一个 全递归函数。全递归函数对应于递归语言，因为它总是被能停 下来的图灵机所计算。n所有常用的整数算术函数都是全递归函数。 14School of Computer Science & Technology, BUPT例3：设计图灵机求真减法n思路： 1. 用空白符B代替带上的最左端的0 2右移至紧跟1后的0,将其改为1 3左移找到B，将B之后的0改为B 4重复上述过程 如果（1）右移找0时，遇到B，意味着mn BBB 0 m-(n+1) 1 111n+1 n个将后面n+1个1变为B，将左侧最后一个B变0，形如 BBB 0 0 m-
13、(n+1) BBBn个 n+1个 这时，带上留下m-n个0，即结果为m-nn 初始带 0m 10n15School of Computer Science & Technology, BUPT求真减法（续）(2) M左移找不到0，意味着 n m，形如BBB 1 111 00m个 m个 n-m个 此时, 用B替换所有剩余的1 和016School of Computer Science & Technology, BUPT例4：L= 0 m m=2n, n 0n设计思路：对输入串w 1. 从左到右扫描带，隔一个消一个0； 2若带上只剩唯一一个0,接受； 3若带上不止一个0,且个数为奇数，拒绝；
14、4让读写头返回带的最左端； 5. 转第一步。17School of Computer Science & Technology, BUPTStartq4q2q10 / #,Rq rejectX /X,RB/B,Rq3B/B,Racceptqq5# / #,RB/B,LX /X,L0 /0,L0 / X,RX /X,RX /X,R0 / X,R0 /0,R识别 L= 0 m m=2n, n 0的图灵机18School of Computer Science & Technology, BUPT课堂练习n设计一个状态数不超过3的图灵机，它能够接受语言 L=a(a+b)* ，若假定T=a,b,两个状
15、态的图灵机能 否接受该语言？19School of Computer Science & Technology, BUPT5.2 图灵机的构造技术在设计图灵机的过程中，写出函数很麻烦，为 了构造复杂的图灵机，需探讨图灵机的若干构造技 术，并引入一些新的概念和工具。目的：设计时方便，但这些构造技术并未增加图灵 机的功能。 20School of Computer Science & Technology, BUPT5.2.1. 利用带存储区的状态（storage in the state）此类图灵机 M = (Q, , , , q0 , B , F ) 中，状态中可以包含 一个具有有限个取值的存储单元，即状态集合为Q = ST = q,a | qS aT ，其中 qS 通常表示控制状态，而 aT 通常表示数据元素.一般情况下，有限控制器内允许存储n个字符，即状态的第2 个元素可存储n个字符。21School of Computer Science & Technology, BUPT例：设计一个图灵机，读写头将扫
