图灵机计算机的理论模型.ppt

图灵的贡献主要有两个：一是建立了图灵机，二是提出了图灵测试、阐述了机器智能的概念。图灵机的概念是现代可计算理论的基础。图灵证明，只有图灵机能解决的计算问题，实际计算机才能解决。 为纪念图灵对计算机科学的贡献，美国计算机协会（ACM）于1966年创立了图灵奖，每年奖给在计算机科学领域中作出贡献的研究人员。被誉为计算机业界和科学界的诺贝尔将。 图灵机就是一个最简单的计算机模型，图灵机将控制处理的规则用0 和1表述，将处理的信息及处理的结果也用0和1表达，处理即是对0和1的变换（可以用机械/电子系统实现）。 图灵与图灵机模型 英国科学家阿兰.图灵 （1912-1954） 图灵是现代计算机理论模型的提出者。 图灵的贡献主要有两个： 建立了图灵机模型 提出了图灵测试、阐述了机器智能的概念。 图灵证明，只有图灵机能解决的计算问题，实际计算机才能解决。 “图灵奖”是美国计算机协会于1966年设立的。 图灵机由一条无限长的纸带、读/写头及控制器构成。 什么是图灵机？ 控制器内包括控制规则表，它能够通过读/写头对纸带上的符号进行读或写，读写头可以在纸带上左右移动。 纸带分成了一个个的小方格，每个方格中可以记录机器字母表里的符号，如0或1等。 图灵机模型 机器的程序是五元组｛Si , X , Y , L(R或N) , Sj｝形式的指令集，定义了机器在一个特定状态下读入一个特定字符时所采取的动作。 五个元素的含义如下： ①Si 表示机器当前的状态； ②X 表示机器从方格中读入的内容，也即当前内容； ③Y 表示机器用来代替X 写入方格中的内容； ④L、R、N 分别表示左移一格、右移一格和不移动； ⑤Sj 表示机器下一步的状态。 图灵机——计算机的理论模型 图灵机——计算机的理论模型 图灵机磁带 图灵机的计算开始于初始状态，设为S0，终止于停止（HALT）状态，设为SH。 例: 设计能够实现“a+1”运算的图灵机，计算完成后要求读写头回到原位。 设a 为十进制数11 机器状态=S0 当前位置 输入 输出 当前状态 （Si） 当前内容 （X） 重写的新内容 （Y） 读写头移动方向 （L，R或N） 进入的新状态 （Sj） S0 b b L S1 S1 0 1 R S3 S1 1 0 L S2 S1 b b R SH S2 0 1 R S3 S2 1 0 L S2 S2 b 1 L S4 S3 0 0 R S3 S3 1 1 R S3 S3 b b N SH S4 任意 b R S3 图灵机进行“a+1”运算的控制规则表 图灵机计算思想 图灵机的功能根据输入编码的不同而变化 程序和数据同等看待 图灵机可以将程序先保存到存储带上，按照程序一步一步运行直到给出结果，结果也保存到存储带上。 图灵机不是一种具体的机器，而是一种理论模型，可用来指导制造一种十分简单但运算能力极强的计算装置，使得这种机器能够对任何“可计算”的函数进行有效的计算，在有限步内求出函数的计算结果。 图灵机模型理论是计算学科最核心的理论之一，图灵机模型是算法分析和程序语言设计的基础，为计算机设计指明了方向。 图灵的贡献主要有两个：一是建立了图灵机，二是提出了图灵测试、阐述了机器智能的概念。图灵机的概念是现代可计算理论的基础。图灵证明，只有图灵机能解决的计算问题，实际计算机才能解决。 为纪念图灵对计算机科学的贡献，美国计算机协会（ACM）于1966年创立了图灵奖，每年奖给在计算机科学领域中作出贡献的研究人员。被誉为计算机业界和科学界的诺贝尔将。 图灵机就是一个最简单的计算机模型，图灵机将控制处理的规则用0 和1表述，将处理的信息及处理的结果也用0和1表达，处理即是对0和1的变换（可以用机械/电子系统实现）。