turing machine 图灵机.pptVIP

Outline 图灵机的意义 图灵机概述 图灵机的基本思想 图灵机的组成 图灵机的计算思想 图灵机的意义 图灵机模型理论是计算科学最核心的理论之一 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计的基础理论 图灵机概述 所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。 图灵机的基本思想 用机器来模拟人们用纸笔进行数学运算的过程，该过程可分为如下两个简单动作： 在纸上写上或擦除某个符号 把注意力从纸的一个位置移动到另一个位置 而在每个阶段，人要决定下一步的动作，依赖于： 此人当前所关注的纸上某个位置的符号 此人当前思维的状态。 … －2 －1 0 1 2 3 … 状态控制器 读写头 图灵机的组成 一个确定型单带图灵机由以下四个部分组成(见上页图)： ·无限长的带子 TAPE，带子划成小格， 格子标记 … , －3，－2，－1，0，1，2, 3，… ·读写头HEAD ·控制规则表TABLE ·状态存储器 图灵机的组成-TAPE 纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。 图灵机的组成-HEAD 读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。 等效于人脑当前所关注的纸上某个位置的符号 图灵机的组成-TABLE 控制规则表可以根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。等效于人脑的知识。 图灵机的组成-状态存储器 保存图灵机当前所处的状态。等效于人脑当前思维的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 图灵机计算思想 程序也是数据 图灵机的功能根据输入编码的不同而变化 存储程序和程序控制：图灵机可以将程序先保存到存储带上，图灵机按照程序一步一步运行直到给出结果，结果也保存到存储带上。 图灵机计算思想 计算机系统应该有： 存储器（相当于存储带） 中央处理器（控制器及其状态） 为了能够将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。 谢谢！