当前位置:首页 >> 经管营销 >>

图灵机模型


第1章 图灵机模型
图灵机模型理论是计算学科最核心的理 论之一 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计 的基础理论。

本章主要内容
图灵机概述 计算“X+1”的图灵机 通用图灵机 图灵机模型的启示

图灵机的直观描述
3个部件:有穷控制器、无穷带和读写头 3个动作:改写当前格、左移或右移一格
存储带 …… 读写头 ……

有穷控制器

图灵机模型

图灵机的形式化描述
图灵机是一个五元组(K,∑,δ,s,H), 其中: K 是有穷个状态的集合; ∑ 是字母表,即符号的集合; s ∈K是初始状态; 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)

通用图灵机(1)
编码方案:

通用图灵机(2)

通用图灵机蕴含的计算思想
程序也是数据
“x+1”图灵机功能是固定的,相当于一个 程序 通用的图灵机功能根据输入编码的不同而变 化

存储程序和程序控制
M图灵机进一步展示了程序和其输入可以先 保存到存储带上,M就按程序一步一步运行 直到给出结果,结果也保存在存储带上。

通用图灵机蕴含的计算思想
通用图灵机模型是计算机的计算能力的极限 计算机系统应该有:
存储器(相当于存储带) 中央处理器(控制器及其状态),并且其字母表 可以仅有0和1两个符号; 为了能将数据保存到存储器并将计算结果从存储 器送出来展示给用户,计算机系统还应该有输入 设备和输出设备如键盘、鼠标、显示器和打印机 等。


赞助商链接
相关文章:
北理大学计算机实验基础 实验一_图灵机模型与计算机硬...
北理大学计算机实验基础 实验一_图灵机模型与计算机硬件系统虚拟拆装-实验报告_互联网_IT/计算机_专业资料。实验一 图灵机模型与计算机硬件系统虚拟拆装五、实验报告 ...
图灵机简介和原理分析
图灵机简介和原理分析 - 图灵机简介和原理分析 摘要: 1936 年, 阿兰·图灵提出了一种抽象的计算模型 ——图 灵机 (Turing Machine)。图灵机是指一个抽象的...
教材习题及答案
4.图灵机模型中的四个要素是什么? 答:输入信息,输出信息、程序、内部状态 (1.1) 5.简述图灵机的工作过程。 答:请参见教材 6.简述问题求解的一般过程。 答...
大学计算机基础习题及答案
B.查尔斯·巴贝奇于 1834 年设计的分析机 C.冯·诺依曼和他的同事们研制的 EDVAC D.艾伦·图灵建立的图灵机模型 2.计算机科学的奠基人是___。 A.查尔斯·巴贝...
第4章 训练与练习(计算思维)
A.图灵机给出的是计算机的理论模型,是一种离散的、有穷的、构造性的问题求解思路 B.图灵机的状态转移函数,其实就是一条指令,即在 q 状态下,当 输入为 X 时...
大学计算机基础习题及答案
10. 微型计算机的种类很多,主要分成台式机、笔记本电脑和 个人数字助理(PDA) 11. 图灵在计算机科学方面的主要贡献是建立图灵机模型和提出了微电子技术。 12. 第...
实验一实验报告
五、实验报告 实验名称:图灵机模型与计算机硬件系统虚拟拆装 学号 姓名: 班级: 实验时间: 2014 年 10 月 31 日 实验报告表 1-1 图灵机模型中的主要组成部分...
大​学​计​算​机​基​础​答​案
图灵建立的图灵机模型 2.计算机科学的奠基人是___。 A.查尔斯?巴贝奇 B.图灵 C.阿塔诺索夫 D.冯,诺依曼 3.物理器件采用晶体管的计算机被称为___。 A.第一...
实验一 实验报告表
实验一 实验报告表 实验名称: 学号: 姓名 班级实验时间实验报告表 1-1 图灵机模型中的主要组成部分及作用 主要组成部分名称 作用 无限长的纸带 读写头 控制规则...
计算机12
A.CAD 二、填充题 1.图灵在计算机科学方面的主要贡献是建立图灵机模型和提出了___ 2.以“存储程序”的概念为基础的各类计算机统称为___。 3.第一款商用计算机...
更多相关标签: