欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载
     

    Part4图灵机及可计算理论.ppt

    • 资源ID:2202422       资源大小:1.06MB        全文页数:82页
    • 资源格式: PPT        下载积分:8
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要8
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    Part4图灵机及可计算理论.ppt

    Part 4 图灵机及可计算理论,主讲教师 贺利坚,2,Part 4 主要内容提示,3,一、图灵机及形式定义,1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言,4,图灵机,FA和PDA的局限 FA有有限的存储,只能处理RL PDA用栈提供无限的存储,但栈只能后进先出,PDA只能处理CFL FA和PDA不能用作通用的计算模型,5,图灵机是通用的计算模型,是计算机的数学模型 图灵在论述“有些数学问题是不可解的”时,提出了图灵机 图灵论题:凡是可计算的函数,都可以用图灵机计算 丘奇论题:任何计算,如果存在一个有效过程,它就能被图灵机实现 提出TM的目的在于: 对有效的计算过程(即算法)进行形式化的描述, 忽略模型的存储容量在内的一些枝节问题, 只考虑算法的基本特征. 图灵提出TM具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。,图灵机,6,图灵生平 1912年出生,演算能力突出 1931年,进剑桥大学学数学 1936年,提出图灵机模型 1938年,获普灵斯顿大学博士学位 1950年,发表论文“计算机和智能”,提出图灵测试 1951年,成为英皇家学会院士 1954年,不幸去世,现代计算机设计思想的创始人,人工智能领域的开拓者 计算机领域的最高奖以图灵命名,图灵机,7,Alan Turing(1912-1954),1912 (23 June): Birth, Paddington, London 1926-31: Sherborne School 1930: Death of friend Christopher Morcom 1931-34: Undergraduate at King's College, Cambridge University 1932-35: Quantum mechanics, probability, logic 1935: Elected fellow of King's College, Cambridge 1936: The Turing machine, computability, universal machine 1936-38: Princeton University. Ph.D. Logic, algebra, number theory 1938-39: Return to Cambridge. Introduced to German Enigma cipher machine 1939-40: The Bombe, machine for Enigma decryption 1939-42: Breaking of U-boat Enigma, saving battle of the Atlantic 1943-45: Chief Anglo-American crypto consultant. Electronic work. 1945: National Physical Laboratory, London 1946: Computer and software design leading the world. 1947-48: Programming, neural nets, and artificial intelligence 1948: Manchester University 1949: First serious mathematical use of a computer 1950: The Turing Test for machine intelligence 1951: Elected FRS. Non-linear theory of biological growth 1952: Arrested as a homosexual, loss of security clearance 1953-54: Unfinished work in biology and physics 1954 (7 June): Death (suicide) by cyanide poisoning, Wilmslow, Cheshire.,8,图灵机的物理模型 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 一个移动将完成以下三个动作: 改变有穷控制器的状态; 在当前所读符号所在的带方格中印刷一个符号; 将读头向右或者向左移一格。,图灵机,9,图灵机的形式定义,定义9-1 图灵机(Turing machine)/基本的图灵机 TM M=(Q, , , , q0, B, F) Q:状态的有穷集合,qQ为M的一个状态; :输入字母表,a为M的一个输入符号。除空白符号B外,只有中的符号才能在M启动时出现在输入带上; :带符号表(tape symbol),X为M的一个带符号,表示在M的运行过程中,X可以在某一时刻出现在输入带上; q0Q:M的开始状态,M从状态q0启动,读头正注视着输入带最左端的符号; B:空白符(blank symbol),含空白符的带方格是空的; FQ:M的终止状态集,qF为M的一个终止状态。 TM M 一旦进入终止状态,它就停止运行。,10,TM M=(Q, , , , q0, B, F) 称为移动函数 :Q× Q× ×R, L,为M的移动函数(transaction function)。 (q, X)=(p, Y, R)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向右移一格; (q, X)=(p, Y, L)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向左移一格。,图灵机的形式定义,11,例 TM M1=(q0, q1, q2,0, 1,0, 1, B, , q0 , B ,q2) 其中 的定义如下 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, B)= (q2, B, R),M1的移动函数的另一种表示:,图灵机的形式定义,q2,(q2, B, R),(q1, 0, R),q1,(q1, 1, R),(q0, 0, R),q0,B,1,0,状态,L(M1)=x | x0,1+,且x中有且仅有一个1,12,补充:图灵机的转移图 M1=(q0, q1, q2,0, 1,0, 1, B, ,q0 , B ,q2) (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, B)= (q2, B, R),当(q , X)=(p , Y, D)时, 在q到p的弧上标记X/Y D,D为或 L(M1)=x | x0,1+,且x中有且仅有一个1,图灵机的形式定义,13,图灵机接受的语言,定义9-2 即时描述(instantaneous description, ID) 12 *,qQ, 1q2称为M的即时描述 q为M的当前状态, M正注视着2的最左符号。 当M的读头注视的符号右边还有非空白符时, 12为M的输入带最左端到最右的非空白符号组成的符号串; 否则, 12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串,14,设X1X2Xi-1qXiXi+1Xn是M的一个ID, 如果(q,Xi)=(p,Y,R),则M的下一个ID为 X1X2Xi-1YpXi+1Xn 记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn,设X1X2Xi-1qXiXi+1Xn是M的一个ID, 如果(q, Xi)=(p, Y, L), 则当i1时,M的下一个ID为 X1X2pXi-1YXi+1Xn 记作X1X2Xi-1qXiXi+1Xn M X1X2pXi-1YXi+1Xn,图灵机接受的语言,15,Mn表示M的n次幂:Mn =(M)n M+表示M的正闭包: M+ =(M)+ M*表示M的克林闭包: M* =(M)* 在意义明确时,用、n 、+、*表示,图灵机接受的语言,16,例 M1在处理输入串的过程中经历的ID变换序列 M1=(q0, q1, q2,0, 1,0, 1, B, , q0 , B ,q2),图灵机接受的语言,M 000100Bq2,M 000100 q1,M 00000q0B,M 00010q11,M 00010q10,M 0000 q00,M 0001q101,M 0001q100,M 000q000,M 000q0101,M 000q0100,M 00q0000,M 00q00101,M 1Bq2,M 00q00100,M 0q00000,M 0q000101,M 1q1,M 0q000100,q000000,q0000101,q01,q0000100,(4)00000,(3)000101,(2)1,(1)000100,(q0, 0)=(q0, 0, R) (q0, 1)=(q1, 1, R) (q1, 0)=(q1, 0, R) (q1, B)=(q2, B, R),17,定义9-3 TM接受的语言 TM M=(Q, , , , q0, B, F) L(M)=x | x*且q0xM* 1q 2 & qF & 1, 2 *,只要在工作过程中能进入终止状态(之一),则可以判断被接受并停机。,图灵机不停地计算: 当输入被接受时, 图灵机将停止, 没有下一个动作; 当因未定义转换函数, 图灵机无法计算下去时, 将拒绝执行; 如果不进入任何接受或拒绝状态, 继续执行下去, 永不停止。 在TM接受的语言中,包含那些不能使TM停机的输入。,图灵机接受的语言,18,定义9-4 TM接受的语言叫做递归可枚举语言(recursively enumerable language,r.e.)。 如果存在TM M=(Q, , , , q0, B, F) ,L=L(M),并且对每一个输入串x,M都停机,则称L为递归语言(recursively language)。 x是任意的串 xL,M进入接受状态并停机 x L,M也可以停机,但不进入接 受状态 M不能停机,则可能是r.e.,或其他 语言可以按TM接受及停机分类,图灵机接受的语言,TM能够定义,TM能够计算,19,例 M2=(q0, q1, q2, q3,0, 1,0, 1, B, ,q0 , B ,q3), (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R) M2接受的语言是什么?,图灵机接受的语言,M2接受的语言是字母表0,1上那些至少含有3个1的0、1符号串。,借助其他描述方法的观察:,20,M2=(q0, q1, q2, q3,0, 1,0,1,B,q0 , B ,q3)处理输入串的过程:,图灵机接受的语言,思考:如何构造出接受字母表0, 1上那些含且恰含有3个1的符号串的TM。 关键:不读完不能进入终态,(3)1001100101100: q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q2100101100 10011q300101100,(1)00010101: q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101q201 0001010q21 00010101q3,(2)000101000: q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010q200 00010100q20 000101000q2B,21,一、图灵机及形式定义,1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言,Any Question?,22,Part 4 主要内容提示,23,二、图灵机的构造,1、一般构造方法 2、TM作为非负整函数的计算模型 3、 状态的有穷存储功能的利用 4、多道(multi-track)技术 5、子程序(subroutine)技术,24,一般构造方法,思路 图灵机可以对输入带进行写操作 写入一些标记即完成记忆(类似PDA的栈,但更丰富) 图灵机还可以用状态标记工作状态,25,例 构造TM M3,使L(M)=0n1n2n | n1。 不能通过“数” 0、1、或者2的个数来实现检查。 用匹配的方法比较它们的个数是否相同: 出现一个0、必然所有0后有1,所有1后有2。 遇0后在带方格上印刷一个X,找到1后在带方格上印刷一个Y,再找到2后在带方格上印刷一个Z。 带上为XXXYYYZZZB时接受 例:对000111222,一般构造方法,000111222B X00111222B X00Y11222B X00Y11Z22B, XX0Y11Z22B XX0YY1Z22B XX0YY1ZZ2B, XXXYY1ZZ2B XXXYYYZZ2B XXXYYYZZZB,26,正常情况下,输入带上的符号串的一般形式为 000011112222 TM经过一段运行, 输入带上的符号串的一般情况为 XX00YY11ZZ22BB 如果能被接受 XXXXYYYYZZB 边界情况可能有 XXXXYYYYZZ22BB XXXXYY11ZZ22BB XX00YYYYZZ22BB XX00YY11ZZZZBB XX00YYYYZZZZBB,一般构造方法,27,(q0, 0)= (q1, X, R),(q1, 0)= (q1, 0, R),(q1, Y)= (q1, Y, R),(q1, 1)= (q2, Y, R),(q2, 1)= (q2, 1, R),(q2, Z)= (q2, Z, R),(q2, 2)= (q3, Z, L),(q3, 0)= (q3, 0, L) (q3, Y)= (q3, Y, L) (q3, 1)= (q3, 1, L) (q3, Z)= (q3, Z, L) (q3, X)= (q0, X, R),构造思路,28,构造思路,(q0, Y)= (q4, Y, R) 0已经读完,(q4,Y)= (q4,Y,R),(q4,Z)= (q4,Z,R),(q4, B)= (q5, B, R),?q2时遇到B ?q2时遇到,终态,?q4时遇到1 ?q4时遇到2,?q1时遇到Z ?q1时遇到2 ?q1时遇到,29,L(M3)=0n1n2n | n1 M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B, q5) 如右定义,(q0, 0)= (q1, X, R) (q1, 0)= (q1, 0, R) (q1, Y)= (q1, Y, R) (q1, 1)= (q2, Y, R) (q2, 1)= (q2, 1, R) (q2, Z)= (q2, Z, R) (q2, 2)= (q3, Z, L) (q3, Z)= (q3, Z, L) (q3, 1)= (q3, 1, L) (q3, Y)= (q3, Y, L) (q3, 0)= (q3, 0, L) (q3, X)= (q0, X, R) (q0, Y)= (q4, Y, R) (q4,Y)= (q4,Y,R) (q4,Z)= (q4,Z,R) (q4, B)= (q5, B, R),一般构造方法,30,一般构造方法,L(M3)=0n1n2n | n1 M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B, q5),31,TM作为非负整函数的计算模型,TM除作为语言的识别器外,还可以求函数的值 用TM求解k元函数f(n1, n2, nk) 编码问题(带方格上的符号) 用符号串0n表示非负整数n 1进制 函数的输入(TM中带的初始值):k元函数f(n1, n2, nk)的输入是: 0n11 0n2110nk 函数的值(TM的输出):如果f(n1, n2, nk)=m,则该TM的输出为0m 。,32,定义9-5 图灵可计算的(Turing computable) 设有k元函数f(n1, n2, nk)=m, TM M=(Q, , , , q0 , B , F) M接受输入串0n11 0n2110nk,输出符号串0m; f(n1, n2, nk)无定义时,TM M没有恰当的输出给出。 称TM M计算k元函数f(n1, n2, nk); 也称f(n1, n2, nk)为TM M计算的函数; 也称f是图灵可计算的。,TM作为非负整函数的计算模型,33,定义9-6 完全递归函数(total recursive function) 设有k元函数f(n1, n2, nk),如果对于任意的n1, n2, nk , f 均有定义,也就是计算f的TM总能给出确定的输出,则称 f 为完全递归函数。 部分递归函数(partial recursive function) 一般地,TM计算的函数称为部分递归函数。 说明 常用算术函数(+-*/)是完全递归函数,均有确定的值。 从停机角度: 部分递归函数对应递归可枚举语言 完全递归函数对应递归语言,TM作为非负整函数的计算模型,34,例 构造TM M4,计算m+n,n和m是非负整数 分析:输入为0n10mB,输出0n+mB 方法:中间1变0,B前0变B,(q0, 0)= (q2, 0, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q2, 0, R) (q2, B)= (q3, B, L) (q3, 0)= (q1, B, R),TM作为非负整函数的计算模型,当n为0时,q0状态下直接遇到1,将1变成B就可以立即结束: (q0, 1)= (q1, B, R) 当m为0时,将最后的由1转变的0改为B,有:M4= (q0,q1,q2,q3, 0, 1, 0,1, B, , q0, B,q1),35,状态的有穷存储功能的利用,TM用有穷的状态控制器实现状态的有穷存储. 例 构造TM M6,使得 L(M6)=x | x0,1*且 x中至多含3个1。 分析:M6只用记录已经读到的1的个数。 q0表示当前已经读到0个1; q1表示当前已经读到1个1; q2表示当前已经读到2个1; q3表示当前已经读到3个1。 到达q3后继续读入字符,考察是否有更多的1,而遇B之前再无1,则可以进入终态qf 如q0, q1, q2后遇到了B,也进入qf,36,L(M6)=x | x0,1*且 x中至多含3个1。 M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf),状态的有穷存储功能的利用,(q0, 0 )=(q0, 0, R) (q0, 1 )=(q1, 1, R) (q0, B )=(qf, B, R) (q1, 0 )=(q1, 0, R) (q1, 1 )=(q2, 1, R) (q1, B )=(qf, B, R),(q2, 0 )=(q2, 0, R) (q2, 1 )=(q3, 1, R) (q2, B )=(qf, B, R) (q3, 0 )=(q3, 0, R) (q3, B )=(qf, B, R),37,对M6进行修改,可得到M7 和M8 L(M7) =x | x0,1*且 x中含且仅含3个1 L(M8)=x | x0,1*且 x中至少含3个1,状态的有穷存储功能的利用,L(M6)=x | x0,1*且 x中至多含3个1。 M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf),(q0, 0 )=(q0, 0, R) (q0, 1 )=(q1, 1, R) (q0, B )=(qf, B, R) (q1, 0 )=(q1, 0, R) (q1, 1 )=(q2, 1, R) (q1, B )=(qf, B, R),(q2, 0 )=(q2, 0, R) (q2, 1 )=(q3, 1, R) (q2, B )=(qf, B, R) (q3, 0 )=(q3, 0, R) (q3, B )=(qf, B, R),38,例 构造TM M9它的输入字母表为0, 1,现在要求M9在它的输入符号串的尾部添加子串101。 将待添加子串101存入有穷控制器。 首先找到符号串的尾部。 将给定符号串中的符号依次地印刷在输入带上 每印刷一个符号,就将它从有穷控制器的“存储器”中删去,当该“存储器”空时,TM就完成了工作。 M9=(q101,q01,q1,q,0,1,0,1,B,q101, B,q) 其中 的定义为: (q101, 0 )=(q101, 0, R) (q101, 1 )=(q101, 1, R) (q101, B )=(q01, 1, R) (q01, B )=(q1, 0, R) (q1, B )=(q, 1, R),状态的有穷存储功能的利用,39,例 P319 5(8)请设计识别语言xxT | x0,1*的TM。,(q,a)=(pa,X,R), a=0,1 (pa,b)=(pa,b,R), b=0,1 (pa,B)=(sa,B,L) (pa,Y)=(sa,Y,L) (sa,a)=(t,Y,L) (t,c)=(t,c,L),c=0,1 (t,X)=(q,X,R) (q,Y)=(f,Y,R) (q,B)=(f,B,R),TM M=(q,p0,p1,s0,s1, t, f,0,1,0,1,B,X,Y, q,B,f),状态的有穷存储功能的利用,40,多道(multi-track)技术,TM有一条含无穷多个带方格的输入带,可以将输入带视为由“多道”构成,形成多道TM,这时X,Y,Z视为整体,即每一个符号形如X,Y,Z,41,例 M11=(Q, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f),多道(multi-track)技术,42,例 构造M11,使L(M11)=xcy | x,y0,1+且 xy 分析: 以符号c为分界线,逐个地将c前的符号与c后的符号进行比较。 当发现对应符号不同时,就进入终止状态。 当发现x与y的长度不同时,就进入终止状态。 当发现x与y相同时,停机。 双道:一个道存放被检查的符号串,另一个存放标记符。,终,多道(multi-track)技术,43,多道(multi-track)技术,44,M11=(q, q0, q1, p0, p1 , q, p, s, f, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f) q状态:找到x中第一个符号做标记 (q, B,a )=(qa, ,a, R) a=0,1 qa状态:去寻找c (qa, B,d)=(qa, B,d, R) d=0,1 qa状态:找到了c,准备找y中 下一个匹配的符号 (qa, B,c)=(pa, B,c, R) (pa, ,b)=(pa, ,b, R) b=0,1,多道(multi-track)技术,45,找到y中第一个尚未匹配的符号,并与pa中记忆的符号相同,标记并准备下一次匹配 (pa, B,a)=(p, ,a, L) p,q状态:返回去找下一符号 (p, ,b)=(p, ,b, L) b=0,1 (p, B,c)=(q, B,c, L) (q, B,a)=(q, B,a, L) a=0,1 发现要找的下一符号,回 到q (q, ,a)=(q, ,a, R) a=0,1,多道(multi-track)技术,46,在pa时,若状态中记忆的符号不等于要匹配的符号,表明xy,进入终止状态:(pa, B,b)=(f, B,b,R) 在pa时,读到B,B,说明|x|y|,从而xy,进入终止状态: (pa, B,B)=(p, B,B, R) 在q,读到B,c,说明x已读完, 这时y未读完则 xy,所以继续 判断,进入s状态 (q, B,c)=(s, B,c,R) s状态:进一步考察y是否读完, 读,b继续往后,读B,a说明xy: (s, ,b)=(s, ,b, R),b=0,1 (s, B,a)=(f, B,a, R) ,a=0,1 y也读完则x=y,往后读会遇到B,B,多道(multi-track)技术,47,子程序(subroutine)技术,将TM的设计看成是一种特殊的程序设计,将子程序的概念引进来。 一个完成某一个给定功能的TM M 从一个状态q开始,到达某一个固定的状态 f 结束。 将这两个状态作为另一个TM M的两个一般的状态。 当M进入状态q时,相当于启动M (调用M 对应的子程序);当M 进入状态 f 时,相当于返回到M的状态 f。,48,例9 构造M12完成正整数的乘法运算。 m×n,即n个m相加,输入0n10m ,输出0n*m 。 算法思想:每次将n个0中的1个0改成B,就在输入串的后面复写m个0。 在M12的运行过程中,输入带的内容为: Bh0n-h10m10m*hB,子程序(subroutine)技术,解:M12的功能可以分为三个部分 (1)初始化 q0表示启动状态,将第一个0变成B,并在最后一个0后写上1后,到达q1状态( q1状态表示完成初始化后的状态)。 q00n10m + Bq10n-110m1,B30n-310m103mB,BB0n-210m102mB,B0n-110m10mB,0n10mB, BnBBmB0nmB(即0nm),Bn10m10nmB, Bn-1010m10(n-1)mB,49,(2)主控部分 从状态q1开始,扫描过前n个0中剩余的0和第一个1,将读头指向m个0的第一个,此时的状态为q2: Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)B q2为子程序的开始状态,当用子程序完成m个0的复写, 复制完成后回到q3状态, q3为子程序的返回(终止)状态。 Bh0n-h1 q20m10m*(h-1)B + Bh0n-h1 q30m10m*hB 在q3状态下,将读头移回到前n个0中剩余的0中的第一个0,并将这个0改成B,进入q1状态,准备进行下一次循环 Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB 当完成n次m个0的复写之后,清除输入带上除了这m*n个0以外的其他非空白符号。q4为终止状态 Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB,子程序(subroutine)技术,50,(3)子程序。 从q2启动,完成将m个0复写到后面的任务后,回到q3结束,返回到主控程序。 1 q20m10kB + 1 q30m10k+mB 在子程序中,读一个0需要做一个标记,可能需要用多带技术进行构造。,子程序(subroutine)技术,51,作业与指导 P318,3、给出M处理4+3的过程中ID的变化 5、设计识别下列语言的图灵机 (1) 1n0m |n m1 (7) w2wT|w0,1*,52,二、图灵机的构造,1、一般构造方法 2、TM作为非负整函数的计算模型 3、 状态的有穷存储功能的利用 4、多道(multi-track)技术 5、子程序(subroutine)技术,Any Question?,53,Part 4 主要内容提示,54,三、图灵机的变形,从不同的方面对TM进行扩充。 双向无穷带TM。 多带TM。 不确定的TM。 多维TM 其他TM 它们与基本的TM等价。 最新发展:树状图灵机、细胞自动机、,55,1. 双向无穷带TM,定义9-7 双向无穷带 (Turing machine with two-way infinite tape,TM) TM M=(Q, , , , q0 , B , F) Q, , , ,q0 , B , F的意义同定义9-1。 的即时描述ID同定义9-2。 允许M的读头处在输入串的最左端时,仍然可以向左移动。,56,用单向无穷带模拟双向无穷带,定理9-1 对于任意一个双向无穷带TM M,存在一个等价的基本TM M。,57,2. 多带TM,定义 多带TM(multi-tape turing machine) 允许TM有多个双向无穷带,每个带上有一个相互独立的读头。 k带TM在一次移动中完成如下三个动作 改变当前状态; 各个读头在自己所注视的带方格上印刷一个希望的符号。 各个读头向各自希望的方向移动一个带方格。,区别于多道技术!,定理 9-2 多带TM与基本的TM等价。,58,3. 不确定的TM,不确定TM与基本TM的区别是对于任意的(q, X)Q×,(q,X)=(q1,Y1,D1),(q2,Y2,D2),(qk,Yk,Dk), Dj为读头的移动方向, 即DjR,L。 表示M在状态q,读到X时,可以有选择地进入状态qj,印刷字符Yj,按Dj移动读头 L(M)=w | w*且ID1*IDn,且IDn含M的终止状态。,定理 9-3 不确定的TM与基本的TM等价,59,4. 多维TM,多维TM(multi-dimensional Turing machine) 读头可以沿着多个维移动。 k维TM(k-dimensional Turing machine) TM可以沿着k维移动。 k维TM的带由k维阵列组成,而且在所有的2k个方向上都是无穷的,它的读头可以向着2k个方向中的任一个移动。 定理 9-4 多维TM与基本TM等价。,Ba1a2a3a4BBBBBB# Ba5Ba6a7a8a9a10BBB# Ba11BBBBa12Ba13Ba14# a15a16BBBBBBBBa16# BBB a17BBBBBa18B# a19a20BBBBBBBBB# BBBBBBBBBBa21$,60,5. 其他TM,(1) 多头TM (2) 离线TM (3) 作为枚举器的TM (4) 多栈机 (5) 计数机 (6) Church-Turing论题与随机存取机,61,(1) 多头TM,多头TM(multi-head Turing machine) 指在一条带上有多个读头,它们受M的有穷控制器的统一控制,M根据当前的状态和这多个头当前读到的字符确定要执行的移动。在M的每个动作中,各个读头所印刷的字符和所移动的方向都可以是相互独立的。 定理 9-5 多头TM与基本的TM等价。 可以用一条具有k+1个道的基本TM来模拟一个具有k个头的TM(k头TM)。其中一个道用来存放原输入带上的内容,其余k个道分别用来作为k个读头位置的标示。,62,(2) 离线TM,离线TM(off-line Turing machine) 有一条输入带是只读带(read-only tape)的多带TM。 符号和$用来限定它的输入串存放区域,在左边,$在右边。 不允许该带上的读头移出由和$限定的区域离线的TM。 如果只允许只读带上的读头从左向右移动,则称之为在线TM(on-line Turing machine)。 定理 9-6 离线TM与基本的TM等价。 证明要点:让模拟M的离线TM比M多一条带,并且用这多出来的带复制M的输入串。然后将这条带看作是M的输入带,模拟M进行相应的处理。,63,(3) 作为枚举器的TM,作为枚举器的TM(Turing machine as enumerator) 多带TM,其中有一条带专门作为输出带,用来记录产生语言的每一个句子。 在枚举器中,一旦一个字符被写在了输出带上,它就不能被更改。如果该带上的读头的正常移动方向是向右移动的话,这个带上的读头是不允许向左移动的。 如果这个语言有无穷多个句子,则它将永不停机。它每产生一个句子,就在其后打印一个分割符“#”。 枚举器产生的语言记为G(M)。 规范的顺序(canonical order) 定理 9-7 L为递归可枚举语言的充分必要条件是存在一个TM M,使得L=G(M)。 定理 9-8 一个语言L为递归语言的充分必要条件是存在一个TM M,使得L=G(M),并且L是被M按照规范顺序产生的。,64,(4) 多栈机,多栈机(multi-stack machines)是一个拥有一条只读输入带和多条存储带的不确定TM。 多栈机的只读带上的读头不能左移。 存储带上的读头可以向左和向右移动。 右移时,一般都在当前注视的带方格上印刷一个非空白字符 左移时,必须在当前注视的带方格中印刷空白字符B。 一个确定的双栈机(double stack machines)是一个确定的TM,它具有一条只读的输入带和两条存储带。存储带上的读头左移时,只能印刷空白符号B 。 下推自动机是一种非确定的多带TM。它有一条只读的输入带,一条存储带。 定理 9-9 一个任意的单带TM可以被一个确定的双栈机模拟。,65,(5) 计数机,计数机(counter machine) 有一条只读输入带和若干个用于计数的单向无穷带的离线TM。 拥有n个用于计数带的计数机被称为n计数机。 用于计数的带上仅有两种字符,一个为相当于是作为栈底符号的Z,该字符也可以看作是计数带的首符号,它仅出现在计数带的最左端;另一个就是空白符B。这个带上所记的数就是从Z开始到读头当前位置所含的B的个数。 定理 9-10 TM可以被一个双计数机模拟。,66,(6) 随机存取机,随机存取机(rando

    注意事项

    本文(Part4图灵机及可计算理论.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开