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

1、111.4 图灵机图灵机n图灵机的基本模型图灵机的基本模型n图灵机接受的语言图灵机接受的语言 递归可枚举语言递归可枚举语言n用图灵机计算函数用图灵机计算函数 部分可计算函数与可计算函数部分可计算函数与可计算函数 2问题的提出问题的提出1900年年 D. Hilbert 在巴黎第二届数学家大会上提出在巴黎第二届数学家大会上提出著名的著名的23个问题个问题.第第10个问题个问题:如何判定整系数多项式是否有整数根如何判定整系数多项式是否有整数根? 要求使用要求使用“有限次运算的过程有限次运算的过程”1970 年证明不存在这样的判定算法年证明不存在这样的判定算法, 即这个问题是即这个问题是不可判定的不

2、可判定的, 或不可计算的或不可计算的.3计算模型计算模型从从20世纪世纪30年代先后提出年代先后提出图灵机图灵机 A.M.Turing, 1936年年转换演算转换演算 A.Church, 1935年年递归函数递归函数 K.Gdel, 1936年年正规算法正规算法 A.A.Markov, 1951年年无限寄存器机器无限寄存器机器 J.C.Shepherdson, 1963年年 4Church-Turing论题论题已经证明这些模型都是等价的已经证明这些模型都是等价的, 即它们计算即它们计算的函数类的函数类 (识别的语言类识别的语言类) 是相同的是相同的.Church-Turing论题论题: 直观可

3、计算的函数类直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模就是图灵机以及任何与图灵机等价的计算模型可计算型可计算 (可定义可定义) 的函数类的函数类5图灵机的基本模型图灵机的基本模型定义定义 图灵机图灵机(TM) M= Q,q0,B,A , 其中其中 (1) 状态集合状态集合Q: 非空有穷集合非空有穷集合; (2) 输入字母表输入字母表: 非空有穷集合非空有穷集合; (3) 带字母表带字母表: 非空有穷集合且非空有穷集合且 ; (4) 初始状态初始状态 q0 Q;控制器控制器6图灵机的基本模型图灵机的基本模型(续续) (5) 空白符空白符B -; (6) 接受状态集接受状态集A Q;

4、 (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的的实例实例（例（例1） 0 1 B q0 q1 q2*q3 (0,R,q0) (1,R,q0) (B,L,

5、q1) (B,L,q2) (1,R,q0) (B,R,q0) (B,L,q3) 8格局格局: 带的内容带的内容, 当前的状态和读写头扫视的方格当前的状态和读写头扫视的方格 = q, 其中其中 , *, q Q初始格局初始格局0= q0w, 其中其中w *是输入字符串是输入字符串接受格局接受格局 = q : q A停机格局停机格局 = qs : (q,s)没有定义没有定义1 2: 从从1经过一步能够到达经过一步能够到达2, 称称2是是1的的后继后继 1 2: 从从1经过若干步能够到达经过若干步能够到达 2图灵机的计算图灵机的计算9图灵机的计算图灵机的计算(续续)计算计算: 一个有穷的或无穷的格局

6、序列一个有穷的或无穷的格局序列, 序列中的每一序列中的每一个格局都是前一个格局的后继个格局都是前一个格局的后继. w *, M从从0= q0w开始的计算有开始的计算有3种可能种可能:(1) 停机在接受格局停机在接受格局, 即计算为即计算为0,1, ,n, 其中其中n是是接受的停机格局接受的停机格局;(2) 停机在非接受格局停机在非接受格局, 即计算为即计算为0,1, ,n, 其中其中n是非接受的停机格局是非接受的停机格局;(3) 永不停机永不停机, 即计算为即计算为0,1, ,n, 10图灵机接受的语言图灵机接受的语言定义定义 w *, 如果如果M从从0= q0w开始的计算停机在开始的计算停机

7、在接受格局接受格局, 则称则称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图灵机图灵机接受的语言接受的语言(续续)定义定义 能被图灵机接受的语言称作能被图灵机接受的语言称作

8、递归可枚举的递归可枚举的, 记作记作r.e.定理定理 语言语言L是是r.e.当且仅当当且仅当 L是是 0 型语言型语言. 图灵机与图灵机与 0 型文法是等价的型文法是等价的12用图灵机计算函数用图灵机计算函数上的上的m元部分字函数元部分字函数: (*)m的的某个子集到某个子集到*的部分函数的部分函数TM M计算的计算的m元部分字函数元部分字函数f : 设输入字母表为设输入字母表为, x1,xm *, 如果如果M从初始格局从初始格局0= q0 x1B xmB开始的计开始的计算停机算停机(不管是否停机在接受状态不管是否停机在接受状态), 从停机时带的内容中删从停机时带的内容中删去去以外的字符以外的

9、字符, 得到字符串得到字符串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时时

10、, 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元部分函元部分函数称作数称作部分递归函数部分递归函数, 或或部分可计算函数部分可计算函数; 部分递