电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

基本图灵机及图灵机的构造技术

31页
  • 卖家[上传人]:xh****66
  • 文档编号:61657788
  • 上传时间:2018-12-08
  • 文档格式:PPT
  • 文档大小:355.50KB
  • / 31 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、1,School of Computer Science & Technology, BUPT,第五章 图灵机,A.Turing在1936年介绍了这样一个通用的计算模型,该模型具有以下两个性质 该模型的每个过程都是有穷可描述的; 过程必须是由离散的、可以机械执行的步骤组成。 图灵机是计算机的一种简单数字模型,尽管简单,但它具有模拟通用计算机的计算能力。 通过研究TM来研究递归可枚举集和部分递归函数 为算法和可计算性研究提供了形式化描述工具。,2,School of Computer Science & Technology, BUPT,主要内容,TM的基本定义 TM的格局 TM接受的语言 TM的构造技术 TM的变形; 重点: TM的定义、TM的构造。 难点: TM的构造。,3,School of Computer Science & Technology, BUPT,读写头在每一时刻扫描带上的一个单元 带有一个最左单元,向右则是无限的。 带的每个单元可容纳一个带符号 开始时,最左边n个单元装着输入(n0,n为有限数),它是一个字符串,符号都选自“带符号”的一个子集,即所谓的“输入符号集

      2、合”。余下的有穷个单元都存放空白符,它是一个特殊的带符号,但不是输入符号。,图灵机的基本模型,4,School of Computer Science & Technology, BUPT,在一个图灵机的动作中,图灵机根据带头(读写头)所扫描的符号和有限控制器的状态可能作 改变状态 在被扫描的带单元上重新写一个符号,以代替原来写在该单元上的符号. 将带头向左或者右移一个单元。 * 图灵机和双向有限自动机的区别:图灵机能改变它带上的符号。,图灵机的工作机制,5,School of Computer Science & Technology, BUPT,图灵机的形式化描述,有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合,q0 Q T B T F Q,转移函数 : Q Q L,R ,形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T, , , q0 , B , F ).,6,School of Computer Science & Technology, BUPT,函数示例: Q QL ,R (q,ai)=

      3、(p,B,L) q, p Q (q,ai)=(p,b,R) ai b 格局 用w1q w2描述图灵机的瞬间工作状态 q为M的当前状态, w1w2 * w1w2是当前时刻从开始端(因为可写)到右边空白符号为止的内容 当读写头已达到带的右端,则w1w2为读写头以左的内容。 约定:w1q w2表示读写头正扫描w2的最左字符 w2 则表示读写头正扫描一个空白字符。,图灵机的函数与格局,7,School of Computer Science & 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+

      4、1Xn M X1X2Xi-1Y p Xi+1Xn , 但有如下两个例外 : (1)i=n时, X1X2Xn-1q Xn M X1X2Xn-1Y p B ,和 (2)i=1及 Y=B 时, q X1X2XnM B p X2Xn-1Xn.,8,School of Computer Science & Technology, BUPT,图灵机接受的语言,L(M) = T*且q0* 1 p 2 ,pF, 12* 图灵机接受的语言是输入字母表中这样一些字符串的集合,初始时,这些字符串放在M的带上,M处于状态q0,且M的带头处在最左单元上,这些字符串将使M进入某个终止状态。 假定: 当输入被接受时,图灵机将停止,没有下一个动作。,9,School of Computer Science & Technology, BUPT,任给图灵机 M = (Q, T, , , q0 , B , F ) ,以及输入字符串wT*. 试问:对于w,M 是否停机? 停机是指图灵机不存在下一个移动步(move). 结论 图灵机的停机问题是不可解的(即不可判定的). 结论 任给图灵机 M ,很容易构造一个图灵机 M,使得

      5、L(M)= L(M ),并满足:如果wL(M) ,则对于 w,M 接受w并一定停机. 如果没有特别指出,总是假定图灵机到达终态(接受态)后一定停机. 但是 ,对不能接受的字符串,图灵机可能永不停止.(只要M还在某个输入上运行,我们无法知道是因为运行的时间不够长而没有被接受,还是根本就不会停机),图灵机的停机问题,10,School 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的个数,不接受。,11,School of Computer Science & Technology, BUPT,例1 L=an bnn=1

      6、,(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 xxyq1bxxq2yyxq2xyyxxq0yyxxyq3yxxyyq3Bxxyyq4,12,School of Computer Science & Technology, BUPT,对于输入字符串001122,该图灵机可以有如下推导步:,q0001122,M,Xq101122,M,X0q11122,M,X0Yq2122,M,X0Y1q222,M,X0Yq31Z2,*M,q3X0Y1Z2,M,Xq00Y1Z2,*M,XXYYZq22,M,XXYYq3ZZ,*M,Xq3XYYZZ,M,XXq0YYZZ,*M,X

      7、XYYq4ZZ,M,XXYYZq5Z,M,XXYYZZq5B,M,XXYYZZBq6B,例2 L = 0n1n2n n 1.,13,School of Computer Science & Technology, BUPT,转移图与转移表,14,School of Computer Science & Technology, BUPT,作为整数函数计算机的图灵机,预备知识:图灵机除了作为语言接受器外,还可看作整数到整数的函数计算机。 传统方法把整数表示成一进制 整数 i 0 用字符串 0i 表示 如果一个函数有k个自变量,i1,i2 ,ik,那么这些整数开始时被放在带上,并用1把他们分隔开。 形如 0i1 1 0i2 1 0i3 1 0ik 如果图灵机停止(不论是否在一个接受状态上)且带上为 0m,则 f(i1,i2,ik)= m f是被图灵机计算的k元函数 如果f(i1,i2,ik)对所有i1,i2,ik有定义, 那么称f是一个全递归函数。全递归函数对应于递归语言,因为它总是被能停下来的图灵机所计算。 所有常用的整数算术函数都是全递归函数。,15,School of Computer

      8、 Science & Technology, BUPT,例3:设计图灵机求真减法,思路: 1. 用空白符B代替带上的最左端的0 2右移至紧跟1后的0,将其改为1 3左移找到B,将B之后的0改为B 4重复上述过程 如果(1)右移找0时,遇到B,意味着mn BBB 0 m-(n+1) 1 111 n+1 n个 将后面n+1个1变为B,将左侧最后一个B变0,形如 BBB 0 0 m-(n+1) BBB n个 n+1个 这时,带上留下m-n个0,即结果为m-n,初始带 0m 10n,16,School of Computer Science & Technology, BUPT,求真减法(续),(2) M左移找不到0,意味着 n m,形如 BBB 1 111 00 m个 m个 n-m个 此时, 用B替换所有剩余的1 和0,17,School of Computer Science & Technology, BUPT,例4:L= 0 m m=2n, n 0,设计思路:对输入串w 1. 从左到右扫描带,隔一个消一个0; 2若带上只剩唯一一个0,接受; 3若带上不止一个0,且个数为奇数,拒绝; 4

      9、让读写头返回带的最左端; 5. 转第一步。,18,School of Computer Science & Technology, BUPT,识别 L= 0 m m=2n, n 0的图灵机,19,School of Computer Science & Technology, BUPT,课堂练习,设计一个状态数不超过3的图灵机,它能够接受语言L=a(a+b)* ,若假定T=a,b,两个状态的图灵机能否接受该语言?,20,School of Computer Science & Technology, BUPT,5.2 图灵机的构造技术,在设计图灵机的过程中,写出函数很麻烦,为了构造复杂的图灵机,需探讨图灵机的若干构造技术,并引入一些新的概念和工具。 目的:设计时方便,但这些构造技术并未增加图灵机的功能。,21,School of Computer Science & Technology, BUPT,5.2.1. 利用带存储区的状态(storage in the state),此类图灵机 M = (Q, , , , q0 , B , F ) 中,状态中可以包含 一个具有有限个取值的存储单元,即状态集合为 Q = ST = q,a | qS aT , 其中 qS 通常表示控制状态,而 aT 通常表示数据元素. 一般情况下,有限控制器内允许存储n个字符,即状态的第2个元素可存储n个字符。,22,School of Computer Science & Technology, BUPT,例:设计一个图灵机,读写头将扫视第一个字符存入有限控制器内,然后扫视整个带,若找不到与第一个相同的字符,则M接受该字符串,否则不接受。 构造M=(Q,a,b,a,b,B,q0

      《基本图灵机及图灵机的构造技术》由会员xh****66分享,可在线阅读,更多相关《基本图灵机及图灵机的构造技术》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.