计算模型与图灵机幻灯片.ppt

1、计算机科学导论 乐嘉锦 计算机科学与技术学院 2012.11,1,本课程使用教材,计算机导论 袁方 王兵 李继民 编著 清华大学出版社 2009年7月（第2版）,2,参考书籍:,计算机科学导论 计算机科学理论与基础知识 - 基础知识 -.计算机科学导论 译者: 石茵 本书作者把计算机的理论以数学为基础作为出发点,从简单的程序编制入手,逐步引导出计算机的结构,全书共分四章。 . . 80K 2006-8-19 -,3,计算机科学导论【作者】 (德)冈特 北京航空航天大学出版社 1999年02月,本书可供大专院校计算机专业的师生作为教科书,教学参考书以及作为从事计算机研究人员的参考书。 相关资料

2、:. . 64K 2006-8-30 -,4,计算机科学导论（美）A.Forouzan. Behrouz 2005年07月,本书是大学计算机相关专业的基础课教材,涉及到计算机科学的各个方面。此书着重讲解基本概念而不是数学模型和技术细节,通过大量的图表和演示范例讲解计算机科学的基础知识;. 41K 2006-7-15 -,5,计算机科学导论,赵玉琢主编,清华大学出版社2003年第1版,参考书籍:,6,计算模型与图灵机,第一讲,7,世界上第一台电子计算机： 恩尼亚克（ENIAC）,1946年2月诞生于美国宾夕法尼亚大学莫尔学院 第一台计算机 ENIAC，重达几十吨，耗去整个城镇一半的电能；却要用十

3、几秒钟才能完成，现在几毫秒就可以完成的加法运算。,8,当年恩尼亚克（ENIAC）现场,9,学术界公认：电子计算机的理论与模型是由英国数学家图灵在此前10年，即1936年发表论文 “论可计算数及其在判定问题中的应用”中奠定基础.,不朽的论文,10,图灵（Turing）是谁?,图灵奖,11,图灵（Turing）,图灵奖，是美国计算机协会（ACM）于1966年设立的，又叫“A.M. 图灵奖”，专门奖励那些对计算机事业作出重要贡献的个人。 其名称取自计算机科学的先驱、英国科学家阿兰图灵，这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。,12,图灵（Tur

4、ing）,图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图灵奖由英特尔公司赞助，奖金为100,000美元。,13,1.0 图灵其人其事（奇人奇事）,图灵：（19121954）英国人； 图灵：英国杰出的数学家； 图灵：计算机理论的创始人和奠基人； 图灵：天才与精神病是一线之分。,14,图灵（Turing）,阿兰麦席森图灵 （Alan Mathison Turing） 1912.6.231954.6.7 英国数学家、逻辑学家， 被称为人工智能之父

5、。,15,1966年，ACM纪念计算机诞生20周年 图灵奖，计算机界设立的第一个奖项 到2001年为止，共颁发36届，43位计算机科学获此殊荣,图灵（Turing）,16,阿伦.图灵（Alan Mathison Turing）,1912.6.23 伦敦近郊帕丁镇（Paddington） 1925年 13岁的图灵进寄宿的谢博恩中学（Sherbaurne School），擅长跑 1931年 想进剑桥“三圣学院”（Trinity College），两次未被录取，只好进了“国王学院”（Kings College）读数学,17,国王学院(Kings College),国王学院(King“s Colleg

6、e)是剑桥大学内最有名的学院之一，成立于1441年。 由当时的英国国王亨利六世设立创建，因而得名“国王”学院。 最初创立时只有1名院长和70名学生，全部来自伊顿公学。,18,国王学院(Kings College),当时国王学院是专门为亨利六世所创的伊顿公学的毕业生而建立的，不收其他学生。 为了显示国王的雄厚财力，学院建立之初就追求宏伟壮观的建筑，而其建筑群中最著名的当属国王学院礼拜堂，它耸入云霄的尖塔和恢弘的哥特建筑风格已经成为整个剑桥镇的标志和荣耀。,19,1935年，23岁的图灵对数理逻辑发生兴趣 数理逻辑又叫“形式逻辑（FormalLogic）”或“符号逻辑（Symbol Logic）”

