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可

1 / 73
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功