图灵机的思想与模型简介课件.ppt

图灵机的思想与模型简介图灵机的思想与模型简介----图灵的贡献图灵的贡献----图灵机：计算机的理论模型图灵机：计算机的理论模型----指令、数据、程序与程序执行指令、数据、程序与程序执行冯冯.诺依曼计算机：机器级程序及其执行诺依曼计算机：机器级程序及其执行2.2.1 图灵机的思想与模型简介图灵机的思想与模型简介图灵机的思想与模型简介图灵及其贡献u图灵图灵(Alan Turing, 1912~1954)，出生于英国伦敦，19 岁入剑桥皇家学院，22 岁当选为皇家学会会员u1937 年，发表了论文《论可计算数及其在判定问题中的应用》，提出了图灵机模型图灵机模型，后来，冯·诺依曼根据这个模型设计出历史上第一台电子计算机u1950 年，发表了划时代的文章：《机器能思考吗?》,成为了人工智能的开山之作u计算机界于1966年设立了最高荣誉奖：ACM 图灵奖图灵奖图灵是谁图灵是谁?你能查阅一下哪些人获得图灵奖了吗？你能查阅一下哪些人获得图灵奖了吗？因为什么贡献而获奖呢？因为什么贡献而获奖呢？图灵机的思想与模型简介u所谓计算计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的变换过程变换过程。

计算…1000111011010001…由“程序”控制，一步步将输入“转换”为输出输入输出程序通用机器通用机器图灵认为什么是计算图灵认为什么是计算?图灵机的思想与模型简介图灵机的思想图灵机的思想是关于数据、指令、程序及程序是关于数据、指令、程序及程序/指令自动执行的基本思想指令自动执行的基本思想u 输入被制成一串0和1的纸带，送入机器中----数据数据如011…u 机器可对输入纸带执行的基本动作基本动作包括：“翻转0为1”，或 “翻转1为0”, “前移一位”, “停止”u 对基本动作的控制----指令指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变), 11表示“前移一位”, 00表示“停止”u 输入如何变为输出的控制可以用指令编写一个程序程序来完成, 如: 011110110111011100…u 机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行执行一条指令由此实现自动计算自动计算图灵机的思想与模型简介u 基本的图灵机模型图灵机模型为一个七元组,如右图示意u 几点结论几点结论:u(1) 图灵机是一种思想模型，它由一个控制器(有限状态转换器)，一条可无限延伸的带子和一个在带子上左右移动的读写头构成。

u(2) 程序是五元组程序是五元组形式形式的指令集的指令集其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方格中写入符号Y, 然后向右移一格R (或向左移一格L或不移动N), 同时将机器状态设为p供下一条指令使用图灵机是什么图灵机是什么?图灵机模型图灵机模型图灵机的思想与模型简介图灵机模型示例图灵机模型示例 (注:圆圈内的是状态，箭线上的是，其含义见前页)执行过程功能：将一串功能：将一串1的后面再加一位的后面再加一位10 0 1 1 1 1 0 0 0控制器控制器(S1,0,0,R,S1)(S1,1,1,R,S2)(S2,1,1,R,S2)(S2,0,1,L,S3)(S3,1,1,L,S3)(S3,0,0,N,S4)S1S2S3S41,1,R1,1,R0,1,L1,1,L0,0,NS1：开始状态S2：右移状态S3：左移状态S4：停机状态0,0,R0 0 1 1 1 1 0 0 00 0 1 1 1 1 0 0 0(S1,0,0,R,S1)(S1,1,1,R,S2)0 0 1 1 1 1 0 0 0(S2,1,1,R,S2)0 0 1 1 1 1 0 0 0(S2,0,1,L,S3)0 0 1 1 1 1 1 0 0(S3,1,1,L,S3)0 0 1 1 1 1 1 0 0(S3,0,0,N,S4)图灵机的思想与模型简介几点结论几点结论(续续):u(3)图灵机模型图灵机模型被认为是计算机的基本理论模型----计算机是使用相应的程序来完成任何设定好的任务。

图灵机是一种离散的、有穷的、构构造造性性的的问题求解思路，一一个个问问题题的的求求解解可可以以通通过过构构造造其其图图灵灵机机(即即程程序序)来解决来解决u(4)图灵认为：凡凡是是能能用用算算法法方方法法解解决决的的问问题题也也一一定定能能用用图图灵灵机机解解决决; 凡凡是是图灵机解决不了的问题任何算法也解决不了图灵机解决不了的问题任何算法也解决不了----图灵可计算性问题图灵机的思想与模型简介谢谢观看谢谢观看！！过三第一组全体成员！过三第一组全体成员！图灵机的思想与模型简介。