图灵机(PPT).ppt

1
第4章图灵机
2
Overview
图灵机(Turing Machine,TM),是计算机的一种简单的数学模型。
历史上,冯•诺曼计算机的产生就是由图灵机诱发的。
丘奇—图灵论题:一切合理的计算模型都等同于图灵机.
3
类型文法结构产生式形式限制条件
0 短语结构文法α→βα∈V+,β∈V*
Phrase Structure
上下文有关文法α1Aα2→α1βα2 |α1βα2|≥|α1Aα2|
1 Context Sensitive α1,α2∈V*
(CSG ) A∈VN , β∈V+
上下文无关文法 A→α A∈VN,α∈V*
2 Context Free
(CFG)
正右线性文法 A→xB,C→y A,B,C∈VN
3 规
文左线性文法 A→Bx,C→y x,y∈VT*
法
4
Overview
0型语言———图灵机
1型语言(CSL) ———线性界限自动机
2型语言(CFL) ———下推自动机
3型语言(正规集)——有限自动机
5
Overview
图灵机所定义的语言类---递归可枚举集合
图灵机所计算的整数函数类---部分递归函数
以图灵机为模型,研究问题的可计算性,即确定该问题是可计算的、部分可计算的,还是不可计算的。
6
Overview
图灵机模型
图灵机的变化和组合
通用图灵机
图灵机可计算性
7
图灵机模型
8
图灵机模型
定义4-1 图灵机M = ( K, Σ, Γ, δ, q0, B,F),
其中
K是有穷的状态集合;
Γ是所允许的带符号集合;
B ∈Γ,是空白符;
ΣΓ,B ∈Σ,是输入字符集合;
F  K,是终止状态集合。
q0∈K, 是初始状态;
9
图灵机模型
δ:K×ΓK×Γ×{L,R,S}
是图灵机的动作(状态转移)函数,这里
L表示读头左移一格;
R表示读头右移一格;
S表示读头不动;

δ(q,a)=(p,b,z)
表示状态q下读头所读符号为a时,状态转移为p,读头符号变为b,同时读头变化为z.
10
图灵机模型
定义4-2 设当前带上字符串为x1x2 … xn,当前状态为q,读头正在读xi ,图灵机的瞬时描述ID 为
x1x2 … xi-1 q xi … xn