离散数学-屈婉玲(形式语言与自动机).ppt

1,11.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,q0,B,A,其中(1)状态集合Q:非空有穷集合;(2)输入字母表:非空有穷集合;(3)带字母表:非空有穷集合且;(4)初始状态 q0Q;,控制器,6,图灵机的基本模型(续),(5)空白符B-;(6)接受状态集AQ;(7)动作函数是Q到L,RQ的部分函数,即dom Q.(q,s)=(s,R,q)的含义:当处于状态q,读写头扫视符号s时,M的下一步把状态转移到q,读写头把这个s改写成s,并向右移一格;(q,s)=(s,L,q)的含义类似,只是读写头向左移一格;若(q,s)没有定义,则M停机.,7,一个TM M的实例（例1）,8,格局:带的内容,当前的状态和读写头扫视的方格=q,其中,*,qQ初始格局0=q0w,其中w*是输入字符串接受格局=q:qA停机格局=qs:(q,s)没有定义1 2:从1经过一步能够到达2,称2是1的后继 1 2:从1经过若干步能够到达 2,图灵机的计算,9,图灵机的计算(续),计算:一个有穷的或无穷的格局序列,序列中的每一个格局都是前一个格局的后继.w*,M从0=q0w开始的计算有3种可能:(1)停机在接受格局,即计算为0,1,n,其中n是接受的停机格局;(2)停机在非接受格局,即计算为0,1,n,其中n是非接受的停机格局;(3)永不停机,即计算为0,1,n,10,图灵机接受的语言,定义 w*,如果M从0=q0w开始的计算停机在接受格局,则称M接受输入串w.M接受的语言L(M)是M接受的所有输入串,即L(M)=w*|M接受w.例1(续)M关于输入w=10100的计算:q010100B 1q00100B 10q0100B 101q000B 1010q00B 10100q0B 1010q10B 101q20BB 101Bq3BB由于停机在接受格局,故M接受10100.L(M)=w00|w0,1*,11,图灵机接受的语言(续),定义 能被图灵机接受的语言称作递归可枚举的,记作r.e.定理 语言L是r.e.当且仅当 L是 0 型语言.图灵机与 0 型文法是等价的,12,用图灵机计算函数,上的m元部分字函数:(*)m的某个子集到*的部分函数TM M计算的m元部分字函数f:设输入字母表为,x1,xm*,如果M从初始格局0=q0 x1B xmB开始的计算停机(不管是否停机在接受状态),从停机时带的内容中删去以外的字符,得到字符串y,则 f(x1,x2,xm)=y;如果M从初始格局0开始的计算永不停机,则f(x1,x2,xm)没有定义,记作 f(x1,x2,xm).,例1(续)M计算函数:x0,1*,13,数论函数,数论函数:自然数集合N上的函数N上的m元部分函数N上的m元全函数:在Nm的每一点都有定义 例如 x+y是全函数,x-y是部分函数,当xy时,x-y一进制表示:用1x表示自然数x 例如 111表示3,空串表示0数论函数的一进制表示:字母表1上的字函数,用一进制表示自然数 例如 x+y 可表成 f(1x,1y)=1x+y,14,递归函数,定义 设f 是N上的m元部分函数,如果图灵机M计算f 的一进制表示,即M的输入字母表为1,x1,xmN,从初始格局 0=开始,若f(x1,xm)=y,则M的计算停机,且停机时带的内容(不计1以外的字符)为1y;若f(x1,xm),则M永不停机,那么称M以一进制方式计算f.定义 图灵机M以一进制方式计算的N上的m元部分函数称作部分递归函数,或部分可计算函数;部分递归的全函数称作递归函数,或可计算函数.,15,递归函数(续),例1(续)M以一进制方式计算,这是一个部分递归函数.,