? 聪明的俄国年轻人马蒂亚塞维奇 (Yuri银河国际手机app Matiyasevich

当前位置:银河国际app下载 > 银河国际手机app > ? 聪明的俄国年轻人马蒂亚塞维奇 (Yuri银河国际手机app Matiyasevich
作者: 银河国际app下载|来源: http://www.jtxdm.com|栏目:银河国际手机app

文章关键词:银河国际app下载,图灵机

  图灵机和通用图灵机_计算机硬件及网络_IT/计算机_专业资料。图灵机和通用图灵机

  西北大学信息科学与技术学院 “大学生IT创新教学实践”活动 培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体 1 学术报告会 图灵(Alan Turing)的伟大贡献 -- 纪念图灵诞辰100周年 郝克刚 2011.10. 2 图灵和图灵机 ? 就如同文学院的学生都熟 悉曹雪芹和红楼梦,物理 系的学生都熟悉爱因斯坦 和相对论一样, ? 计算机有关专业和学科的 学生,不能不知晓计算机 和计算机科学理论的奠基 人图灵以及图灵机等的基 本知识和概念。 1912-1954 3 图灵(Alan Turing) ? 英国数学家图灵(Alan Turing)是计算机和计算机 科学理论的奠基人。 ? 他出生于1912年6月23日, 明年是他诞辰100周年。 ? 为了纪念他对计算机科学的 伟大贡献,从今年年底开始 世界计算机界要举行一系列 的纪念活动,。 2012年是图灵年 Alan Turing Year 4 提纲:一串待思考的问题 1. 2. 3. 4. 5. 6. 7. 8. 图灵的生平 什么是图灵机和通用图灵机 为什么说它是电子计算机的理论基础 有超越图灵机计算能力的模型吗 是否存在计算机不可解的问题 怎么度量计算的能力和复杂度 图灵测试,计算机能思维吗 图灵奖,对年轻人的期盼和希望 5 1.图灵的生平 ? 图灵Alan Mathison Turing 1912年6月23日 出生于英国伦敦近郊。 ? 父亲是英国驻印度的官 员。寄养在别人家中。 ? 1926年后中学寄宿,喜 欢赛跑。 6 剑桥大学King?s College ? 1930年图灵进入剑桥大 学King‘s College攻读数 学。1934年他22岁时, 完成了学位论文, 7 图灵机器概念的提出 ? 1935 年图灵对数理逻辑发 生兴趣。1936年发表“论可 计算数及其在判定问题中的 应用”一文。 ? 图灵机器就是为此提出的一个概念。论文 发表后引起美国科学家的重视,应邀到美 国普林斯顿大学,1938取得博士学位 8 破译了德军密码光荣受勋 ? 1938年回英国剑桥大学。1939 年进入英国政府的一研究机构, 破译了德军密码,战后光荣受勋。 ? 战后进入英国国家物理实验室, 开始了设计和建造英国的电子计 算机工程(ACE)。1951被选为 英国皇家学会院士。。 ? 1954年6 月7日因吃了含氰化物 的苹果,在家中死亡,享年不足 42岁。死因成不解之谜。自杀或 意外。2008.9布朗的政府道歉。 9 2. 图灵机和通用图灵机 ? 图灵机器是图灵在他的论文中提出的一个抽 象的计算机模型。模型非常简单,由下面几 部分构成: ? n个符号S={s1,…,sn}, 其中有空格符号b?S ; ? m个状态Q={q1,…,qm}, 其中有初始状态q1? Q 10 无穷长的由格子组成的带子。 ? 一条两个方向或一个方向 是潜在无穷长的由格子组 成的带子。 ? 每个格子可存放一个符号。 ? 带子边附有一个读写头, Si qj ? 读写头处于某个状态并指向某个格子, ?可以读写所指格子上的符号, ?并在带子上左右移动。 11 一组有穷条形如下式的规则: ? si,qj ? sk,ql,d. 其中 d=H,L或R. ? 执行开始时,在图灵机带子的一串格子上放上由 符号(除b外)组成的初始字。读写头处于初始状 态q1 ,并指向初始字的第一个格子。 ? 然后如下执行。如果所指的符号是si, 读头的状态 是qj, ? 在所指格子上写符号sk,读头变换状态为ql, ? 根据d的值(d=H,L或R)读头位置保持不动(H),左移 (L)或右移(R)一格。 12 图灵机器 S :{ s1,…,sn } 演示 … ql s sk i … ql qjl Q:{ q1,…,qm } si,qj ? sk,ql, d 其中 d = H,L 或 R 13 通用图灵机的概念 演示 ? 存在这样的一个图灵机T,称为通用图灵机 (Universal Turing Machine ) : ? 对任给的图灵机A,只要把它(A)的规则和 初始字,并列起来作为通用图灵机T的初始 字,让通用图灵机T运行,运行结果就是图 灵机A的运行结果。 ? 正是这个思想奠定了10年后通用电子计算 机出现的理论基础。 14 3. 电子计算机出现的理论基础 ? 第一台电子数字计算机 ENIAC (Electronic Numerical Integrator and Computer) 1946.2 诞生于 美国宾州大学莫尔学院。 ENIAC是一台为各种炮火 计算弹道的专用计算机, 程序是用外接电路板输入。 ? 后查证,世界上第一台专用电子计算机,1939 年爱荷华 (Iowa) 州立大学用电子管开发了Atanasoff –Berry Computer(简称ABC),另外,二战中德国也研制了计算机。 15 ? 冯· 诺伊曼的设计思想 ? 1945年冯· 诺伊曼(Von Neumann) 发表 “关于离散变量自动电子计算 机的草案”。最早提出 “存储程序 式”的通用计算机的设计思想。 ? 计算机EDVAC (Electronic Discrete Variable Automatic Computer) 由他 设计的,建造合同1946 年 4 月签订。 预算是十万美元,但最后耗资五十万。 ? 1949 年 8 月交付美国军队的 弹道研 究实验室 ,1951 年开始运行。 1903-1957 16 冯· 诺伊曼的设计思想来自图灵 ? 第一台“存储程序式”计算机。 EDSAC (Electronic Delay Storage Automatic Calculator)英 国剑桥大学威尔克斯(Maurice Vincent Wilkes)领导设计和制造 的, 1949年5月6日试运行成功。 1951年批量生产投入市场 ? 但是他的设计思想完全来自冯· 诺 伊曼的EDVAC的设计。 ? 而冯· 诺伊曼的设计思想却又 来自图灵1936年的文章中引 入的概念—图灵机器和通用 图灵机。 17 图灵机奠定了通用电子计算机设 计的理论基础 ? 之所以这么快就由硬件连线构成的专用计 算机过渡到“存储程序式”的通用计算机, 完全归功于通用图灵机概念的引入。 ? 因而我们说,是图灵的图灵机理论奠定了 通用电子计算机设计的理论基础。这种理 论准备同电子技术的结合才最终产生了20 世纪最伟大的奇迹。 18 最早设计可编程计算机 ? 巴贝奇 Babbage是最早设计 可编程计算机的人。 ? 他设计了分析机,以蒸汽为动 力的计算器械,目的是编制各 类数学表,可用穿孔卡写出程 序控制计算过程;说明计算过 程可自动化。 ? 描述了一系列设计,到1871 Charles Babbage 年Babbage死去还未造出机器。 1791-1871 19 历史上第一个编程序的人 ? Augusta Ada King充分了解Babbage机 器,1842年-1843年的9个月里,她在 一篇文章的注记中用分析机器的指令写 下如何计算伯努利(Bernoulli)数的详 细步骤,这证明了分析机器的能力. ? 史学家们认为这注记是历史上第一个程 序。 ? 1979年,美国国防部以她的名字命名了 他们的语言 Ada语言 ? 1998 年起英国计算机学会建立 Ada 奖。 由 2008 年起搞一年一度的女学生计算 Augusta Ada King 机科学竞赛。 1815-1852 20 4.有超越图灵机计算能力的模型吗 ? 图灵机是为直观的“计算”给出一个严格的形式 化的定义。它的神妙之处还在于它的组成和执行 规则相当简单,但是功能却非常强大。 ? 试图对其扩展来扩大它的计算能力都不成功。 ? 例如多增加几个无穷长的带子和读头,最后证明 它的计算能力还是等价于原来的图灵机。 ? 即使是非确定的图灵机的能力也等价于确定的图 灵机。 21 丘奇- 图灵论题 ? 图灵 1937年被邀请到美国普林斯 顿和丘奇(Alonzo Church)一起合 作,他们提出了一个后来被叫做丘 奇- 图灵论题。 ? 这个论题断言图灵机同直观的有效 的函数计算具有等价的问题求解机 制。即所有“能解”的问题都存在 一个图灵机,只要把问题放在图灵 机带子上,若有解则停机后带子内 容即是解答。 ? 这个断言叫做“论题”是由于他无 法严格证明。 1903-1995 22 全都被证明同图灵机等价 ? 那个时代和后来曾经提出 过不少的形式化计算模型, 如λ演算、递归函数、正 规算法、POST系统、递 归算法(胡世华)等, ? 全都被证明同图灵机等价。 ? 这些事实在一定程度上加 强了这个论题。 1912-1998 23 有一些对此论题的质疑 ? 当然在学界也有一些对此论题的质疑, ? 例如有人认为交互式机器超越了图灵机(Peter Wegner), ? 有人认为量子计算机,生物计算机可能会超越图 灵机,但是这些意见都还没有能给出具有说服力 的论证,从而也没有为普遍学者所认可。 ? 在纪念图灵诞辰100周年之际,关于是否有超越 图灵机计算能力的模型也是一个争论的热门线.是否存在计算机不可解的问题 ? 由于图灵机是为 “计算”给出的一个严格 的形式化的定义。从而使严格证明某些问 题是“不可计算”(“不可解”或“不可 判定”)成为可能。 ? 要知道这种否定的证明通常是相当困难的, 所以说这也是图灵的一个重要贡献。 25 许多实际数学问题是不可判定的。 ? 首先可以证明图灵机的停机问题是不 可判定的。 ? 接着证明了推导系统的字的问题是不 可判定的。 ? 后来又证明了逻辑系统以外的许多实 际数学问题是不可判定的。如有名的 希尔伯特第十问题是不可解的,即不 存在这样的算法,它能判定一个任意 David Hilbert 的丢番图方程(Diophantine Equation) 1862-1943 是否有整数解。 26 丢番图方程(Diophantine Equation) ? 整系数代数多项式方程 ,有无整数解? ? x2+y2=z2,勾3股4弦五5 中国古代已知有 整数解。 ? xn+yn=zn 在n2时没有非零整数解,费尔 马 (Pierre de Fermat, 1601-1665)猜想,隔 了三百多年(1995)才得到证明。 ? 聪明的俄国年轻人马蒂亚塞维奇 (Yuri Matiyasevich,) 1970年(23岁)成功地证 Matiyasevich 明了罗宾逊猜想,最终解决了希尔伯特第十 1947问题,证明它是不可解的。 27 不可解的问题程度层次的不同, ? 即使是不可解的问题,也 有程度层次的不同,克林 (Stephen Kleene)曾对其进 行了分层。 ? 笔者早期也曾涉及此类研 究,提出过“可构造实数 论中若干谓词在Kleen分层 下所属的类型”(《数学 学报》1964年第四期。) 28 6.怎么度量计算的能力和复杂度 ? 图灵机的提出,影响深远,可以说它为以 后整个计算机科学的研究奠定了重要的理 论基础。 ? 例如关于形式语言和自动机的理论和算法 复杂度的理论研究就以图灵机作为基础, 它对计算机编译系统和操作系统技术以及 应用软件的发展起着重要作用。 29 机器的计算能力 ? 判断一类机器的计算能力,可以以其能计 算的函数类型和所能接受的字的类型来划 分。银河国际手机app ? 说某机器M 接受某个字 w ,是指如果以字 w 作为机器 M 的输入(对图灵机来说就是 作为他的初始字),运行后以某指定的接 受状态结束计算。也就是说,如果 M 在其 他状态结束计算,或计算不终止,则M不接 受该字 w 。 30 语言进行分类 ? 乔姆斯基(Avram Noam Chomsky)曾按 生成文法的不同对语言 进行分类。所谓语言就 是某字母表上字的集合。 而后来发现语言又和接 受它的机器类型有关 192831 理论研究证明如下的对应关系: 语言类型 0 型语言 一型语言 二型语言 三型语言 生成文法 0 型文法 上下文有感文法 上下文无关文法 正则文法 接受的机器类型 图灵机 线性有界自动机 下推自动机 有穷自动机 32 关于算法复杂度的研究 ? 同样是算法,在机器上运行时所需要的时间和空 间资源的数量时常相差很大。因而需要定义算法 的复杂度来作为度量算法优劣的一个重要指标。 ? 假定算法在图灵机上计算的输入字的长度是l,那 么完成此计算所需要的最长时间(即运算的最长 步数)是l的一个函数,称此函数为此算法的时间 复杂度。同样,完成此计算所需要的最大空间 (即运算涉及的格子最大数量)也是l的一个函数, 称此函数为此算法的空间复杂度。 33 时间、空间复杂度 ? 例如函数不超过多项式函数,就说此算法 具有多项式时间或多项式空间复杂度。 ? 函数不超过指数函数,就说此算法具有指 数时间或指数空间复杂度。 34 指数比多项式函数增长快得多 1200 1000 800 600 400 200 0 1 2 3 4 5 6 7 8 9 10 y=n n2 y=n^2 2n y=2^n 35 “实际可行的 (feasible) ” 算法 ? 例如:多项式函数t=n3, n=60, t=216000, 一台百万次计算机,0.2秒即可完成。 ? 而指数函数。t=3n, n=60, t=360?4x1028,若 能用10亿台百万次计算机并行运算,需要 运行一百万年。 ? 因而常认为具有多项式时间复杂度的算法 是 “实际可行的 (feasible) ” 算法。而具有 指数时间复杂度的算法是实际不可行的。 36 “千僖年数学难题” ? 这里再顺便介绍一下悬赏奖金一百万美元 巨奖,被称为 “千僖年数学难题” 之一 的“P = NP?”问题。 ? 这个问题是:“在多项式时间界限下,确 定的和非确定的图灵机器是否具有同等的 功能?” 37 确定的和非确定的图灵机 ? 如果执行中每次只可能有一个规则匹配, 也就是说所有规则的左端都不完全相同, 图灵机的执行是唯一确定的,称这样的机 器为确定的图灵机。 ? 反之,有两个或更多的规则的左端完全相 同时,图灵机的执行就不是唯一确定的, 称这样的机器为非确定的图灵机。 38 有些情况功能是相同的 ? 确定的和非确定的有穷自动机的功能是相 同的,它们所接受的语言都是正则集合。 ? 如果不加多项式时间的限制,确定的和非 确定的图灵机的功能也是相同的,它们所 接受的语言都是递归可枚举集。 ? 如果对图灵机加上空间的限制,在多项式 空间界限下,确定的和非确定的图灵机也 具有同样的功能。 39 不是都具有同样的功能 ? 但是,并不是在所有情况下确定的和非确 定的机器都具有同样的功能。 ? 例如,对具有一个下推存贮的有穷机器来 讲两者的功能是不相同的,非确定性的下 推自动机所接受的语言是上下文无关语言, 而确定的下推自动机所接受的语言却是上 下文无关语言的一个线 问题至今仍未解决 ? 那么在多项式时间界限下,确定的和非确 定的图灵机器是否具有同等的功能呢?即 是否P = NP? ? 这个问题的提法相当清晰,但是要解答这 个问题却不容易。当代很多有名的计算机 科学家都研究过这个问题,问题至今仍未 解决。解决这个问题似乎需要在方法上有 重大突破。 41 NP完全的理论 ? 上世纪70年代提出的NP完全的理论,对解 决此问题有很大的推进,但仍未最终解决。 ? 笔者30年前曾写过一篇综述文章,NP完全 问题及有关理论研究(《计算机科学》, 1980年1期。) ? 不久前,有一位HP公司的工程师宣称他证 明了P != NP,不过目前还尚未被认可。 42 7. 图灵测试,计算机能思维吗 ? 人们惊奇地发现它的能力大大超出原来的预期。 计算机不仅可以做大量的计算,还能进行复杂的 推理。 ? 于是就把它同人的大脑进行比较,提出“计算机 能思维吗(Can machines think? )”的问题。 ? 这里涉及到对“什么是思维”的理解和界定,涉 及哲学、认知学以及社会学等各个方面,相当复 杂众说纷纭,很难有一个统一的标准。 43 图灵测试 ? 图灵1950年10月在英国曼彻斯特大学发表 论文“计算机和智能”,巧妙地把这个问 题转化为一种可操作的方法,那就是测试。 后来被称为图灵测试。 ? 简单说就是与其争论什么是“思维”,不 如我们去做实验测试。计算机通过了测试 就说该计算机能思维,否则就说还达不到 思维的水平。 44 图灵测试的设计 ? 测试分测试人员和被测 试方两部分。被测试方 由A和B构成,A和B分别 是一个人和一台被测试 的计算机。测试人员和 被测试方是分开的,测 试人员并不知道A和B那 个是人那个是计算机。 ? A ? B 45 通过测试被认为是能够思维的 ? 测试人员分别向A和B提问, 如果测试人员能够通过问题 的回答,分不出A和B谁是机 器谁是人,那这个机器就通 过图灵测试。 ? 图灵指出:“如果机器在某 些条件下,能够非常好地模 仿人回答问题,以至提问者 在相当长时间里误认它不是 机器,那么机器就可以被认 为是能够思维的。” 46 图灵预言,50年内通过图灵测试 ? 当时的计算机根本无法通过这一测试。图灵预言, 50年内,即在20世纪末会有计算机通过图灵测试。 ? 图灵测试没有规定问题的范围和提问的标准,如 果想要制造出能通过试验的机器,必须在电脑中 储存人类所有可以想到的问题,储存对这些问题 的所有合乎常理的回答,并且还需要理智地作出 选择。 ? 这几乎是不可能的。到目前为止还没有电脑能通 过图灵测试。但是如果限制在一定的领域和范围 之内通过图灵测试是完全有可能的。 47 计算机深蓝战胜国际象棋冠军 ? 人工智能专家经过多年的 努力,开发了不少智能软 件,在理论和实践上取得 了很大的进步。 ? 1997年5月3-11日,IBM的 计算机深蓝(Deep Blue) 以2胜1负3平的成绩第一次 战胜国际象棋冠军卡斯帕 ? 自然,对于图灵测试的 理解以及它的作用等 罗夫大师。也可以说在一 方面,学界也有各种 定意义下实现了图灵的预 不同的争论。 言。 48 2208 年机器能识别出我是人! 49 8.图灵奖与对年轻人的期盼 ? 1966年,美国的国际计算机 学会ACM(Association for Computing Machinery)为 表彰图灵对计算机科学的伟 大贡献,设立了图灵奖(A. M. Turing Award)。 ? 每年一届,奖金25万美元,奖金由 Intel 和 Google公司提供。 50 计算机科学界的诺贝尔奖 ? 奖励在计算机科学研究中 做出创造性贡献,推动计 算机科学技术发展的杰出 科学家。 ? 选择条件要求很高,程序 极严,一直被公认是世界 计算机科学领域的最高荣 誉奖项,相当于计算机科 学界的诺贝尔奖。 51 图灵奖的得主 ? 1966-2010年已举行45届,有55名科学 家获此殊荣。 ? 许多著名的对计算机科学技术作出重大 贡献的科学家都是图灵奖的得主。 ? 获奖者的名单和他们一个个的贡献推介, 活生生地展现了几十年来计算机科学技 术发展的历程和辉煌成就的方方面面。 52 中国人的遗憾 ? 令我们中国人感到遗憾的是我们国 内培养成长的专家至今还没有一个 在获奖名单中出现。 ? 获图灵奖的唯一一位华人是2000年 得主姚期智博士(Chi-Chih Yao), ? 台湾大学毕业,在美国哈佛大学和伊利诺斯大学取 得博士学位,曾在美国著名的麻省理工学院、斯丹 佛大学、加州大学贝克莱分校任教,获奖时任美国 普林斯顿大学教授。现在海归聘为中国清华大学教 授。 53 对中国学者很大的期待, ? 我们国家的科学研究水平同国家的经济和 政治地位是不匹配的。希望在不远的将来 能够有我们自己培养的科学家做出重大的 贡献。 ? 1993年图灵奖得主米勒(Robin Milner):“中国,作为在世界 上发挥日益重要作用的大国, 具有引领为新技术建立科学基 础的机会 …。 ”《通信与移动系 统:π-演算》中译本(2009年出版)序 言。 54 结束语:寄希望于新一代年轻人 ? 外国人说出了我们中国 人的心声,这也正是我 们广大中国学者所日夜 期盼的。希望把机会变 为现实。 ? 实现这个愿望,也许要 经过几代人的不懈努力。 ? 寄希望于新一代年轻人。 55 推荐阅读 ? 苹果CEO乔布斯2005在斯坦福大学的演讲稿 56 求知若饥,虚心若愚。 史蒂夫?乔布斯: Steven Paul Jobs (1955.2.24-2011.10.5) ? 你们的时间很有限, 所以不要将它浪费 在重复其它人的生 活上。 ? Stay Hungry. Stay Foolish. 57 电子邮件个人网页 科学网博客

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!