7、，是逻辑学的一个重要分支。数理逻辑用数学方法，也就是用符号和公式、公理的方法研究人的思维过程、思维规律。,阿伦.图灵,20,数理逻辑其起源可追溯到17世纪，德国大数学家莱布尼茨（Gottfried Wilhelm Leibniz，16461716）的思想中，数理逻辑、数学和计算机三者均出于一个统一的目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。,莱布尼茨,21,“计算机”到底是一种什么样的机器，应由哪些部分组成，如何进行计算和工作？在图灵之前没人能清楚地说明过。 正是图灵1936年（24岁）的那篇论文，第一次提出了一种计算机的抽象模型，该模型就是现在被大家称作为“图灵机”（Tur

8、ing Machine），同年，图灵赴美国普林斯顿大学攻读博士学位。,阿伦.图灵,22,学术界公认：电子计算机的理论与模型是由英国数学家图灵在此前10年，即1936年发表论文 “论可计算数及其在判定问题中的应用”中奠定基础.,不朽的论文,23,图灵论文发表后，引起了美国科学家的重视，普林斯顿大学向图灵发出邀请，到美国与丘奇合作。 1938年，图灵在美国普林斯顿大学获博士学位。,阿伦.图灵,24,在美国，图灵遇到匈牙利的天才冯。诺依曼（John Von Neumann 19031957 54岁），冯.诺依曼1930年移民美国，在普林斯顿大学任教。,阿伦.图灵,25,冯.诺依曼1945年6月30日

9、（42岁）发表了题为“关于离散变量自动电子计算机的草案”的长文，正式提出了存储程序的概念，因而存储程序式计算机被称为“冯.诺依曼体系结构”，而ENIAC为非存储程序式计算机。,冯.诺依曼,26,1938年，图灵返回英国，到剑桥大学从事Z函数的计算方法。 1939年，二战爆发后，图灵进入英国外交部的科学研究机构中工作，细节不祥。图灵的主要工作是破译德军的密码，用继电器做“霹雳弹”，破译了许多德军的密码，获得了荣誉勋章。,阿伦.图灵,27,1942年，图灵再次访问美国（战时的公务），会见普林斯顿的老朋友，了解美国在计算机研制方面的最新进展。 1946年，战后，图灵去英国国家物理实验室NPL（Nat

10、ional Physical Laboratory）新建的数学部工作，开始设计与建造电子计算机的重大工程。,阿伦.图灵,28,同年5月，来了个称心的助手，詹姆斯.威尔金森（James Hardy Wilkinson，19191986，詹姆斯.威尔金森是1970年图灵奖的获得者），他们研制名为ACE（Automatic Computing Engine）计算机的第五版。,詹姆斯.威尔金森,29,1948年，图灵离开NPL，留下正在设计、研制的ACE第八版，威尔金森接手研制，图灵则加盟曼彻斯特大学继续其研究。 1950年，5月，在威尔金森的领导下，ACE第五版研制成功，生产了30台商用机。 195

11、0年10月，图灵发表论文“计算机和智能”（Computing Machinery and Intelligence），开创了计算机人工智能的先河。,阿伦.图灵,30,阿伦.图灵,1951年，由于图灵一系列杰出的贡献和重大创造，被评为英国皇家学会院士，之后因同性恋问题，陷入个人生活的危机。 1952年，图灵被法院传讯，指控其行为“极为不端” 。,31,1954年6月7日（42岁生日不到2星期），图灵因服用氰化物溶液中浸泡过的苹果而在家中死去。 2001年6月23日，为纪念图灵89岁诞辰，在英国曼彻斯特的Sackille公园为图灵建造了一尊真人大小的青铜坐像，手拿苹果的图灵安详地坐在一条长靠背椅上

