- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
8_2图灵机
*College of Computer Science Technology, BUPT * 图灵机 A.Turing在1936年 介绍了这样一个通用的计算模型,该模型具有以下两个性质 该模型的每个过程都是有穷可描述的; 过程必须是由离散的、可以机械执行的步骤组成。 图灵机是计算机的一种简单数字模型,尽管简单,但它具有模拟通用计算机的计算能力。 通过研究TM来研究递归可枚举集和部分递归函数 为算法和可计算性研究提供了形式化描述工具。 * Finite control X 1 B B ... X 2 X n X i 带(tape) 单元格(cell) 带符(tape symbol) 读写头在每一时刻扫描带上的一个单元 带有一个最左单元,向右则是无限的。 带的每个单元可容纳一个带符号 开始时,最左边n个单元装着输入(n=0,n为有限数),它是一个字符串,符号都选自“带符号”的一个子集,即所谓的“输入符号集合”。余下的有穷个单元都存放空白符,它是一个特殊的带符号,但不是输入符号。 图灵机的基本模型 * 在一个图灵机的动作中,图灵机根据带头(读写头)所扫描的符号和有限控制器的状态可能作 改变状态 在被扫描的带单元上重新写一个符号,以代替原来写在该单元上的符号. 将带头向左或者右移一个单元。 * 图灵机和双向有限自动机的区别:图灵机能改变它带上的符号。 图灵机的工作机制 * 图灵机的形式化描述 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合 q0 ? Q T ? ? B ? ? – T F ? Q 转移函数? : Q ? ? ? Q ? ? ? { L,R } 形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T, ?, ?, q0 , B , F ). * δ函数示例: Q×∑ → Q×∑×{L ,R} δ(q,ai)=(p,B,L) q, p ∈Q δ(q,ai)=(p,b,R) ai∈∑ b∈∑ 格局 用w1q w2描述图灵机的瞬间工作状态 q为M的当前状态, w1w2∈ ∑* w1w2是当前时刻从开始端(因为可写)到右边空白符号为止的内容 当读写头已达到带的右端,则w1w2为读写头以左的内容。 约定:w1q w2表示读写头正扫描w2的最左字符 w2=? 则表示读写头正扫描一个空白字符。 图灵机的函数与格局 * 图灵机的格局 给定图灵机 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. * 图灵机接受的语言 L(M) = {ω│ω∈T*且q0ω├* α1 p α2 ,p∈F, α1α2∈∑*} 图灵机接受的语言是输入字母表中这样一些字符串的集合,初始时,这些字符串放在M的带上,M处于状态q0,且M的带头处在最左单元上,这些字符串将使M进入某个终止状态。 假定: 当输入被接受时,图灵机将停止,没有下一个动作。 * 任给图灵机 M = (Q, T, ?, ?, q0 , B , F ) ,以及输入字符串w?T*. 试问:对于w,M 是否停机? 停机是指图灵机不存在下一个移动步(move). 结论 图灵机的停机问题是不可解的(即不可判定的). 结论 任给图灵机 M ,很容易构造一个图灵机 M?,使得L(M)= L(M? ),并满足:如果w?L(M) ,则对于 w,M? 接受w并一定停机. 如果没有特别指出,总是假定图
文档评论(0)