离散数学配套课件PPT(第5版)第六部分-形式语言与自动机图灵机

110.4图灵机图灵机的基本模型图灵机接受的语言——递归可枚举语言用图灵机计算函数——部分可计算函数与可计算函数2问题的提出1900年D.Hilbert在巴黎第二届数学家大会上提出著名的23个问题.第10个问题:如何判定整系数多项式是否有整数根?要求使用“有限次运算的过程”1970年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.3计算模型从20世纪30年代先后提出图灵机A.M.Turing,1936年转换演算A.Church,1935年递归函数K.Gödel,1936年正规算法A.A.Markov,1951年无限寄存器机器J.C.Shepherdson,1963年…4Church-Turing论题已经证明这些模型都是等价的,即它们计算的函数类(识别的语言类)是相同的.Church-Turing论题:直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模型可计算(可定义)的函数类5图灵机的基本模型定义图灵机(TM)M=Q,,,,q0,B,A,其中(1)状态集合Q:非空有穷集合;(2)输入字母表:非空有穷集合;(3)带字母表:非空有穷集合且;(4)初始状态q0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一个TMM的实例01B→q0q1q2*q3(0,R,q0)(1,R,q0)(B,L,q1)(B,L,q2)(1,R,q0)(B,R,q0)(B,L,q3)—————例18格局:带的内容,当前的状态和读写头扫视的方格=q,其中,Γ*,qQ初始格局0=q0w,其中wΣ*是输入字符串接受格局=q:qA停机格局=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|w{0,1}*}11图灵机接受的语言(续)定义能被图灵机接受的语言称作递归可枚举的,记作r.e.定理语言L是r.e.当且仅当L是0型语言.图灵机与0型文法是等价的12用图灵机计算函数上的m元部分字函数:(*)m的某个子集到*的部分函数TMM计算的m元部分字函数f:设输入字母表为,x1,…,xm*,如果M从初始格局0=q0x1B…xmB开始的计算停机(不管是否停机在接受状态),从停机时带的内容中删去Σ以外的字符,得到字符串y,则f(x1,x2,…,xm)=y;如果M从初始格局0开始的计算永不停机,则f(x1,x2,…,xm)没有定义,记作f(x1,x2,…,xm).否则若若,10,100,)(wxwwxwxf例1(续)M计算函数:x{0,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+y14递归函数定义设f是N上的m元部分函数,如果图灵机M计算f的一进制表示,即M的输入字母表为{1},x1,…,xmN,从初始格局0=开始,若f(x1,…,xm)=y,则M的计算停机,且停机时带的内容(不计{1}以外的字符)为1y;若f(x1,…,xm),则M永不停机,那么称M以一进制方式计算f.定义图灵机M以一进制方式计算的N上的m元部分函数称作部分递归函数,或部分可计算函数;部分递归的全函数称作递归函数,或可计算函数.BBBqmxxx11121015递归函数(续)例1(续)M以一进制方式计算否则整除但不被整除被若整除被若,4,2,2/4,4/)(xxxxxf这是一个部分递归函数.