【MD作业】图灵(Alan Turing)

简介

艾伦·麦席森·图灵(英语: Alan Mathison Turing,1912年6月23日--1954年6月7日)，英国数学家，逻辑学家，被称为计算机科学之父，人工智能之父。

生平

• 1912年6月23日，艾伦·麦席森·图灵生于英国帕丁顿。

• 1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金，在剑桥，他的数学能力得到充分的发展。1935年，他的第一篇数学论文“左右殆周期性的等价”发表于《伦敦数学会杂志》上。同年，他还写出“轮高斯误差函数”一文。这一论文使他由一名大学生直接当选为国王学院的研究员，并于次年荣获英国著名的史密斯数学奖，成为国王学院声名显赫的毕业生之一。

• 1936年5月，图灵写出了表述他的最重要的数学成果的论“论可计算数及其在判定问题中的应用”，该文于1937年在《伦敦数学会文集》第42期上发表后，立即引起广泛的注意。文中，他分析了计算的过程，给出了理论上可计算任何“可计算序列”----某种0和1的序列----的“通用”计算机概念，并利用这一概念解决了D.希尔伯特提出的一个著名的判定问题。1937年，图灵发表的另一篇文章“可计算性与λ可定义性”则拓广了丘奇提出的“丘奇论点”，形成“丘奇-图灵论点”，对计算机理论的严格化，对计算机科学得形成和发展都具有奠基性的意义。

• 1936年9月，图灵应邀到美国普林斯顿高级研究员学习，并与丘奇一起工作，在美国期间，他对群论做了一些研究，并撰写了博士论文，1983年在普林斯顿获得博士学位，其论文题目为“以序数为基础的逻辑系统”，1939年正式发表，在数理逻辑研究中产生了深远的影响。

• 1938年夏，图灵回到英国，仍在剑桥大学国王学院任研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制工作，第二次世界大战打断了他的正常研究工作，1939年秋，他应召到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作，他的工作取得了极好的成就，因而于1945年获政府的最高奖——大英帝国荣誉勋章(O.B.E.勋章)。人们认为，通用计算机的概念就是图灵提出来的。

• 1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作，具体研制出新的计算机来，这一想法得到当局的支持。同年，图灵被录用为泰丁顿国家物理研究所的研究人员，开始从事“自动计算机”的逻辑设计和具体研制工作。这一年，图灵写出一份长达50页的关于ACE的设计说明书。这一说明书在保密了27年之后，于1972年正式发表。在图灵的设计思想指导下，1950年制出了ACE样机，1958年制成大型ACE机。

• 1948年，图灵接受了曼彻斯特大学的高级讲师职务，并被指定为曼彻斯特自动数字计算机项目的负责人助理，具体领导该项目数学方面的工作。作为这一工作的总结，1950年图灵编写并出版了《曼彻斯特电子计算机程序员手册》这期间，他继续进行数理逻辑方面的理论研究。

• 早在1947年，图灵就提出过自动程序设计的思想，1950年，他提出关于机器思维的问题，他的论文“计算机和智能，引起了广泛的注意和深远的影响。1956年，在收入一部文集时此文改名为“机器能够思维吗？”，至今仍是研究人工智能的首选读物之一。

• 1951年，图灵当选为英国皇家学会会员。1952年，他辞去剑桥大学国王学院研究员的职务，专心在曼彻斯特大学工作。除了日常工作和研究工作之外，他还指导一些博士研究生，还担任了制造曼彻斯特自动数字计算机的一家公司——弗兰蒂公司—的顾问。

• 图灵少年时就形成的对自然科学的兴趣一直使他乐于思考自然科学问题，40年代末他表现出对生物学的浓厚兴趣，1951年，他写成长篇专论“形态形成的化学基础”于次年发表，他利用数学工具深刻地阐释了生物形态和生物化学的问题，对生物数学的发展起了直接的推动作用。

• 图灵思想活跃，但性格较内向，他爱好体育，在剑桥上学时就当过赛艇划手，40年代以后更把长跑当作主要的锻炼和休息形式。他在国家物理学研究所的运动会上得过1英里跑和3英里跑的冠军；还得过3英里跑的俱乐部冠军；1947年，他参加了英国业余体联举办的马拉松冠军赛并进入了前15名，此时他已名扬四海，报纸上称他为“电子运动员”，图灵终身未婚。

• 1952年，图灵被判犯有“严重猥亵罪”，随后被迫接受了化学阉割。他因与一名19岁的男子交往而被捕。

• 1954年6月7日，艾伦·麦席森·图灵在曼彻斯特去世。

• 2009 年，时任首相戈登·布朗代表英国政府就 “他(图灵)所受的骇人听闻的对待方式” 作出正式道歉。

• 2013年12月24日，在英国司法大臣克里斯·格雷灵的要求下，英国女王伊丽莎白二世向图灵颁发了皇家赦免。

主要贡献

可计算理论

图灵把可计算函数定义为图灵机可计算函数。1937年，图灵在他的“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法(能行)可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数。这就是“丘奇-图灵论点”，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用。

图灵机的概念有十分独特的意义：如果把图灵机的内部状态解释为指令，用字母表的字来表示，与输出字输入字同样存贮在机器里，那就成为电子计算机了，由此开创了“自动机”这一学科分支，促进了电子计算机的研制工作。