12、，似乎在沉思什么（此铜像为中国制造）,阿伦.图灵,32,33,上图这位人物是阿兰麦席森图灵，数学家、密码学家、计算机科学的创始人。,当年图灵由于身为同性恋者,被强行“化学阉割”，在被迫注射大量雌性激素后，不堪屈辱，吃沾染氰化钾的苹果自尽，他死去的桌边还剩下半个苹果，时年42岁。,34,苹果公司？,图灵的粉丝乔布斯把公司取名为苹果,并且以被咬了一口的苹果作为标志。 2009年9月，英国首相布朗为当年执行“化学阉割”向艾兰图灵道歉。 对于是否对罪犯实行“化学阉割”，争议还在继续你怎么看？,35,1.1 计算模型与图灵机,20世纪30年代，计算模型研究取得突破性进展的时期。 这时，图灵等人在研究中陆

13、续提出了一批计算模型，如递归函数，演算、图灵机、 波斯特系统等。人们认为，只要能用算法解决的问题，一定能用这些计算模型解决。,36,1.1 计算模型与图灵机,计算模型，是刻画计算这一概念的、抽象的形式系统或数学系统，而算法是对计算过程、步骤（或状态）的一种刻画，是计算方法的一种能行实现的方式。,37,1.1 计算模型与图灵机,图灵机的基本组成： 由一条两端可以无限延长的带子，一个读写头和一组控制读写头工作的命令（控制器）组成。 控制器的命令可表示成： （状态，符号）（写符号，移动，状态）,38,图灵机的基本组成,39,1.1 计算模型与图灵机,为了模拟人的这种运算过程，图灵构造出一台假想的机器

14、，该机器由以下几个部分组成： 1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, . ，纸带的右端可以无限伸展。,40,1.1 计算模型与图灵机,2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。,41,1.1 计算模型与图灵机,3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。,42,

15、1.1 计算模型与图灵机,4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。,43,1.1 计算模型与图灵机,注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。,44,1.1 计算模型与图灵机,图灵机是一种数学自动机，控制命令相当于程序指令。对图灵机的理解有如下三种： 一、把图灵机看作识别器，即判断带子上最初的内容能否被图灵机接受；,45,1.1 计算模型与图灵机,二、把图灵机看作生成器，对给定的输入集合

16、，考察输出集合，并研究输入、输出集合性质之间的关系，这就研究了图灵机的生成能力。,46,1.1 计算模型与图灵机,三、把图灵机看作计算器，相当于一个函数。图灵机的输入是函数自变量的值，图灵机的输出是函数的值。,47,1.1 计算模型与图灵机,图灵机简洁的构造和运行原理隐含了存储程序的思想，深刻地揭示了现代通用电子计算机最核心的内容。 20世纪40年代，在图灵机提出不到10年，世界上第一台存储程序式通用电子数字计算机就诞生了。,48,1.1 计算模型与图灵机,由于图灵对计算科学的杰出贡献，美国计算机协会（ACM）于1966年设立了一图灵名字命名的计算机科学大奖以纪念这位杰出的科学巨匠。 同时，在

17、每年的ACM年会上表彰对计算科学作出卓越贡献的科学家，并颁发此奖。,49,1.2 二进制的数据表示,二进制与十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进制表示的符号只有两个：0，1。 现实中的信息种类有：数值、文字、语音、图形和图像， 而计算机是一个数字化的世界，内部所有的信息均必须数字化编码，转化为二进制表示的信息，才能进行传送、存储和处理。,50,1.2 二进制的数据表示,二进制的特点： 1、逢二进一； 2、位权为2n； 3、基数由0，1组成。,51,1.2 二进制的数据表示,十进制（D） 二进制（B）八进制（O）十六进制（H）,0 1 2

18、3 4 5 6 7 10 11 12 13 14 15 16 17,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0123456789abcdef,0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111,52,1.3 存储程序式计算机的基本结 构与工作原理,存储程序： 图灵机的带子可以看成是最初的计算机存储设备，数据可以存储在上面，也可以根据需要被擦去或修改；图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器的安排下，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。,53,1.3 存储程序式计算机的基本结构与工作原理,在图灵机诞生后不到10年，在以冯。诺依曼为代表的科学家的努力下，现代存储式电子数字计算机的基本结构与工作原理被确定下来。 计算机的五个组成部分： 存储器，控制器，运算器，输入设备和输出设备。,54,1.4 电子计算机的分类,按照用途分：专用计算机和通用计算机； 按