02小说网

第五课 普林斯顿大学名人榜人工智能之父阿兰图灵（第1页）

第五课普林斯顿大学名人榜——人工智能之父阿兰·图灵

大学名言

成就是谦虚者前进的阶梯，也是骄傲者后退的滑梯。

人物履历

阿兰·麦席森·图灵（1912—1954），英国著名数学家、逻辑学家，被称为计算机科学之父、人工智能之父。1912年6月23日生于英国帕丁顿，1931年进入剑桥大学国王学院，师从著名数学家哈代，1938年在美国普林斯顿大学取得博士学位，二战爆发后返回剑桥，曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。1954年6月7日在曼彻斯特去世。他是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而专门设立了“图灵奖”。

成长经历

图灵的父亲朱利斯·麦席森·图灵（JuliusMathis）是一名英属印度的公务员。1911年，图灵的母亲埃塞尔在印度的杰德拉布尔怀了孕。

他们希望阿兰在英国出生，所以回到伦敦，住在帕丁顿（Paddington）。结果就在那里生下了阿兰。父亲的公务员委任使他在阿兰小时候经常来往于英伦和印度。由于担心印度的气候不利于儿童成长，他把家庭留在英伦与朋友同住。图灵很小的时候就表现出他的天才，后来就更加显著。他说他在三个星期里自己学会阅读，而且，就对数字和智力游戏着迷。

6岁的时候，他的父母为他在一间叫圣迈克尔的（St。Michael's）日间学校注了册。女校长很快就注意到他的天才，随后Marlbh学院的许多教育家也注意到这点。1926年，他14岁的时候转到了在多塞特郡（Dorset）的舍伯恩（Sherborne）寄宿学校。开学的第一天，刚好遇上了大罢工。图灵决心要赶上第一天的课，于是他独自从南安普顿（Southampton）骑了60英里（37公里）的自行车去上学，途中还在一间旅社度过一宵。

图灵天生对科学的喜好并没有给他在舍伯恩的老师留下好印象。他们对教育的定义是着重于人文学科而不是科学。虽然如此，图灵继续在他喜欢的学科表现出惊人的能力，还没有学过基础微积分的他，就已经能够解答以他年纪来说算是很高深的难题。1928年，在图灵16岁的时候，开始阅读阿尔伯特·爱因斯坦的著作。他不但能够理解，而且看出了爱因斯坦对牛顿运动定律存有质疑，即使爱因斯坦的著作中并没有明白指出这点。

科研时期

1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金。在剑桥，他的数学能力得到充分的发展。1935年，他的第一篇数学论文“左右周期性的等价”发表于《伦敦数学会杂志》上。同一年，他还写出“论高斯误差函数”一文。这一论文使他由一名大学生直接当选为国王学院的研究员，并于次年荣获英国著名的史密斯（Smith）数学奖，成为国王学院声名显赫的毕业生之一。1936年5月，图灵写出了表述他的最重要的数学成果的论文“论可计算数及其在判定问题中的应用”，该文于1937年在《伦敦

数学会杂志》第42期上发表后，立即引起广泛的注意。

1937年，阿兰·麦席森·图灵发表的另一篇文章“可计算性与λ可定义性”则拓广了丘奇（Church）提出的“丘奇论点”，形成“丘奇一图灵论点”，对计算理论的严格化，对计算机科学的形成和发展都具有奠基性的意义，1936年9月，阿兰·麦席森·图灵应邀到美国普林斯顿高级研究院学习，并与丘奇一同工作。在美国期间，他对群论作了一些研究，并撰写了博士论文，1938年在普林斯顿大学获博士学位，其论文题目为“以序数为基础的逻辑系统”，1939年正式发表，在数理逻辑研究中产生了深远的影响。

1938年夏，阿兰·麦席森·图灵回到英国，仍在剑桥大学国王学院任研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制工作。第二次世界大战打断了他的正常研究工作，1939年秋，他应召到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。他在布莱奇利庄园（BletchleyPark）利用工具Bombe破译德军的密码“谜（Enigma）”，并参与了世界上最早的电子计算机的研制工作。他的工作取得了极好的成就，因而于1945年获政府的最高奖——大英帝国荣誉勋章。人们认为，通用计算机的概念就是阿兰·麦席森·图灵提出来的。1945年，阿兰·麦席森·图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作，具体研制出新的计算机来。这一想法得到当局的支持，同年，图灵被录用为泰丁顿（Teddington）国家物理研究所的研究人员，开始从事“自动计算机”（ACE）的逻辑设计和具体研制工作。

这一年，图灵写出一份长达50页的关于ACE的设计说明书。这一说明书在保密了27年之后，于1972年正式发表。在图灵的设计思想指导下，1950年制出了ACE样机，1958年制成大型ACE机。1948年，图灵接受了曼彻斯特大学的高级讲师职务，并被指定为曼彻斯特自动数字计算机（Madam）项目的负责人助理，具体领导该项目数学方面的工作。作为这一工作的总结，1950年图灵编写并出版了《曼彻斯