与此同时，图灵还提出了通用图灵机的概念，它相当于通用计算机的解释程序，这一点直接促进了后来通用计算机的设计和研制工作，图灵自己也参加了这一工作。

在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决。这种思想开启了后来计算机科学中计算复杂性理论的先河。

判定问题

所谓“判定问题”指判定所谓“大量问题”是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质(如是否真，是否可满足或是否有解等，随大量问题本身的性质而定)的问题。

图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如果问题A可判定，则停机问题可判定。”从而由“停机问题是不可判定的”推出“问题A是不可判定的”。

1937年，图灵用他的方法解决了著名的希尔伯特判定问题：狭谓词演算(亦称一阶逻辑)公式的可满足性的判定问题。他用一阶逻辑中的公式对图灵机进行编码，再由图灵机停机问题的不可判定性推出一阶逻辑的不可判定性。他在此处创用的“编码法”成为后来人们证明一阶逻辑的公式类的不可判定性的主要方法之一。

在判定问题上，图灵的另一成果是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”及相对递归的概念。运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较。在此基础上，E.波斯特(Post)提出了不可解度这一重要概念，这方面的工作后来有重大的进展。

图灵参与解决的另一个著名的判定问题是“半群的字的问题”，它是图埃(Thue)在1914年提出来的：对任意给定的字母表和字典，是否存在一种算法能判定两个任意给定的字是否等价［给出有限个不同的称为字母的符号，便给出了字母表，字母的有限序列称为该字母表上的字。把有限个成对的字(A1，B1)，…，(An，Bn)称为字典。如果两个字R和S使用有限次字典之后可以彼此变换，则称这两个字是等价的］1947年，波斯特和A.A.马尔科夫(Markov)用图灵的编码法证明了这一问题是不可判定的。1950年，图灵进一步证明，满足消元律的半群的字的问题也是不可判定的。

电子计算机

电子计算机的出现和广泛应用是20世纪新技术革命的主要标志之一。很长时期中人们一直认为，第一台电子计算机是美国人按J.W.莫奇利(Mauchly)提出的方案于1946年制成的“电子数字积分和自动计算机”(ENIAC)。图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，但此项工作严格保密。直到70年代，内情才有所披露。从一些文件来看，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的CO-LOSSUS(巨人)机，这台机器的设计采用了图灵提出的某些概念。它用了1500个电子管，采用了光电管阅读器；利用穿孔纸带输入；并采用了电子管双稳态线路，执行计数、二进制算术及布尔代数逻辑运算，巨人机共生产了10台，用它们出色地完成了密码破译工作。

1945年初，冯诺伊曼、莫奇利等人提出了著名的EDVAC［electronic discret variable automatic comp-uter(离散变量自动电子计算机)］方案，提出关于存贮程序控制的电子计算机的总体设想，指出这种计算机应由计算器、控制器、存贮器及输入、输出装置等五个部分组成(后来形成了左右电子计算机40余年的所谓“冯诺伊曼方式”)，但没有提出进一步的结构设计。1945年底图灵写出的关于ACE的设计说明书中，最先给出了存贮程序控制计算机的结构设计(图灵后来参与研制的Madam机则是当时世界上存贮量最大的电子计算机)。在图灵的这份说明书中还最先提出了指令寄存器和指令地址寄存器的概念，提出了子程序和子程序库的思想，这都是现代电子计算中最基本的概念和思想。令人吃惊的是，在这份说明书中，图灵已提出了“仿真系统”的思想，所谓仿真系统，指机器可以没有固定的指令系统，但它能够模拟许多具有不同指令系统的计算机的功能。英国的ACE机只采用了图灵的部分思想，而出于保密的需要，图灵的ACE设计说明书，直到1972年才得以发表。这期间，人们不得不重新发现图灵已经发现过的东西，恰恰也是在1972年，人们才制成具有仿真系统的计算机。

人工智能

图灵是人工智能研究的先驱者之一，实际上，图灵机，尤其是通用图灵机作为一种非数值符号计算的模型，就蕴含了构造某种具有一定的智能行为的人工系统以实现脑力劳动部分自动化的思想，这正是人工智能的研究目标。而且正是从图灵机概念出发，在第二次世界大战时的军事工作期间，图灵在业余时间里经常考虑并与一些同事探讨“思维机器”的问题，并且进行了“机器下象棋”一类的初步研究工作。[2]

1950年，图灵发表了著名的“计算机和智能”的论文。这篇文章对智能给出一个行为主义的定义，并设计了著名的“图灵测验”，即一个人在不接触对象的情况下，同对象进行一系列的问答(可借助电传打写机)，如果他根据这些问答无法判断对象是人还是计算机，那么就可以认为这个计算机具有同人相当的智力，图灵还预言，20世纪末将会出现这样的机器。1956年图灵的这篇文章以“机器能够思维吗？”为题重新发表。此时，人工智能也进入了实践研制阶段。图灵的机器智能思想无疑是人工智能的直接起源之一。而且随人工智能领域的深入研究，人们越来越认识到图灵思想的深刻性：它们至今仍然是人工智能的主要思想之一。

图灵奖

为了纪念他对计算机科学的巨大贡献，由美国计算机协会（ACM）于1966年设立一年一度的图灵奖，以表彰在计算机科学中做出突出贡献的人，图灵奖被喻为“计算机界的诺贝尔奖”。