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