特电子计算机程序员手册》。这期间，他继续进行数理逻辑方面的理论研究。早在1947年，图灵就提出过自动程序设计的思想，1950年，他提出关于机器思维的问题，他的论文“计算机和智能（adintelligence），引起了广泛的注意和深远的影响。

1956年，在收入一部文集时此文改名为“机器能够思维吗?”，至今仍是研究人工智能的首选读物之一。1951年，图灵当选为英国皇家学会会员。1952年，他辞去剑桥大学国王学院研究员的职务，专心在曼彻斯特大学工作。除了日常工作和研究工作之外，他还指导一些博士研究生，还担任了制造曼彻斯特自动数字计算机的一家公司——弗兰蒂公司的顾问。1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究群根据图灵的理论，在MANIAC上设计出世界上第一个电脑程序的象棋。

可计算性理论与图灵机

在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来。似乎正是为了证明一切科学命题，至少是一切数学命题存在算法，莱布尼茨（Leibniz）开创了数理逻辑的研究工作。但是20世纪初，人们发现有许多问题已经过长期研究，仍然找不到算法，例如希尔伯特第10问题，半群的字的问题等。于是人们开始怀疑，是否对这些问题来说，根本就不存在算法，即它们是不可计算的。这种不存在性当然需要证明，这时人们才发现，无论对算法还是对可计算性，都没有精确的定义。1934年，哥德尔（Godel）在埃尔布朗（Herbrand）的启示下提出了一般递归函数的概念，并指出：凡算法可计算函数都是一般递归函数，反之亦然。

1936年，克林（Kleene）又加以具体化。因此，算法可计算函数的一般递归函数定义后来被称为埃尔布朗·哥德尔·克林定义。同年，丘奇证明了他提出的λ可定义函数与一般递归函数是等价的，并提出算法可计算函数等同于一般递归函数或λ可定义函数，这就是著名的“丘奇论点”，用一般递归函数虽给出了可计算函数的严格数学定义，但在具体的计算过程中，就某一步运算而言，选用什么初始函数和基本运算仍有不确定性。为消除所有的不确定性，艾伦·麦席森·图灵在他的“论可计算数及其在判定问题中的应用”一文中从一个全新的角度定义了可计算函数，他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械的程序都可以归约为这些动作。这种简单的方法是以一个抽象自动机概念为基础的，其结果是：算法可计算函数就是这种自动机能计算的函数。这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，对后世产生了巨大的影响，这种“自动机”后来被人们称为“图灵机”。图灵在他的重要论文《论可计算数及其在判定问题上的应用》（1936年5月28日提交）里，对哥德尔1931年在证明和计算的限制的结果作了重新论述，他用现在叫作图灵机的简单形式装置代替了哥德尔的以通用算术为基础的形式语言。由于速度很慢，尽管没有一台图灵机会有实际用途，图灵还是证明了这样的机器有能力解决任何可想象的数学难题，如果这些难题是用一种算法来表达。

现今，图灵机还是计算理论研究的中心课题。他继续证明了判定问题是没有答案的。他的证明首先展示了图灵机的停机问题（haltingproblem）是没有答案的，这是说不可能用一个算法来决定一台指定的图灵机是否会停机。尽管他的证明比阿隆佐·丘奇在λ演算方面相等的证明晚发表了几个月，图灵的著作是更易于理解和直观的。他的通用（图灵）机的概念也是新颖的。这一通用机能够完成任何其他机器所能做的任务。图灵机是一种自动机的数学模型，它是一条两端（或一端）无限延长的纸带，上面划成方格，每个方格中可以印上某字母表中的一个字母；又有一个读写头，它具有有限个内部状态。任何时刻读写头都注视着纸带上的某一个方格，并根据注视方格的内容以及读写头当时的内部状态而执行变换规则所规定的动作。每个图灵机都有一组变换规则，它们具有下列三种形状之一：qiaRqi，qiaLqi，qiabqj意思是：当读写头处于状态qi时如果注视格的内容为字母a则读写头右移一格，或左移一格，或印下字母b（即把注视格的内容由a改成b。a，b可为so）。

艾伦·麦席森·图灵把可计算函数定义为图灵机可计算函数，1937年，阿兰·麦席森·图灵在他的“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数。这就是“丘奇-图灵论点”，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用。图灵机的概念有十分独特的意义：如果把图灵机的内部状态解释为指令，用字母表的字来表示，与输出字输入字同样存贮在机器里，那就成为电子计算机了。由此开创了“自动机”这一学科分支，促进了电子计算机的研制工作。在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决。这种思想开启了后来计算机科学中计算复杂性理论的先河。

判定问题

所谓“判定问题”指判定所谓“大量问题”是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质的问题。艾伦·麦席森·图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如果问题A可判定，则停机问题可判定。”从而由“停机问题是不可判定的”推出“问题A是不可判定的”。所谓停机指图灵机内部达到一个结果状态、指令表上没有的状态或符号对偶，从而导致计算终止。

在每一时刻，机器所处的状态，纸带上已被写上符号的所有格子以及机器当前注视的格子位置，统称为机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局，此最终格局就包含机器的计算结果。所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机?图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础。