计算模型主要内容图灵机模型.pptx

第二章 计算模型
计算模型主要内容图灵机模型
主要内容
图灵机模型
RAM机
RASP机
Lambda演算模型
计算模型主要内容图灵机模型
图灵机模型
图灵机组成：
线性带（读写介质）
基本符号表（表示信息）
信息处理状态
信息处理动作（静止，左、右移）
信息处理方法（规则，即程序）
计算模型主要内容图灵机模型
状态控制器
q0
q5
q4
q3
q1
q2
读写头
线性带
计算模型主要内容图灵机模型
定义：图灵机的M＝(Q, ∑, , δ, B, q0, F)，其中：
Q 为状态的有限集合；
∑为有限字母表，为输入符号集；
为线性带符号集，∑ ；
B空符号，B，B ∑；
q0Q为初始状态
FQ是终止状态集;
：Q× Q×(×{L, R, S})为转移函数。
计算模型主要内容图灵机模型
例1：δ(q, a) = (p, (b, L))
说明：若当前状态为q，读写头读取a，经过δ动作后，图灵机状态改为p，线性带上a改变为b，同时读写头左移一格。
 
例2：δ(q, a) = (p, (a, R))
说明：若当前状态为q，读写头读取a，经过δ动作后，图灵机状态改为p，线性带上a不改变，同时读写头右移一格。
计算模型主要内容图灵机模型
例3：δ(q, a) = (q, (B, S))
说明：当前状态为q，读写头读取a，经过δ动作后，图灵机状态不改变，仍为q，线性带上a被清空为null，同时读写头不动。
计算模型主要内容图灵机模型
例4：有图灵机M定义如下：
M=({q0,q1,q2}, {0,1}, {0,1,B}, δ, q0, B, {q2}),其中δ定义为：
δ(q0, 0) = (q0, 0, R),
δ(q0, 1) = (q1, 1, R),
δ(q1, 0) = (q1, 0, R),
δ(q1, B) = (q2, B, R).
计算模型主要内容图灵机模型
表示：
图
表
计算模型主要内容图灵机模型
q0
q1
q2
0（0,R）
1（1,R）
0（0,R）
B（B,R）
计算模型主要内容图灵机模型