文档介绍：第1章图灵机模型及数据编码
图灵机模型理论是计算学科最核心的理论之一
图灵机模型为计算机设计指明了方向
图灵机模型是算法分析和程序语言设计的基础理论。
本章主要内容
图灵机
位的存储
存储器
数据在计算机中的表示
数据压缩
数据传输误码及对策
图灵机的直观描述
3个部件:有穷控制器、无穷带和读写头
3个动作:改写当前格、左移或右移一格
读写头
有穷控制器
存储带
……
……
图灵机模型
图灵机的形式化描述
图灵机是一个五元组(K,∑,δ,s,H),其中:
K 是有穷个状态的集合;
∑是字母表,即符号的集合;
s ∈K是初始状态;
H∈K 是停机状态的集合,当控制器内部状态为停机状态时图灵机结束计算;
δ是转移函数,即控制器的规则集合。
计算“x+1”的图灵机
目标:利用二进制来设计一个专门计算“x+1”的图灵机,要求计算完成时,读写头要回归原位
状态集合K:{start,add,carry,noncarry,overflow,return,halt};
字母表∑:{0,1,*};
初始状态s:start;
停机状态集合H:{halt};
计算“x+1”的图灵机
规则集合δ:
“5+1”的计算过程(1)
“5+1”的计算过程(2)
“5+1”的计算过程(3)
“5+1”的计算过程(4)