09 图灵机new

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

1、1形式语言与自动机第9章图灵机2第9章图灵机图灵机(Turingmachine)是由图灵(AlanMathisomTuring)在1936年提出的，它是一个通用的计算模型。通过研究TM，来研究递归可枚举集(recursivelyenumerableset)和部分递归函数(partialrecursivefunction)。对算法和可计算性进行研究提供形式化描述工具。3第9章图灵机计算机科学与技术学科研究的根本问题——什么能且如何被有效地自动计算。有效过程(effectiveprocedure)与算法(algorithm)。希尔伯特纲领

2、—计划构造一个可以判定所有数学命题真假的算法。1931年，奥地利25岁的数理逻辑学家哥德尔(KuriGödel)发表了著名的不完备性定理，指出这种形式系统根本不存在。具有有穷描述的过程是可数无穷多的，但函数却是不可数无穷多的。世界上存在着许多的问题和函数，是无法用具有有穷描述的过程完成计算的——是不可计算的(incomputable)。1936年，图灵提出一个通用的计算模型，它是计算机的一个简单的数学模型，与现今看到的计算机具有相同的功能。与TM具有同样计算能力的还有丘奇提出的λ演算、哥德尔提出的递归函数、波斯特提出的波斯特系统。丘奇

3、-图灵论题：可计算函数的直观概念可以用部分递归函数来等同。49.1基本概念图灵提出TM具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。5基本TM图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,δ,q0,B,F)Q为状态的有穷集合，q∈Q，q为M的一个状态。q0∈Q，是M的开始状态，对于一个给定的输

4、入串，M从状态q0启动，读头正注视着输入带最左端的符号。FQ，是M的终止状态集，q∈F，q为M的一个终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行。Γ为带符号表(tapesymbol)，X∈Γ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上。B∈Γ，被称为空白符(blanksymbol)，含有空白符的带方格被认为是空的。∑Γ-{B}为输入字母表，a∈∑，a为M的一个输入符号。除了空白符号B之外，只有∑中的符号才能在M启动时出现在输入带上。6基本TMδ:Q×ΓQ×Γ×{R,L

5、}，为M的移动函数(transactionfunction)。δ(q,X)=(p,Y,R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格；δ(q,X)=(p,Y,L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。7TM的工作过程演示h££££statensymbol01tBs(s;0;!)(s;1;!)(q;t;Ã)(s;B;!)q(q0;t;!)(q1;t;!)(q;t;¡)(h;B;!)q0(s;0;Ã)(s;0;Ã)(s;0;Ã

6、)(h;B;!)q1(s;1;Ã)(s;1;Ã)(s;1;Ã)(h;B;!)0100BQ:WhatdoesthisTuringmachinedo?8例9-1设M1=({q0,q1,q2},{0,1},{0,1,B},δ,q0,B,{q2})，其中δ的定义如下：δ(q0,0)=(q0,0,R)δ(q0,1)=(q1,1,R)δ(q1,0)=(q1,0,R)δ(q1,B)=(q2,B,R)也可以用下表表示：01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,B,R)q2含且仅含一个1的0,1串才能将TMM1引导到终止状态

7、。1/1→0/0→q2q0q1B/B→0/0→9即时描述即时描述(instantaneousdescription,ID)12∈Γ*，q∈Q，1q2称为M的即时描述q为M的当前状态。当M的读头注视的符号右边还有非空白符时,12为M的输入带最左端到最右的非空白符号组成的符号串。否则12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串。M正注视着2的最左符号。10即时描述设X1X2…Xi-1qXiXi+1…Xn是M的一个ID如果δ(q,Xi)=(p,Y,R)，则M的下一个ID为X1X2…Xi-1YpXi+1…

8、Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…Xi-1YpXi+1…Xn。如果δ(q,Xi)