形式语言自动机 图灵机 Turing Machine课件.ppt

《形式语言自动机 图灵机 Turing Machine课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杨磊图灵机TuringMachineTuringMachine——————————————————————————————————————阿兰-图灵阿兰·麦席森·图灵（1912~1954），英国著名数学家、逻辑学家、密码学家，被称为计算机科学之父、人工智能之父。生于英国帕丁顿，二战爆发后帮助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。其实也正是因为二战，英国政府才肯掏钱让图灵 制造最原始的计算机。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念最后，在他事业刚刚达 到顶风的时候，他自杀了。为了纪念这个伟大的学者，

2、计算机界设立了最高荣誉奖：ACM图灵奖。TuringMachine——————————————————————————————————————图灵机模型1936年，阿兰—图灵提出了一种抽象的计算模型——图灵机(Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：1.在纸上写上或擦除某个符号；2.把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于 此人当前所关注的纸上某个位置的符号和此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想

3、的机器TuringMachine——————————————————————————————————————图灵机模型组成：1.一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号  表示空白。2.一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。3.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。4.一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符

4、号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。TuringMachine——————————————————————————————————————图灵机TuringMachine——————————————————————————————————————形式化一台图灵机是一个七元组，{Q，Σ，Γ，δ，q0,B,F}，其中Q，Σ，Γ都是有限集合，且满足1.Q是有穷状态集合；∀q∈Q，q为M的一个状态；2.Σ是有限输入符号集，∀a∈Σ，a为M的一个输入符号。除了空白符号B之外，只有Σ中的符号才能在M启动时出现在输入带上；3.

5、Γ是有限带符号集，∀X∈Γ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带4.δ：Q×「→Q×Γ×{L,R}是转移函数，其中L,R表示读写头是向左移还是向右移；TuringMachine——————————————————————————————————————5.q0∈Q是起始状态；q0∈Q，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号；6.B是被称为空白符(blanksymbol)，含有空白符的带方格被认为是空的；7.F是M的终止状态集，∀q∈F，q为M的一个终止状态。一旦M进入终止状态，它就停止

6、运行。TuringMachine——————————————————————————————————————形式化开始的时候将输入符号串从左到右依此填在纸带的第几号格子上，其他格子保持空白（即填以空白符）。M的读写头指向第0号格子，M处于状态q0。机器开始运行后，按照转移函数δ所描述的规则进行计算。例如，若当前机器的状态为q，读写头所指的格子中的符号为x，设δ（q,x)=(q',x',L），则机器进入新状态q'，将读写头所指的格子中的符号改为x'，然后将读写头向左移动一个格子。若在某一时刻，读写头所指的是第0号格子，但根据转移函数它下一步将继续向左移

7、，这时它停在原地不动。TuringMachine——————————————————————————————————————小虫模型输入I={黑色，白色}，输出O={前进，后退}规则={输入输出黑色前移白色后移}读写头纸带然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个 最简单的模型。首先，我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身改造TuringMachine——————————————————————————————————————小虫模型II输入I={黑色，白色}，输出O={前进，后退，涂黑，涂白}规

8、则={输入输出黑色前移白色涂黑}读写头纸带小虫子会一直机械的向前走。模型的问题：那就是如果你给它固定的输入信