第二讲 图灵机模型

《第二讲 图灵机模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2讲图灵机模型图灵机(Turingmachine)是由图灵（AlanMathisomTuring）在1936年提出的，它是一个通用的计算模型。通过研究图灵机，来研究递归可枚举集（recursivelyenumerableset）和部分地归函数（partialrecursivefunction）。对算法和可计算性进行研究提供形式化描述工具。1主要内容、重难点主要内容图灵机作为一个计算模型，它的基本定义，即时描述，图灵机接受的语言；图灵机的构造技术；图灵机的变形；Church-Turing论题；通用图灵机。可计算语言、不可判定性

2、、P-NP问题)。重点图灵机的定义、图灵机的构造。难点图灵机的构造。22.1基本概念图灵提出图灵机具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一个移动将完成以下三个动作改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。3直观物理模型42.1.1基本图灵机图灵机（Turingmachine）/基本的图灵机M=(Q,∑,Γ,δ,q0,B,F)，Q为状态的有穷集合，q∈Q，q为M的一个状态；q

3、0∈Q，是M的开始状态，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号；52.1.1基本图灵机FQ，是M的终止状态集，q∈F，q为M的一个终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行；Γ为带符号表（tapesymbol），X∈Γ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上；62.1.1基本图灵机B∈Γ，被称为空白符（blanksymbol），含有空白符的带方格被认为是空的；∑Γ-{B}为输入字母表，a∈∑，a为M的一个输入符号。除了空白符

4、号B之外，只有∑中的符号才能在M启动时出现在输入带上；72.1.1基本图灵机δ：Q×ΓQ×Γ×{R,L}，为M的移动函数（transactionfunction）。δ(q,X)=(p,Y,R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格；δ(q,X)=(p,Y,L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。8例子2-1说明例2-1设M1=({q0,q1,q2},{0,1},{0,1,B},δ,q0,B,{q2})，其中

5、δ的定义如下，对于此定义，也可以用表2-1表示。δ(q0,0)=(q0,0,R)δ(q0,1)=(q1,1,R)δ(q1,0)=(q1,0,R)δ(q1,B)=(q2,B,R)9例子2-1说明01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,B,R)q2102.1.1基本图灵机即时描述(instantaneousdescription,ID)α1α2∈Γ*，q∈Q，α1qα2称为M的即时描述q为M的当前状态。α1α2为M的输入带最左端到最右的非空白符号组成的符号串或者是M的输入带最左端到M的读头注视的带方格

6、中的符号组成的符号串M正注视着α2的最左符号。112.1.1基本图灵机设X1X2…Xi-1qXiXi+1…Xn是M的一个ID如果δ(q,Xi)=(p,Y,R)，则，M的下一个ID为X1X2…Xi-1YpXi+1…Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…Xi-1YpXi+1…Xn。122.1.1基本图灵机如果δ(q,Xi)=(p,Y,L)则，当i≠1时，M的下一个ID为X1X2…pXi-1YXi+

7、1…Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…pXi-1YXi+1…Xn；132.1.1基本图灵机├M是Γ*QΓ*×Γ*QΓ*上的一个二元关系├Mn表示├M的n次幂：├Mn=(├M)n├M+表示├M的正闭包：├M+=(├M)+├M*表示├M的克林闭包：├M*=(├M)*在意义明确时，分别用├、├n、├+、├*表示├M、├Mn、├M+、├M*。142.1.1基本图灵机例2-2.例2-1所给的M1在处

8、理输入串的过程中经历的ID变换序列。（1）处理输入串000100的过程中经历的ID的变换序列如下：q0000100├M0q000100├M00q00100├M000q0100├M0001q100├M00010q10├M000100q1├M000100Bq2152.1.1基本图