09下推自动机new

《09下推自动机new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言与自动机FormalLanguagesandAutomataTheory第八章图灵机教师：胡春明、赵永望http://act.buaa.edu.cn/zhaoyw/course/flat_2012.html第八章图灵机图灵机的提出基本概念计算模型构造方法2艾伦·图灵简介AlanMathisonTuringhttp://zh.wikipedia.org/wiki/艾伦·图灵http://baike.baidu.com/view/2130.htm参阅《逻辑的引擎》关注更多计算机科学家的故事，图灵机的提出计算机科学与技术研究的根本问题是：什么

2、能且如何被有效地自动计算。即，对于某一类问题，我们希望能有一个适当的有效过程来进行处理。这个有效过程就是我们习惯的算法。这不是一个简单的问题，例如对于具有有穷描述的语言，判断它是否为空？是否为无穷？构造处理它们的算法并不总是能做到早在20世纪初，数学家希尔伯特曾计划构造一个可以判定所有数学命题真假的算法，该计划称为“希尔伯特纲领”。其基础是19世纪英国数学家乔治.布尔创立的布尔代数。他从构造判定所有的关于整数的一阶谓词演算公式的真、假的算法入手。一阶谓词演算足以表示CFG产生的*中的任何句子，因此，这个问题相当于“判定一个CFL的补是否为空

3、？”图灵机的提出1931年，奥地利25岁的数理逻辑学家哥德尔﹙K．Gödel﹚提出的关于形式系统的“不完备性定理”中指出，这种形式系统是不存在的，从而宣告了著名的“西尔伯特纲领”的失败。它告诉人们，一个形式系统是不能穷尽所有的数学命题的。哥德尔构造了一个关于整数谓词演算公式，在这个逻辑系统中，既不能否定它，也不能肯定他。在哥德尔研究成果的影响下，图灵从计算一个数的一般过程入手对计算的本质进行了研究，所谓计算就是计算者﹙人或机器﹚对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定

4、的符号串的变换过程。用形式化方法成功表述可·图灵的手稿计算这一过程的本质。图灵机的提出图灵的研究成果可计算性＝图灵可计算性。在进行可计算性问题的讨论时，不可避免地要提到一个与计算具有同等地位和意义的基本概念，那就是算法。算法也称为能行方法或能行过程，是对解题﹙计算﹚过程的精确描述，它由一组定义明确且能机械执行的规则﹙语句、指令等﹚组成。根据图灵的论点，可以得到这样的结论：任一过程是能行的﹙能够具体表现在一个算法中﹚，当且仅当它能够被一台图灵机实现。图灵机等计算模型均是用来解决问题的，理论上的能行性隐含着计算模型的正确性，而实际实现中的能行性还包

5、含时间与空间的有效性。图灵机的提出图灵机停机问题（不可判定问题之一）图灵机停机问题:能否给出一个判断任意一个图灵机是否停机的一般方法?答案是NO,不可能.问题实际上是问:是否存在一台"万能的"图灵机H,把任意一台图灵机M输入给H,它都能判定M最终是否停机,输出一个明确的"yes"或"no"的答案?假定存在一个能够判定任意一台图灵机是否停机的万能图灵机H(M),如果M最终停机,H输出"halt";如果M不停机,H输出"loop".我们把H当作子程序,构造如下程序P:functionP(M){if(H(M)=="loop")return"

6、halt";elseif(H(M)=="halt")while(true);//loopforever}因为P本身也是一台图灵机,可以表示为一个字符串,所以我们可以把P输入给它自己,然后问P(P)是否停机.按照程序P的流程,如果P不停机无限循环,那么它就停机,输出"halt";如果P停机,那么它就无限循环,不停机;这样无论如何我们都将得到一个矛盾,所以假设前提不成立,即不存在这样的H.或者说,图灵机停机问题是不可判定的9.1基本概念对算法和可计算性进行研究提供形式化描述工具图灵机具有以下两个性质具有有穷描述。过程必须是由离散的、可以机

7、械执行的步骤组成。基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。9.1基本概念一个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。9.1.1基本图灵机图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,δ,q,B,F)，0Q为状态的有穷集合，q∈Q，q为M的一个状态；q∈Q，是M的开始状态，对于一个给定的输入串，M从状态q启00动，读头正注视着输入带最左端的符号；FQ，是M的终止状态集，q∈F，q为M的一个

8、终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行。Γ为带符号表(tapesymbol)，X∈Γ，X为M的一个带符号，表示在M