计算机导论 教学课件 作者 祁亨年 主编 汪杭军 高志刚 副主编第1章 图灵机模型.ppt

《计算机导论 教学课件 作者 祁亨年 主编 汪杭军 高志刚 副主编第1章 图灵机模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章图灵机模型图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论。本章主要内容图灵机概述计算“X+1”的图灵机通用图灵机图灵机模型的启示图灵机的直观描述3个部件：有穷控制器、无穷带和读写头3个动作：改写当前格、左移或右移一格读写头有穷控制器存储带…………图灵机模型图灵机的形式化描述图灵机是一个五元组（K，∑，δ，s，H），其中：K是有穷个状态的集合；∑是字母表，即符号的集合；s∈K是初始状态；H∈K是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；δ是转移函

2、数，即控制器的规则集合。计算“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+

3、1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入编码的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上。通用图灵机蕴含的计算思想通用图灵机模型是计算机的计算能力的极限计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。