09 图灵机

1形式语言与自动机2第9章图灵机图灵机(Turingmachine)是由图灵(AlanMathisomTuring)在1936年提出的，它是一个通用的计算模型。通过研究TM，来研究递归可枚举集(recursivelyenumerableset)和部分递归函数(partialrecursivefunction)。对算法和可计算性进行研究提供形式化描述工具。3第9章图灵机计算机科学与技术学科研究的根本问题——什么能且如何被有效地自动计算。有效过程(effectiveprocedure)与算法(algorithm)。希尔伯特纲领—计划构造一个可以判定所有数学命题真假的算法。1931年，奥地利25岁的数理逻辑学家哥德尔(KuriGödel)发表了著名的不完整性理论，指出这种形式系统根本不存在。具有有穷描述的过程是可数无穷多的，但函数却是不可数无穷多的。世界上存在着许多的问题和函数，是无法用具有有穷描述的过程完成计算的——是不可计算的(incomputable)。1936年，图灵提出一个通用的计算模型，它是计算机的一个简单的数学模型，与现今看到的计算机具有相同的功能。与TM具有同样计算能力的还有丘奇提出的λ演算、哥德尔提出的递归函数、波斯特提出的波斯特系统。丘奇-图灵论题：可计算函数的直观概念可以用部分递归函数来等同。49.1基本概念图灵提出TM具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。5基本TM图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,δ,q0,B,F)Q为状态的有穷集合，q∈Q，q为M的一个状态。q0∈Q，是M的开始状态，对于一个给定的输入串，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}，为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;Ã)(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引导到终止状态。9例9-11/1→0/0→q2q0q1B/B→0/0→01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,B,R)q210即时描述即时描述(instantaneousdescription,ID)12∈Γ*，q∈Q，1q2称为M的即时描述q为M的当前状态。当M的读头注视的符号右边还有非空白符时,12为M的输入带最左端到最右的非空白符号组成的符号串。否则12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串。M正注视着2的最左符号。11即时描述设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。如果δ(q,Xi)=(p,Y,L)，则当i≠1时，M的下一个ID为X1X2…pXi-1YXi+1…Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn表示M在IDX1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…pXi-1YXi+1…Xn；12即时描述├M是Γ*QΓ*×Γ*QΓ*上的一个二元关系├Mn表示├M的n次幂：├Mn=(├M)n├M+表示├M的正闭包：├M+=(├M)+├M*表示├M的克林闭包：├M*=(├M)*在意义明确时，分别用├,├n,├+,├*表示├M,├Mn,├M+,├M*。13例9-2考察M1在处理输入串的过程中经历的ID变换序列。(1)处理输入串000100的过程中经历的ID的变换序列如下：q0000100├M0q000100├M00q00100├M000q0100├M0001q100├M00010q10├M000100q1├M000100Bq2(2)处理输入串0001的过程中经历的ID变换序列如下：q00001├M0q0001├M00q001├M000q01├M0001q1├M0001Bq2(3)处理输入串000101的过程中经历的ID变换序列如下：q0000101├M0q000101├M00q00101├M000q0101├M0001q101├M00010q111/1→0/0→q2q0q1B/B→0/0→14例9-2考察M1在处理输入串的过程中经历的ID变换序列。(4)处理输入串1的过程中经历的ID变换序列如下：q01├M1q1├M1Bq2(5)处理输入串00000的过程中经历的ID变换序列如下：q000000├M0q00000├M00q0000├M000q000├M0000q00├M00000q0B1/1→0/0→q2q0q1B/B→0/0→15TM接受的语言TM接受的语言L(M)={x|x∈∑*且q0x├M*1q2且q∈F且1,2∈Γ*}TM接受的语言叫做递归可枚举语言(recursivelyenumerablelanguage，r.e.)。如果存在TMM=(Q,∑,Γ,δ,q0,B,F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursivelylanguage)。16例9-3设有M2=({q0,q1,q2,q3},{0,1},{0,1,B},δ,q0,B,{q3})，其中δ的定义如下：δ(q0,0)=(q0,0,R)δ(q0,1)=(q1,1,R)δ(q1,0)=(q1,0,R)δ(q1,1)=(q2,1,R)δ(q2,0)=(q2,0,R)δ(q2,1)=(q3,1,R)试分析M2接受的语言。01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,1,R)q2(q2,0,R)(q3,1,R)q317例9-3为了弄清楚M2接受的语言，需要分析它的工作过程。(1)处理输入串00010101的过程中经历的ID变换序列如下：q000010101├0q00010101├00q0010101├000q010101├0001q10101├00010q1101├000101q201├0001010q21├00010101q3M2在q0状态下，遇到0时状态仍然保持为q0，同时将读头向右移动一格而指向下一个符号；在q1状态下遇到第一个1时状态改为q1，并继续右移读头，以寻找下一个1；在遇到第二个1时，动作类似，只是将状态改为q2；当遇到第三个1时，进入终止状态q3，此时它正好扫描完整个输入符号串，表示符号串被M2接受。18例9-3(2)处理输入串1001100101100的过程中经历的ID变换序列如下：q01001100101100├1q1001100101100├10q101100101100├100q11100101100├1001q2100101100├10011q300101100M2遇到第三个1时，进入终止状态q3，输入串的后缀00101100还没有被处理。但是由于M2已经进入终止状态，表示符号串1001100101100被M2接受(3)处理输入串000101000的过程中经历的ID变换序列如下：q0000101000├0q000101000├00q00101000├000q0101000├0001q101000├00010q11000├000101q2000├0001010q200├00010100q20├000101000q2B当M2的ID变为000101000q2B时，因为无法进行下一个移动而停机,不接受输入串000101000。M2接受的语言是字母表{0,1}上那些至少含有3个1的0,1符号串。请考虑，如何构造出接受字母表{0,1}上那些含且恰含有3个1的符号串的TM。19例9-4构造TMM3，使L(M)={0n1n2n|n≥1}不能通过“数”0,1或者2的个数来实现检查。最为原始的方法来比较它们的个数是否是相同的：消除一个0、然后消除一个1，最后消除一个2。消除的0的带方格上印刷一个X，在消除的1的带方格上印刷一个Y，在消除的2的带方格上印刷一个Z。正常情况下，输入带上的符号串的一般形式为00…0011…1122…22TM启动后，经过一段运行，输入带上的符号串的一般情况为X…X0…0Y…Y1…1Z…Z2…2BB需要给予边界情况密切的关注。X…XX…XY…YY…YZ…Z2…2BBX…XX…XY…Y1…1Z…Z2…2BBX…X0…0Y…YY…YZ…Z2…2BBX…X0…0Y…Y1…1Z…ZZ…ZBBX…X0…0Y…YY…YZ…ZZ…ZBB20例9-4构造思路21例9-4移动函数012XYZBq0(q0,X,R)(q4,Y,R)q1(q1,0,R)(q2,Y,R)(q1,Y,R)q2(q2,1,R)(q3,Z,L)(q2,Z,R)q3(q3,0,L)(q3,1,L)(q0,X,R)(q3,Y,L)(q3,Z,L)q4(q4,Y,R)(q4,Z,R)(q5,B,R)q522TM作为非负整函数的计算模型非负整数进行编码——1进制用符号串0n表示非负整数n。对于一个k元函数f(n1,n2,…,nk)，用符号串表示它的k个变元n1,n2,…,nk的值，并将其作为相应的TM的输入。如果f(n1,n2,…,nk)=m，则该TM的输出为0m。即该TM在处理完相应的输入串后停机，并且此时输入带上留下符号串0m。knnn1011002123TM作为非负整函数的计算模型图灵可计算的(Turingcomputable)设有k元函数f(n1,n2,…,nk)=m，TMM=(Q,∑,Γ,δ,q0,B,F)接受输入串输出符号串0m。当f(n1,n2,…,nk)无定义时，TMM没有恰当的输出给出。称TMM计算k元函数f(n1,n2,…,nk)，f(n1,n2,…,nk)为TMM计算的函数。也称f是图灵可计算的。knnn1011002124TM作为非负整函数的计算模型完全递归函数(totalrecu