离散数学(第5版)耿素云

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,10.4,图灵机,图灵机的基本模型,图灵机接受的语言,递归可枚举语言,用图灵机计算函数,部分可计算函数与可计算函数,2,问题的提出,1900,年,D.Hilbert,在巴黎第二届数学家大会上提出,著名的,23,个问题,.,第,10,个问题,:,如何判定整系数多项式是否有整数根,?,要求使用“有限次运算的过程”,1970,年证明不存在这样的判定算法,即这个问题是,不可判定的,或不可计算的,.,3,计算模型,从,20,世纪,30,年代先后提出,图灵机,A.M.Turing,1936,年,转换演算,A.Church,1935,年,递归函数,K.Gdel,1936,年,正规算法,A.A.Markov,1951,年,无限寄存器机器,J.C.Shepherdson,1963,年,4,Church-Turing,论题,已经证明这些模型都是等价的,即它们计算,的函数类,(,识别的语言类,),是相同的,.,Church-Turing,论题,:,直观可计算的函数类,就是图灵机以及任何与图灵机等价的计算模,型可计算,(,可定义,),的函数类,5,图灵机的基本模型,定义 图灵机,(TM),M,=,Q,q,0,B,A,其中,(1),状态集合,Q,:,非空有穷集合,;,(2),输入字母表,:,非空有穷集合,;,(3),带字母表,:,非空有穷集合且,;,(4),初始状态,q,0,Q,;,控制器,6,图灵机的基本模型,(,续,),(5),空白符,B,-,;,(6),接受状态集,A,Q,;,(7),动作函数,是,Q,到,L,R,Q,的部分函数,即,dom,Q,.,(,q,s,)=(,s,R,q,),的含义,:,当处于状态,q,读写头扫视,符号,s,时,M,的下一步把状态转移到,q,读写头把这,个,s,改写成,s,并向右移一格,;,(,q,s,)=(,s,L,q,),的含义类似,只是读写头向左移一,格,;,若,(,q,s,),没有定义,则,M,停机,.,7,一个,TM,M,的,实例,0 1,B,q,0,q,1,q,2,*q,3,(0,R,q,0,)(1,R,q,0,)(,B,L,q,1,),(,B,L,q,2,)(1,R,q,0,)(,B,R,q,0,),(,B,L,q,3,),例,1,8,格局,:,带的内容,当前的状态和读写头扫视的方格,=,q,其中,*,q,Q,初始格局,0,=,q,0,w,其中,w,*,是输入字符串,接受格局,=,q,:,q,A,停机格局,=,qs,:,(,q,s,),没有定义,1,2,:,从,1,经过一步能够到达,2,称,2,是,1,的,后继,1,2,:,从,1,经过若干步能够到达,2,图灵机的计算,9,图灵机的计算,(,续,),计算,:,一个有穷的或无穷的格局序列,序列中的每一个格局都是前一个格局的后继,.,w,*,M,从,0,=,q,0,w,开始的计算有,3,种可能,:,(1),停机在接受格局,即计算为,0,1,n,其中,n,是接受的停机格局,;,(2),停机在非接受格局,即计算为,0,1,n,其中,n,是非接受的停机格局,;,(3),永不停机,即计算为,0,1,n,10,图灵机接受的语言,定义,w,*,如果,M,从,0,=,q,0,w,开始的计算停机在,接受格局,则称,M,接受输入串,w,.,M,接受的语言,L,(,M,),是,M,接受的所有输入串,即,L,(,M,)=,w,*,|,M,接受,w,.,例,1(,续,),M,关于输入,w,=10100,的计算,:,q,0,10100,B,1,q,0,0100,B,10,q,0,100,B,101,q,0,00,B,1010,q,0,0,B,10100,q,0,B,1010,q,1,0,B,101,q,2,0,BB,101,Bq,3,BB,由于停机在接受格局,故,M,接受,10100.,L,(,M,)=,w,00|,w,0,1,*,11,图灵机,接受的语言,(,续,),定义,能被图灵机接受的语言称作,递归可枚举的,记作,r.e.,定理,语言,L,是,r.e.,当且仅当,L,是,0,型语言,.,图灵机与,0,型文法是等价的,12,用图灵机计算函数,上的,m,元部分字函数,:(,*,),m,的,某个子集到,*,的部分函数,TM,M,计算的,m,元部分字函数,f,:,设输入字母表为,x,1,x,m,*,如果,M,从初始格局,0,=,q,0,x,1,B,x,m,B,开始的计算停机,(,不管是否停机在接受状态,),从停机时带的内容中删去,以外的字符,得到字符串,y,则,f,(,x,1,x,2,x,m,)=,y,;,如果,M,从初始格局,0,开始的计算永不停机,则,f,(,x,1,x,2,x,m,),没有定义,记作,f,(,x,1,x,2,x,m,),.,例,1(,续,),M,计算函数,:,x,0,1,*,13,数论函数,数论函数,:,自然数集合,N,上的函数,N,上的,m,元部分函数,N,上的,m,元全函数,:,在,N,m,的每一点都有定义,例如,x+y,是全函数,x-y,是部分函数,当,xy,时,x-y,一进制表示,:,用,1,x,表示自然数,x,例如,111,表示,3,空串,表示,0,数论函数的一进制表示,:,字母表,1,上的字函数,用一进制表示自然数,例如,x+y,可表成,f,(1,x,1,y,)=1,x+y,14,递归函数,定义,设,f,是,N,上的,m,元部分函数,如果图灵机,M,计算,f,的一进制表示,即,M,的输入字母表为,1,x,1,x,m,N,从初始格局,0,=,开始,若,f,(,x,1,x,m,)=,y,则,M,的计算停机,且停机时带的内容,(,不计,1,以外的字符,),为,1,y,;,若,f,(,x,1,x,m,),则,M,永不停机,那么称,M,以一进制方式计算,f,.,定义,图灵机,M,以一进制方式计算的,N,上的,m,元部分函数称作,部分递归函数,或,部分可计算函数,;,部分递归的全函数称作,递归函数,或,可计算函数,.,15,递归函数,(,续,),例,1(,续,),M,以一进制方式计算,这是一个部分递归函数,.,