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

'10.4图灵机图灵机的基本模型图灵机接受的语言——递归可枚举语言用图灵机计算函数——部分可计算函数与可计算函数1 问题的提出1900年D.Hilbert在巴黎第二届数学家大会上提出著名的23个问题.第10个问题:如何判定整系数多项式是否有整数根?要求使用“有限次运算的过程”1970年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.2 计算模型从20世纪30年代先后提出图灵机A.M.Turing,1936年转换演算A.Church,1935年递归函数K.Gödel,1936年正规算法A.A.Markov,1951年无限寄存器机器J.C.Shepherdson,1963年…3 Church-Turing论题已经证明这些模型都是等价的,即它们计算的函数类(识别的语言类)是相同的.Church-Turing论题:直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模型可计算(可定义)的函数类4 图灵机的基本模型定义图灵机(TM)M=Q,,,,q0,B,A,其中(1)状态集合Q:非空有穷集合;(2)输入字母表:非空有穷集合;(3)带字母表:非空有穷集合且;(4)初始状态q0Q;控制器5 图灵机的基本模型(续)(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停机.6 一个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)—————例17 格局:带的内容,当前的状态和读写头扫视的方格=q,其中,Γ*,qQ初始格局0=q0w,其中wΣ*是输入字符串接受格局=q:qA停机格局=qs:δ(q,s)没有定义1⊢2:从1经过一步能够到达2,称2是1的后继12:从1经过若干步能够到达2图灵机的计算8 图灵机的计算(续)计算:一个有穷的或无穷的格局序列,序列中的每一个格局都是前一个格局的后继.w*,M从0=q0w开始的计算有3种可能:(1)停机在接受格局,即计算为0,1,…,n,其中n是接受的停机格局;(2)停机在非接受格局,即计算为0,1,…,n,其中n是非接受的停机格局;(3)永不停机,即计算为0,1,…,n,…9 图灵机接受的语言定义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}*}10 图灵机接受的语言(续)定义能被图灵机接受的语言称作递归可枚举的,记作r.e.定理语言L是r.e.当且仅当L是0型语言.图灵机与0型文法是等价的11 用图灵机计算函数上的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).例1(续)M计算函数:x{0,1}*,12 数论函数数论函数:自然数集合N上的函数N上的m元部分函数N上的m元全函数:在Nm的每一点都有定义例如x+y是全函数,x-y是部分函数,当x