114图灵机 ■图灵机的基本模型 ■图灵机接受的语言 递归可枚举语言 用图灵机计算函数 部分可计算函数与可计算函数
1 11.4 图灵机 ◼ 图灵机的基本模型 ◼ 图灵机接受的语言 ——递归可枚举语言 ◼ 用图灵机计算函数 ——部分可计算函数与可计算函数
问题的提出 1900年D. Hilbert在巴黎第二届数学家大会上提出 著名的23个问题 第10个问题如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970年证明不存在这样的判定算法,即这个问题是 不可判定的,或不可计算的
2 问题的提出 1900年 D. Hilbert 在巴黎第二届数学家大会上提出 著名的23个问题. 第10个问题:如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的
计算模型 从20世纪30年代先后提出 图灵机 A M.Turing,1936年 λ转换演算 A Church,1935年 递归函数KG6del,1936年 正规算法A.A. Markov,1951年 无限寄存器机器 J.C. Shepherdson,1963年
3 计算模型 从20世纪30年代先后提出 图灵机 A.M.Turing, 1936年 λ转换演算 A.Church, 1935年 递归函数 K.Gödel, 1936年 正规算法 A.A.Markov, 1951年 无限寄存器机器 J.C.Shepherdson, 1963年 …
Church- Turing论题 已经证明这些模型都是等价的,即它们计算 的函数类(识别的语言类)是相同的 Church- Turing论题:直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算(可定义)的函数类
4 Church-Turing论题 已经证明这些模型都是等价的, 即它们计算 的函数类 (识别的语言类) 是相同的. Church-Turing论题: 直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算 (可定义) 的函数类
图灵机的基本模型 ……Ba1a2……an1anB 。。。。 控制器 定义图灵机(TM)M=(Q,,6,q0,B,A),其中 (1)状态集合Q:非空有穷集合; (2)输入字母表∑:非空有穷集合; (3)带字母表/:非空有穷集合且Xc厂; (4)初始状态q∈Q;
5 图灵机的基本模型 定义 图灵机(TM) M=Q,Σ,Γ,δ,q0 ,B,A , 其中 (1) 状态集合Q: 非空有穷集合; (2) 输入字母表Σ: 非空有穷集合; (3) 带字母表Γ: 非空有穷集合且ΣΓ; (4) 初始状态 q0Q; 控制器
图灵机的基本模型(续) (5)空白符B∈x; (6)接受状态集AcQ; (7)动作函数是Q×/到Ⅳ{,R}XQ的部分函数, 即 dondo×∑ 6(q1,)=(sR,q)的含义:当处于状态q读写头扫视 符号s时,M的下一步把状态转移到q,读写头把这 个改写成s,并向右移一格; 6(q1,s)=(s,L,q)的含义类似,只是读写头向左移一 格;若δ(q,s)没有定义,则M停机
6 图灵机的基本模型(续) (5) 空白符BΓ-Σ; (6) 接受状态集AQ; (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停机
个TMM的实例(例1) 01 B →0(0,R0)(1,R40)(B,L,) (B,L,q2)(1,R,q0)(B,R,q0) 42(B,L,q3) q 1/1,R 0/0,R 0/B,A0/B,R q L B/B,q q 1/1,R B/B R
7 一个TM M的实例（例1） δ 0 1 B →q0 q1 q2 *q3 (0,R,q0 ) (1,R,q0 ) (B,L,q1 ) (B,L,q2 ) (1,R,q0 ) (B,R,q0 ) (B,L,q3 ) — — — — —
图灵机的计算 格局:带的内容,当前的状态和读写头扫视的方格 σ=aq,其中a,B∈r,q∈Q 初始格局σo=q0w,其中ν∈Σ是输入字符串 接受格局σ=aqB:q∈A 停机格局σ=qsβ:冽(q,s没有定义 1}σ2:从σ1经过一步能够到达a2,称a2是a1的后继 G1a2:从σ经过若干步能够到达2
8 格局: 带的内容, 当前的状态和读写头扫视的方格 σ = αqβ, 其中 α,βΓ* , qQ 初始格局σ0= q0w, 其中wΣ*是输入字符串 接受格局σ = αqβ : qA 停机格局σ = αqsβ : δ(q,s)没有定义 σ1 ⊢ σ2 : 从σ1经过一步能够到达σ2 , 称σ2是σ1的后继 σ1 σ2 : 从σ1经过若干步能够到达σ2 图灵机的计算
图灵机的计算(续) 计算:一个有穷的或无穷的格局序列,序列中的每 个格局都是前一个格局的后继. vw∈∑,M从σ=qv开始的计算有3种可能: (1)停机在接受格局,即计算为o0,01,…,σm,其中σn是 接受的停机格局; (2)停机在非接受格局,即计算为σ0,G1,…,n,其中σn 是非接受的停机格局 (3)永不停机,即计算为0,01,…,0n…
9 图灵机的计算(续) 计算: 一个有穷的或无穷的格局序列, 序列中的每一 个格局都是前一个格局的后继. wΣ* , M从σ0= q0w开始的计算有3种可能: (1) 停机在接受格局, 即计算为σ0 ,σ1 , … ,σn , 其中σn是 接受的停机格局; (2) 停机在非接受格局, 即计算为σ0 ,σ1 , … ,σn , 其中σn 是非接受的停机格局; (3) 永不停机, 即计算为σ0 ,σ1 , … ,σn , …
图灵机接受的语言 定义Vw∈∑,如果M从G=q开始的计算停机在 接受格局,则称M接受输入串w.M接受的语言LMD 是M接受的所有输入串,即LMO={w∈x|M接受w 例1(续)M关于输入w=10100的计算: q10100B}1q0100B}10g0100B}101q00B}1010g0B F101000BF1010g10BF101q20BB}101Bg3BB 由于停机在接受格局,故M接受10100 L(MO={v0|w∈{0,41}"} 10
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}* }