Part4图灵机及可计算理论(精)

Part4图灵机及可计算理论主讲教师贺利坚2Part4主要内容提示内容教材出处一、图灵机及形式定义9.1基本概念(9.1.1)二、图灵机的构造9.1基本概念(9.1.1-3)三、图灵机的变形9.2图灵机的变形四、通用图灵机9.3通用图灵机五、可计算性理论9.4可计算性理论的几个相关概念3一、图灵机及形式定义1、图灵机2、图灵机的形式定义3、图灵机接受的语言4图灵机FA和PDA的局限FA有有限的存储，只能处理RLPDA用栈提供无限的存储，但栈只能后进先出，PDA只能处理CFLFA和PDA不能用作通用的计算模型5图灵机是通用的计算模型，是计算机的数学模型图灵在论述“有些数学问题是不可解的”时，提出了图灵机图灵论题：凡是可计算的函数，都可以用图灵机计算丘奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现提出TM的目的在于:对有效的计算过程(即算法)进行形式化的描述,忽略模型的存储容量在内的一些枝节问题,只考虑算法的基本特征.图灵提出TM具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。图灵机6图灵生平1912年出生，演算能力突出1931年，进剑桥大学学数学1936年，提出图灵机模型1938年，获普灵斯顿大学博士学位1950年，发表论文“计算机和智能”，提出图灵测试1951年，成为英皇家学会院士1954年，不幸去世现代计算机设计思想的创始人，人工智能领域的开拓者计算机领域的最高奖以图灵命名图灵机7AlanTuring(1912-1954)1912(23June):Birth,Paddington,London1926-31:SherborneSchool1930:DeathoffriendChristopherMorcom1931-34:UndergraduateatKing'sCollege,CambridgeUniversity1932-35:Quantummechanics,probability,logic1935:ElectedfellowofKing'sCollege,Cambridge1936:TheTuringmachine,computability,universalmachine1936-38:PrincetonUniversity.Ph.D.Logic,algebra,numbertheory1938-39:ReturntoCambridge.IntroducedtoGermanEnigmaciphermachine1939-40:TheBombe,machineforEnigmadecryption1939-42:BreakingofU-boatEnigma,savingbattleoftheAtlantic1943-45:ChiefAnglo-Americancryptoconsultant.Electronicwork.1945:NationalPhysicalLaboratory,London1946:Computerandsoftwaredesignleadingtheworld.1947-48:Programming,neuralnets,andartificialintelligence1948:ManchesterUniversity1949:Firstseriousmathematicaluseofacomputer1950:TheTuringTestformachineintelligence1951:ElectedFRS.Non-lineartheoryofbiologicalgrowth1952:Arrestedasahomosexual,lossofsecurityclearance1953-54:Unfinishedworkinbiologyandphysics1954(7June):Death(suicide)bycyanidepoisoning,Wilmslow,Cheshire.8图灵机的物理模型基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。图灵机9图灵机的形式定义定义9-1图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,,q0,B,F)Q：状态的有穷集合，q∈Q为M的一个状态；∑：输入字母表，a∑为M的一个输入符号。除空白符号B外，只有∑中的符号才能在M启动时出现在输入带上；Γ：带符号表(tapesymbol)，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上；q0∈Q：M的开始状态，M从状态q0启动，读头正注视着输入带最左端的符号；B：空白符(blanksymbol)，含空白符的带方格是空的；FQ：M的终止状态集，q∈F为M的一个终止状态。TMM一旦进入终止状态，它就停止运行。10TMM=(Q,∑,Γ,,q0,B,F)称为移动函数：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，然后将读头向左移一格。图灵机的形式定义11例TMM1=({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)M1的移动函数的另一种表示:图灵机的形式定义q2(q2,B,R)(q1,0,R)q1(q1,1,R)(q0,0,R)q0B10状态L(M1)={x|x∈{0,1}+，且x中有且仅有一个1}12补充：图灵机的转移图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)Sq0q1q20/0→1/1→0/0→B/B→当(q,X)=(p,Y,D)时，在q到p的弧上标记X/YD，D为→或←L(M1)={x|x∈{0,1}+，且x中有且仅有一个1}图灵机的形式定义13图灵机接受的语言定义9-2即时描述(instantaneousdescription,ID)12∈*，q∈Q，1q2称为M的即时描述q为M的当前状态，M正注视着2的最左符号。当M的读头注视的符号右边还有非空白符时，12为M的输入带最左端到最右的非空白符号组成的符号串；否则，12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串14设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设X1X2…Xi-1qXiXi+1…Xn是M的一个ID，如果(q,Xi)=(p,Y,L),则当i≠1时，M的下一个ID为X1X2…pXi-1YXi+1…Xn记作X1X2…Xi-1qXiXi+1…Xn├MX1X2…pXi-1YXi+1…Xn图灵机接受的语言15├Mn表示├M的n次幂：├Mn=(├M)n├M+表示├M的正闭包：├M+=(├M)+├M*表示├M的克林闭包：├M*=(├M)*在意义明确时，用├、├n、├+、├*表示图灵机接受的语言16例M1在处理输入串的过程中经历的ID变换序列M1=({q0,q1,q2},{0,1},{0,1,B},,q0,B,{q2})图灵机接受的语言├M000100Bq2├M000100q1├M00000q0B├M00010q11├M00010q10├M0000q00├M0001q101├M0001q100├M000q000├M000q0101├M000q0100├M00q0000├M00q00101├M1Bq2├M00q00100├M0q00000├M0q000101├M1q1├M0q000100q000000q0000101q01q0000100（4）00000（3）000101（2）1（1）000100(q0,0)=(q0,0,R)(q0,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,B)=(q2,B,R)17定义9-3TM接受的语言TMM=(Q,∑,Γ,,q0,B,F)L(M)={x|x∈∑*且q0x├M*1q2&qF&1,2*}只要在工作过程中能进入终止状态（之一），则可以判断被接受并停机。图灵机不停地计算：当输入被接受时,图灵机将停止,没有下一个动作;当因未定义转换函数,图灵机无法计算下去时,将拒绝执行;如果不进入任何接受或拒绝状态,继续执行下去,永不停止。在TM接受的语言中，包含那些不能使TM停机的输入。图灵机接受的语言18语言定义9-4TM接受的语言叫做递归可枚举语言(recursivelyenumerablelanguage，r.e.)。如果存在TMM=(Q,∑,Γ,,q0,B,F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursivelylanguage)。x是任意的串x∈L，M进入接受状态并停机xL，M也可以停机，但不进入接受状态M不能停机，则可能是r.e.，或其他语言可以按TM接受及停机分类图灵机接受的语言r.e.递归语言TM能够定义TM能够计算19例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接受的语言是什么？Sq0q10/0→1/1→0/0→1/1→q20/0→1/1→q3图灵机接受的语言01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,1,R)q2(q2,0,R)(q3,1,R)q3M2接受的语言是字母表{0,1}上那些至少含有3个1的0、1符号串。借助其他描述方法的观察:20M2=({q0,q1,q2,q3},{0,1},{0,1,B},,q0,B,{q3})处理输入串的过程:图灵机接受的语言思考：如何构造出接受字母表{0,1}上那些含且恰含有3个1的符号串的TM。关键：不读完不能进入终态（3）1001100101100：q01001100101100├1q1001100101100├10q101100101100├100q11100101100├1001q2100101100├10011q300101100（1）00010101：q000010101├0q00010101├00q0010101├000q010101├0001q10101├00010q1101├000101q201├0001010q21├00010101q3（2）000101000：q0000101000├0q000101000├00q00101000├000q0101000├0001q101000├00010q11000├000101q2000├0001010q200├00010100q20├000101000q2B22Part4主要内容提示内容教材出处一、图灵机及形式定义9.1基本概念(9.1.1)二、图灵机的构造9.1基本概念(9.1.1-3)三、图灵机的变形9.2图灵机的变形四、通用图灵机9.3通用图灵机五、可计算性理论9.4可