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

图灵机模型


第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)。图灵机是指一个抽象的...
大学计算机基础习题及答案
B.查尔斯·巴贝奇于 1834 年设计的分析机 C.冯·诺依曼和他的同事们研制的 EDVAC D.艾伦·图灵建立的图灵机模型 2.计算机科学的奠基人是___。 A.查尔斯·巴贝...
大学计算机基础习题及答案
图灵在计算机科学方面的主要贡献是建立图灵机模型和提出了微电子技术。 12. 第一款商用计算机是 1951 年开始生产的 UNIVAC 计算机。 三、参考答案(一)选择题 1.C...
认知心理学的图灵机模型
认知心理学的图灵机模型 - 1936 年,英国数学家 A. M. Turing 提出了一种简单机器的概念,这种机器后 被称为图灵机(Turing Machine)。这里的“机器”指的是一...
教材习题及答案
模型建立的前提下,利用计算机求解问题的核心工作就( 算法 3. 算法是一组规则...答:输入信息,输出信息、程序、内部状态 (1.1) 5.简述图灵机的工作过程。 答...
实验一实验报告
五、实验报告 实验名称:图灵机模型与计算机硬件系统虚拟拆装 学号 姓名: 班级: 实验时间: 2014 年 10 月 31 日 实验报告表 1-1 图灵机模型中的主要组成部分...
第4章 训练与练习(计算思维)
A.图灵机给出的是计算机的理论模型,是一种离散的、有穷的、构造性的问题求解思路 B.图灵机的状态转移函数,其实就是一条指令,即在 q 状态下,当 输入为 X 时...
实验一 实验报告表
实验一 实验报告表 实验名称: 学号: 姓名 班级实验时间实验报告表 1-1 图灵机模型中的主要组成部分及作用 主要组成部分名称 作用 无限长的纸带 读写头 控制规则...
大学计算机基础答案
A.ENIAC B.EDVAC C.MARK I D.UNIVAC 二、填充题 1.图灵在计算机科学方面的主要贡献是建立图灵机模型和提出了___ 。 2.最近的研究表明,电子计算机的雏形应该...
更多相关标签: