培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体

Presentation on theme: "培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体"— Presentation transcript:

1 培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体
西北大学信息科学与技术学院 “大学生IT创新教学实践”活动 培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体

2 图灵（Alan Turing）的伟大贡献 -- 纪念图灵诞辰100周年
学术报告会 图灵（Alan Turing）的伟大贡献 -- 纪念图灵诞辰100周年 郝克刚

3 图灵和图灵机 就如同文学院的学生都熟悉曹雪芹和红楼梦，物理系的学生都熟悉爱因斯坦和相对论一样，
计算机有关专业和学科的学生，不能不知晓计算机和计算机科学理论的奠基人图灵以及图灵机等的基本知识和概念。

4 图灵（Alan Turing） 英国数学家图灵（Alan Turing）是计算机和计算机科学理论的奠基人。
他出生于1912年6月23日，明年是他诞辰100周年。 为了纪念他对计算机科学的伟大贡献，从今年年底开始世界计算机界要举行一系列的纪念活动，。 2012年是图灵年Alan Turing Year

5 提纲：一串待思考的问题 图灵的生平 什么是图灵机和通用图灵机 为什么说它是电子计算机的理论基础 有超越图灵机计算能力的模型吗
是否存在计算机不可解的问题 怎么度量计算的能力和复杂度 图灵测试，计算机能思维吗 图灵奖，对年轻人的期盼和希望

6 1.图灵的生平 图灵Alan Mathison Turing 1912年6月23日出生于英国伦敦近郊。
父亲是英国驻印度的官员。寄养在别人家中。 1926年后中学寄宿，喜欢赛跑。

7 剑桥大学King‘s College 1930年图灵进入剑桥大学King‘s College攻读数学。1934年他22岁时，完成了学位论文，

8 图灵机器概念的提出 1935年图灵对数理逻辑发生兴趣。1936年发表“论可计算数及其在判定问题中的应用”一文。
图灵机器就是为此提出的一个概念。论文发表后引起美国科学家的重视，应邀到美国普林斯顿大学，1938取得博士学位

9 破译了德军密码光荣受勋 1938年回英国剑桥大学。1939年进入英国政府的一研究机构，破译了德军密码，战后光荣受勋。
战后进入英国国家物理实验室，开始了设计和建造英国的电子计算机工程（ACE）。1951被选为英国皇家学会院士。。 1954年6 月7日因吃了含氰化物的苹果，在家中死亡，享年不足42岁。死因成不解之谜。自杀或意外。2008.9布朗的政府道歉。

10 2. 图灵机和通用图灵机 图灵机器是图灵在他的论文中提出的一个抽象的计算机模型。模型非常简单，由下面几部分构成：
n个符号S={s1,…,sn}, 其中有空格符号bS ； m个状态Q={q1,…,qm}, 其中有初始状态q1 Q

11 无穷长的由格子组成的带子。 一条两个方向或一个方向是潜在无穷长的由格子组成的带子。 每个格子可存放一个符号。 带子边附有一个读写头，
qj Si 读写头处于某个状态并指向某个格子， 可以读写所指格子上的符号， 并在带子上左右移动。

12 一组有穷条形如下式的规则： si,qj  sk,ql,d. 其中 d=H,L或R.
执行开始时，在图灵机带子的一串格子上放上由符号（除b外）组成的初始字。读写头处于初始状态q1 ，并指向初始字的第一个格子。 然后如下执行。如果所指的符号是si, 读头的状态是qj， 在所指格子上写符号sk，读头变换状态为ql， 根据d的值（d=H,L或R）读头位置保持不动(H)，左移(L)或右移(R)一格。

13 图灵机器 演示 … … si,qj  sk,ql, d 其中 d = H,L 或 R S ：{ s1,…,sn } si sk ql ql
图灵机器 演示 S ：{ s1,…,sn } … … si sk ql ql qj ql Q：{ q1,…,qm } si,qj  sk,ql, d 其中 d = H,L 或 R

14 通用图灵机的概念 演示 存在这样的一个图灵机T，称为通用图灵机(Universal Turing Machine ) :
通用图灵机的概念 演示 存在这样的一个图灵机T，称为通用图灵机(Universal Turing Machine ) : 对任给的图灵机A，只要把它(A)的规则和初始字，并列起来作为通用图灵机T的初始字，让通用图灵机T运行，运行结果就是图灵机A的运行结果。 正是这个思想奠定了10年后通用电子计算机出现的理论基础。

15 3. 电子计算机出现的理论基础 第一台电子数字计算机 ENIAC (Electronic Numerical Integrator and Computer) 诞生于美国宾州大学莫尔学院。 ENIAC是一台为各种炮火计算弹道的专用计算机，程序是用外接电路板输入。 后查证，世界上第一台专用电子计算机，1939 年爱荷华（Iowa） 州立大学用电子管开发了Atanasoff –Berry Computer(简称ABC)，另外，二战中德国也研制了计算机。

16 冯·诺伊曼的设计思想 1945年冯·诺伊曼（Von Neumann）发表 “关于离散变量自动电子计算机的草案”。最早提出 “存储程序式”的通用计算机的设计思想。 计算机EDVAC (Electronic Discrete Variable Automatic Computer) 由他设计的，建造合同1946 年 4 月签订。预算是十万美元,但最后耗资五十万。 1949 年 8 月交付美国军队的 弹道研究实验室 ，1951 年开始运行。

17 冯·诺伊曼的设计思想来自图灵 而冯·诺伊曼的设计思想却又来自图灵1936年的文章中引入的概念—图灵机器和通用图灵机。
第一台“存储程序式”计算机。EDSAC (Electronic Delay Storage Automatic Calculator)英国剑桥大学威尔克斯（Maurice Vincent Wilkes）领导设计和制造的, 1949年5月6日试运行成功。1951年批量生产投入市场 但是他的设计思想完全来自冯·诺伊曼的EDVAC的设计。 而冯·诺伊曼的设计思想却又来自图灵1936年的文章中引入的概念—图灵机器和通用图灵机。

18 图灵机奠定了通用电子计算机设计的理论基础
之所以这么快就由硬件连线构成的专用计算机过渡到“存储程序式”的通用计算机，完全归功于通用图灵机概念的引入。 因而我们说，是图灵的图灵机理论奠定了通用电子计算机设计的理论基础。这种理论准备同电子技术的结合才最终产生了20世纪最伟大的奇迹。

19 最早设计可编程计算机 巴贝奇 Babbage是最早设计可编程计算机的人。
他设计了分析机，以蒸汽为动力的计算器械，目的是编制各类数学表，可用穿孔卡写出程序控制计算过程；说明计算过程可自动化。 描述了一系列设计，到1871年Babbage死去还未造出机器。 Charles Babbage

20 历史上第一个编程序的人 Augusta Ada King 1815-1852
Augusta Ada King充分了解Babbage机器，1842年－1843年的9个月里，她在一篇文章的注记中用分析机器的指令写下如何计算伯努利（Bernoulli）数的详细步骤，这证明了分析机器的能力． 史学家们认为这注记是历史上第一个程序。 1979年，美国国防部以她的名字命名了他们的语言 Ada语言 1998 年起英国计算机学会建立 Ada 奖。由 2008 年起搞一年一度的女学生计算机科学竞赛。 Augusta Ada King

21 4.有超越图灵机计算能力的模型吗 图灵机是为直观的“计算”给出一个严格的形式化的定义。它的神妙之处还在于它的组成和执行规则相当简单，但是功能却非常强大。 试图对其扩展来扩大它的计算能力都不成功。 例如多增加几个无穷长的带子和读头，最后证明它的计算能力还是等价于原来的图灵机。 即使是非确定的图灵机的能力也等价于确定的图灵机。

22 丘奇- 图灵论题 图灵 1937年被邀请到美国普林斯顿和丘奇(Alonzo Church)一起合作，他们提出了一个后来被叫做丘奇- 图灵论题。 这个论题断言图灵机同直观的有效的函数计算具有等价的问题求解机制。即所有“能解”的问题都存在一个图灵机，只要把问题放在图灵机带子上，若有解则停机后带子内容即是解答。 这个断言叫做“论题”是由于他无法严格证明。

23 全都被证明同图灵机等价 那个时代和后来曾经提出过不少的形式化计算模型，如λ演算、递归函数、正规算法、POST系统、递归算法（胡世华）等，
全都被证明同图灵机等价。 这些事实在一定程度上加强了这个论题。

24 有一些对此论题的质疑 当然在学界也有一些对此论题的质疑， 例如有人认为交互式机器超越了图灵机（Peter Wegner），
有人认为量子计算机，生物计算机可能会超越图灵机，但是这些意见都还没有能给出具有说服力的论证，从而也没有为普遍学者所认可。 在纪念图灵诞辰100周年之际，关于是否有超越图灵机计算能力的模型也是一个争论的热门话题。

25 5.是否存在计算机不可解的问题 由于图灵机是为 “计算”给出的一个严格的形式化的定义。从而使严格证明某些问题是“不可计算”（“不可解”或“不可判定”）成为可能。 要知道这种否定的证明通常是相当困难的，所以说这也是图灵的一个重要贡献。

26 许多实际数学问题是不可判定的。 首先可以证明图灵机的停机问题是不可判定的。 接着证明了推导系统的字的问题是不可判定的。
后来又证明了逻辑系统以外的许多实际数学问题是不可判定的。如有名的希尔伯特第十问题是不可解的，即不存在这样的算法，它能判定一个任意的丢番图方程(Diophantine Equation)是否有整数解。 David Hilbert

27 丢番图方程(Diophantine Equation)
整系数代数多项式方程 ，有无整数解？ x2+y2=z2，勾3股4弦五5 中国古代已知有整数解。 xn+yn=zn 在n>2时没有非零整数解，费尔马 (Pierre de Fermat,  )猜想，隔了三百多年(1995)才得到证明。 聪明的俄国年轻人马蒂亚塞维奇 (Yuri Matiyasevich,) 1970年（23岁）成功地证明了罗宾逊猜想，最终解决了希尔伯特第十问题,证明它是不可解的。 Matiyasevich 1947-

28 不可解的问题程度层次的不同， 即使是不可解的问题，也有程度层次的不同，克林(Stephen Kleene)曾对其进行了分层。

29 6.怎么度量计算的能力和复杂度 图灵机的提出，影响深远，可以说它为以后整个计算机科学的研究奠定了重要的理论基础。
例如关于形式语言和自动机的理论和算法复杂度的理论研究就以图灵机作为基础，它对计算机编译系统和操作系统技术以及应用软件的发展起着重要作用。

30 机器的计算能力 判断一类机器的计算能力，可以以其能计算的函数类型和所能接受的字的类型来划分。
说某机器M 接受某个字 w ，是指如果以字w 作为机器 M 的输入（对图灵机来说就是作为他的初始字），运行后以某指定的接受状态结束计算。也就是说，如果 M 在其他状态结束计算，或计算不终止，则M不接受该字 w 。

31 语言进行分类 乔姆斯基（Avram Noam Chomsky）曾按生成文法的不同对语言进行分类。所谓语言就是某字母表上字的集合。而后来发现语言又和接受它的机器类型有关 1928-

32 理论研究证明如下的对应关系： 语言类型 生成文法 接受的机器类型 0 型语言 0 型文法 图灵机 一型语言 上下文有感文法 线性有界自动机
二型语言 上下文无关文法 下推自动机 三型语言 正则文法 有穷自动机

33 关于算法复杂度的研究 同样是算法，在机器上运行时所需要的时间和空间资源的数量时常相差很大。因而需要定义算法的复杂度来作为度量算法优劣的一个重要指标。 假定算法在图灵机上计算的输入字的长度是l，那么完成此计算所需要的最长时间（即运算的最长步数）是l的一个函数，称此函数为此算法的时间复杂度。同样，完成此计算所需要的最大空间（即运算涉及的格子最大数量）也是l的一个函数，称此函数为此算法的空间复杂度。

34 时间、空间复杂度 例如函数不超过多项式函数，就说此算法具有多项式时间或多项式空间复杂度。
函数不超过指数函数，就说此算法具有指数时间或指数空间复杂度。

35 指数比多项式函数增长快得多 n2 2n

36 “实际可行的 (feasible) ” 算法 例如：多项式函数t=n3, n=60, t=216000，一台百万次计算机，0.2秒即可完成。
而指数函数。t=3n, n=60, t=3604x1028，若能用10亿台百万次计算机并行运算，需要运行一百万年。 因而常认为具有多项式时间复杂度的算法是 “实际可行的 (feasible) ” 算法。而具有指数时间复杂度的算法是实际不可行的。

37 “千僖年数学难题” 这里再顺便介绍一下悬赏奖金一百万美元巨奖，被称为 “千僖年数学难题” 之一的“P = NP?”问题。
这个问题是：“在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能？”

38 确定的和非确定的图灵机 如果执行中每次只可能有一个规则匹配，也就是说所有规则的左端都不完全相同，图灵机的执行是唯一确定的，称这样的机器为确定的图灵机。 反之，有两个或更多的规则的左端完全相同时，图灵机的执行就不是唯一确定的，称这样的机器为非确定的图灵机。

39 有些情况功能是相同的 确定的和非确定的有穷自动机的功能是相同的，它们所接受的语言都是正则集合。
如果不加多项式时间的限制，确定的和非确定的图灵机的功能也是相同的，它们所接受的语言都是递归可枚举集。 如果对图灵机加上空间的限制，在多项式空间界限下，确定的和非确定的图灵机也具有同样的功能。

40 不是都具有同样的功能 但是，并不是在所有情况下确定的和非确定的机器都具有同样的功能。
例如，对具有一个下推存贮的有穷机器来讲两者的功能是不相同的，非确定性的下推自动机所接受的语言是上下文无关语言，而确定的下推自动机所接受的语言却是上下文无关语言的一个真正的子类。

41 问题至今仍未解决 那么在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能呢？即是否P = NP?
这个问题的提法相当清晰，但是要解答这个问题却不容易。当代很多有名的计算机科学家都研究过这个问题，问题至今仍未解决。解决这个问题似乎需要在方法上有重大突破。

42 NP完全的理论 上世纪70年代提出的NP完全的理论，对解决此问题有很大的推进，但仍未最终解决。
不久前，有一位HP公司的工程师宣称他证明了P != NP，不过目前还尚未被认可。

43 7. 图灵测试，计算机能思维吗 人们惊奇地发现它的能力大大超出原来的预期。计算机不仅可以做大量的计算，还能进行复杂的推理。
于是就把它同人的大脑进行比较，提出“计算机能思维吗(Can machines think? )”的问题。 这里涉及到对“什么是思维”的理解和界定，涉及哲学、认知学以及社会学等各个方面，相当复杂众说纷纭，很难有一个统一的标准。

44 图灵测试 图灵1950年10月在英国曼彻斯特大学发表论文“计算机和智能”，巧妙地把这个问题转化为一种可操作的方法，那就是测试。后来被称为图灵测试。 简单说就是与其争论什么是“思维”，不如我们去做实验测试。计算机通过了测试就说该计算机能思维，否则就说还达不到思维的水平。

45 图灵测试的设计 A B 测试分测试人员和被测试方两部分。被测试方由A和B构成，A和B分别是一个人和一台被测试的计算机。测试人员和被测试方是分开的，测试人员并不知道A和B那个是人那个是计算机。

