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

《基本图灵机及图灵机的构造技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。通过研究TM来研究递归可枚举集和部分递归函数为算法和可计算性研究提供了形式化描述工具。1SchoolofComputerScience&Technology,BUPT主要内容TM的基本定义TM的格局TM接受的语言TM的构造技术TM的变形；重点:TM的定义、TM的构造。难点:TM的构造。2SchoolofComputerScience&T

2、echnology,BUPTFinitecontrolX1BB...X2XnXi带（tape）单元格（cell）带符（tapesymbol）读写头在每一时刻扫描带上的一个单元带有一个最左单元，向右则是无限的。带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n>＝0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。图灵机的基本模型3SchoolofComputerScience&Technology,BUPT在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符

3、号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.将带头向左或者右移一个单元。*图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。图灵机的工作机制4SchoolofComputerScience&Technology,BUPT图灵机的形式化描述有限状态集有限输入符号集有限带符号集转移函数开始状态特殊带符:空白符终态集合q0QTB–TFQ转移函数:QQ{L,R}形式定义一个图灵机TM(Turingmachine)是一个七元组M=(Q,T,,,q0,B,F).5SchoolofComputerScie

4、nce&Technology,BUPTδ函数示例：Q×∑→Q×∑×{L,R}δ(q,ai)=(p,B,L)q,p∈Qδ(q,ai)=(p,b,R)ai∈∑b∈∑格局用w1qw2描述图灵机的瞬间工作状态q为M的当前状态，w1w2∈∑*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：w1qw2表示读写头正扫描w2的最左字符w2＝则表示读写头正扫描一个空白字符。图灵机的函数与格局6SchoolofComputerScience&Technology,BUPT图灵机的格局给定图灵机M=(Q,T,,,q0,B,

5、F)，定义格局之间的推导关系├M如下：1.设(q,Xi)=(p,Y,L)，则有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-2pXi-1Y…Xn，但有如下两个例外：（1）i=1时，qX1X2…Xn├MqYX2…Xn，和（2）i=n及Y=B时，X1X2…Xn-1qXn├MX1X2…Xn-2pXn-1B.2.设(q,Xi)=(p,Y,R)，则有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn，但有如下两个例外：（1）i=n时，X1X2…Xn-1qXn├MX1X2…Xn-1YpB，和（2）i=1及Y=B时，qX1X2…Xn├MBpX2…Xn

6、-1Xn.7SchoolofComputerScience&Technology,BUPT图灵机接受的语言L(M)={ω│ω∈T*且q0ω├*α1pα2,p∈F,α1α2∈∑*}图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：当输入被接受时，图灵机将停止，没有下一个动作。8SchoolofComputerScience&Technology,BUPT任给图灵机M=(Q,T,,,q0,B,F)，以及输入字符串wT*.试问：对于w，M是否停机？停机是指图灵机不存

7、在下一个移动步（move）.结论图灵机的停机问题是不可解的（即不可判定的）.结论任给图灵机M，很容易构造一个图灵机M，使得L(M)=L(M)，并满足：如果wL(M)，则对于w，M接受w并一定停机.如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机.但是，对不能接受的字符串，图灵机可能永不停止.（只要M还在某个输入上运行，我们无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）图灵机的停机问题9SchoolofComputerScience&Techn