8_2图灵机.ppt

*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并一定停机. 如果没有特别指出，总是假定图