46 通过测试被认为是能够思维的 测试人员分别向A和B提问，如果测试人员能够通过问题的回答，分不出A和B谁是机器谁是人，那这个机器就通过图灵测试。
图灵指出：“如果机器在某些条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。”

47 图灵预言，50年内通过图灵测试 当时的计算机根本无法通过这一测试。图灵预言，50年内，即在20世纪末会有计算机通过图灵测试。
图灵测试没有规定问题的范围和提问的标准，如果想要制造出能通过试验的机器，必须在电脑中储存人类所有可以想到的问题，储存对这些问题的所有合乎常理的回答，并且还需要理智地作出选择。 这几乎是不可能的。到目前为止还没有电脑能通过图灵测试。但是如果限制在一定的领域和范围之内通过图灵测试是完全有可能的。

48 自然,对于图灵测试的理解以及它的作用等方面，学界也有各种不同的争论。
计算机深蓝战胜国际象棋冠军 人工智能专家经过多年的努力，开发了不少智能软件，在理论和实践上取得了很大的进步。 1997年5月3-11日，IBM的计算机深蓝（Deep Blue）以2胜1负3平的成绩第一次战胜国际象棋冠军卡斯帕罗夫大师。也可以说在一定意义下实现了图灵的预言。 自然,对于图灵测试的理解以及它的作用等方面，学界也有各种不同的争论。

49 2208 年机器能识别出我是人！

50 8.图灵奖与对年轻人的期盼 1966年，美国的国际计算机学会ACM（Association for Computing Machinery）为表彰图灵对计算机科学的伟大贡献，设立了图灵奖（A. M. Turing Award）。 每年一届，奖金25万美元，奖金由 Intel 和 Google公司提供。

51 计算机科学界的诺贝尔奖 奖励在计算机科学研究中做出创造性贡献，推动计算机科学技术发展的杰出科学家。
选择条件要求很高，程序极严，一直被公认是世界计算机科学领域的最高荣誉奖项，相当于计算机科学界的诺贝尔奖。

52 图灵奖的得主 1966-2010年已举行45届，有55名科学家获此殊荣。 许多著名的对计算机科学技术作出重大贡献的科学家都是图灵奖的得主。
获奖者的名单和他们一个个的贡献推介，活生生地展现了几十年来计算机科学技术发展的历程和辉煌成就的方方面面。

53 中国人的遗憾 令我们中国人感到遗憾的是我们国内培养成长的专家至今还没有一个在获奖名单中出现。
获图灵奖的唯一一位华人是2000年得主姚期智博士(Chi-Chih Yao)， 台湾大学毕业，在美国哈佛大学和伊利诺斯大学取得博士学位，曾在美国著名的麻省理工学院、斯丹佛大学、加州大学贝克莱分校任教，获奖时任美国普林斯顿大学教授。现在海归聘为中国清华大学教授。

54 对中国学者很大的期待， 我们国家的科学研究水平同国家的经济和政治地位是不匹配的。希望在不远的将来能够有我们自己培养的科学家做出重大的贡献。
1993年图灵奖得主米勒（Robin Milner）：“中国，作为在世界上发挥日益重要作用的大国，具有引领为新技术建立科学基础的机会 …。 ”《通信与移动系统：π-演算》中译本（2009年出版）序言。

55 结束语：寄希望于新一代年轻人 外国人说出了我们中国人的心声，这也正是我们广大中国学者所日夜期盼的。希望把机会变为现实。
实现这个愿望，也许要经过几代人的不懈努力。 寄希望于新一代年轻人。

56 推荐阅读 苹果CEO乔布斯2005在斯坦福大学的演讲稿

57 Stay Hungry. Stay Foolish.
求知若饥，虚心若愚。 史蒂夫•乔布斯: Steven Paul Jobs （ ） 你们的时间很有限，所以不要将它浪费在重复其它人的生活上。 Stay Hungry. Stay Foolish.

58 谢谢大家！ 电子邮件 hkg@nwu.edu.cn 个人网页 http://mainpage.nwu.edu.cn/hkg/home/
个人网页 科学网博客