第一讲计算模型及图灵机.pptVIP

阿伦.图灵 1951年，由于图灵一系列杰出的贡献和重大创造，被评为英国皇家学会院士，之后因同性恋问题，陷入个人生活的危机。 1952年，图灵被法院传讯，指控其行为“极为不端” 。 1954年6月7日（42岁生日不到2星期），图灵因服用氰化物溶液中浸泡过的苹果而在家中死去。 2001年6月23日，为纪念图灵89岁诞辰，在英国曼彻斯特的Sackille公园为图灵建造了一尊真人大小的青铜坐像，手拿苹果的图灵安详地坐在一条长靠背椅上，似乎在沉思什么（此铜像为中国制造） 阿伦.图灵 上图这位人物是阿兰·麦席森·图灵，数学家、密码学家、计算机科学的创始人。 当年图灵由于身为同性恋者,被强行“化学阉割”，在被迫注射大量雌性激素后，不堪屈辱，吃沾染氰化钾的苹果自尽，他死去的桌边还剩下半个苹果，时年42岁。 苹果公司？ 图灵的粉丝乔布斯把公司取名为苹果,并且以被咬了一口的苹果作为标志。 2009年9月，英国首相布朗为当年执行“化学阉割”向艾兰·图灵道歉。 对于是否对罪犯实行“化学阉割”，争议还在继续……你怎么看？ 1.1 计算模型与图灵机 20世纪30年代，计算模型研究取得突破性进展的时期。 这时，图灵等人在研究中陆续提出了一批计算模型，如递归函数，λ演算、图灵机、 波斯特系统等。人们认为，只要能用算法解决的问题，一定能用这些计算模型解决。 1.1 计算模型与图灵机 计算模型，是刻画计算这一概念的、抽象的形式系统或数学系统，而算法是对计算过程、步骤（或状态）的一种刻画，是计算方法的一种能行实现的方式。 1.1 计算模型与图灵机 图灵机的基本组成： 由一条两端可以无限延长的带子，一个读写头和一组控制读写头工作的命令（控制器）组成。 控制器的命令可表示成： （状态，符号）?（写符号，移动，状态） 图灵机的基本组成 1.1 计算模型与图灵机 为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成： 1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。  1.1 计算模型与图灵机 2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。  1.1 计算模型与图灵机 3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。  1.1 计算模型与图灵机 4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。  1.1 计算模型与图灵机 注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。 1.1 计算模型与图灵机 图灵机是一种数学自动机，控制命令相当于程序指令。对图灵机的理解有如下三种： 一、把图灵机看作识别器，即判断带子上最初的内容能否被图灵机接受； 1.1 计算模型与图灵机 二、把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入、输出集合性质之间的关系，这就研究了图灵机的生成能力。 1.1 计算模型与图灵机 三、把图灵机看作计算器，相当于一个函数。图灵机的输入是函数自变量的值，图灵机的输出是函数的值。 1.1 计算模型与图灵机 图灵机简洁的构造和运行原理隐含了存储程序的思想，深刻地揭示了现代通用电子计算机最核心的内容。 20世纪40年代，在图灵机提出不到10年，世界上第一台存储程序式通用电子数字计算机就诞生了。 1.1 计算模型与图灵机 由于图灵对计算科学的杰出贡献，美国计算机协会（ACM）于1966年设立了一图灵名字命名的计算机科学大奖——以纪念这位杰出的科学巨匠。 同时，在每年的ACM年会上表彰对计算科学作出卓越贡献的科学家，并颁发此奖。 1.2 二进制的数据表示 二进制与十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进制表示的符号只有两个：0，1。 现实中的信息种类有：数值、文字、语音、图形和图像， 而计算机是一个数字化的世界，内部所有的信息均必须数字化编码，转化为二进制表示的信息，才能进行传送、存储和处理。 1.2 二进制的数据表示 二进制的特点： 1、逢二进一； 2、位权为2n；