算法设计与分析附录图灵-巨星辉耀新编.ppt

2002-3-27 纪玉波制作(C)1图灵-巨星辉耀 1936 年, 阿兰· 图灵( Alan Turing 1912-1954) 向伦敦权威的数学杂志投了一篇论文,题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中, 图灵给“可计算性”下了一个严格的数学定义,并提出著名的图灵机“( Turing Machine ) 的设想。“图灵机”不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算装置,用来计算所有能想像得到的可计算函数。“图灵机”与“”齐名,被永远载入计算机的发展史中。 1950 年10 月,图灵又发表了另一篇题为“机器能思考吗”的论文,成为划时代之作。也正是这篇文章,为图灵赢得了“人工智能之父”的桂冠。 2002-3-27 纪玉波制作(C)2 英国现代计算机的起步是从德国的密码电报机- -Enigma ( 谜)开始的,而解开这个谜的不是别人, 正是阿兰· 图灵,一个在计算机界响当当的人物, 可与美国的冯· 诺依曼相媲美的电脑天才。在他短暂的生涯中,图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究,在晚年还开创了一门新学科--非线性力学。图灵英年早逝。在他 42 年的人生历程中,他的创造力是丰富多彩的,他是天才的数学家和计算机理论专家。 24 岁提出图灵机理论, 31 岁参与 COLOSSUS 的研制, 33 岁设想仿真系统, 35 岁提出自动程序设计概念, 38 岁设计" 图灵测验" 。这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。特别是在 60 年代后形成的人工智能新领域中, 图灵的理论观点具有重大的科学价值。 2002-3-27 纪玉波制作(C)3 当然,图灵最高的成就还是在电脑和人工智能方面,他是这一领域开天辟地的大师。为表彰他的贡献,专门设有一个一年一度的“图灵奖”,颁发给最优秀的电脑科学家。这枚奖章就像“诺贝尔奖”一样,为计算机界的获奖者带来至高无上的荣誉。而阿兰· 图灵本人,更被人们推崇为人工智能之父,在计算机业十倍速变化的历史画卷中永远占有一席之地。他的惊世才华和盛年夭折,也给他的个人生活涂上了谜一样的传奇色彩。阿兰· 图灵, 1912 年6月23 日出生于英国伦敦。其祖父曾获得剑桥大学数学荣誉学位,但他父亲的数学才能平平。因此,图灵的家庭教育,对他以后在数学及计算机方面的成就并没有多少帮助。 2002-3-27 纪玉波制作(C)4 小时侯的图灵生性活泼好动,很早就表现出对科学的探索精神。据他母亲回忆, 3岁时,小图灵就进行了他的首次实验,尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里,等待长出更多的木头人。到了8岁,他更开始尝试写一部科学著作,题目为《关于一种显微镜》。在这部很短的书中,天才儿童图灵拼错了很多单词,句法也有些问题,但写得还能让人看懂,很像那么一回事儿。在书的开头和结尾,他都用同一句话“首先你必须知道光是直的”作前后呼应, 但中间的内容却很短,短得破了科学著作的记录。图灵曾说:“我似乎总想从最普通的东西中弄出些名堂”。就连和小朋友们玩足球,他也能放弃当前锋进球这样出风头的事,只喜欢在场外巡边,因为这样能有机会去计算球飞出边界的角度。他的老师认为: “图灵的头脑思维可以像袋鼠一样进行跳跃。” 2002-3-27 纪玉波制作(C)5 图灵是个天才。他 16岁就开始研究爱因斯坦的相对论。 1931 年,图灵考入剑桥大学国王学院,开始他的数学生涯,研究量子力学、概率论和逻辑学。在校期间,图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴趣。数理逻辑的创建,主要是为了对付“悖论”。“悖论”( paradox) 是人类思维中最狡猾的两面派,最早起源于古希腊克里特岛上有个叫爱皮梅尼特的“智者”,他说: “所有的克里特岛人都说谎”。我们可以把它简化为: “我说的这句话是假话”。这就出现一种两面都无法自圆的怪圈:如果他没有说谎, 那他这句话是错的,他是在说谎;如果他真的在说谎, 那他说自己在说谎是对的,所以他又没有说谎。罗素和怀特海把它从逻辑、集合论以及数论中驱逐出去, 最后又想尽办法归入《数学原理》之中。 2002-3-27 纪玉波制作(C)6 图灵一上大学,就迷上了《数学原理》。在 1931 年,著名的" 哥德尔定理" 出现后该定理认为没有一种公理系统可以导出数论中所有的真实命题,除非这种系统本身就有悖论),天才的图灵在数理逻辑大本营的剑桥大学提出一个设想:能否有这样一台机器,通过某种一般的机械步骤, 能在原则上一个接一个地解决所有的数学问题。大学毕业后,图灵去美国普林斯顿大学攻读博士学位,还顺手发明过一个解码器。在那里, 他遇见了冯· 诺依曼,后者对他的论