图灵

图灵
孙宏安
(江宁师范大学)
　
　　图灵，A．M．(Turing，Alan Mathison)1912年6月23日生于英国伦敦；1954年6月7日卒于英国威姆斯洛(Wilmslow)．数学、数理逻辑、计算机科学．
　　图灵的父亲J．M．图灵早年就读于牛津大学科帕斯克斯蒂学院历史系，后来从政，被派往印度，担任民政部的官员．图灵的母亲E．S．斯托尼(Stoney)生于一个铁路工程师家庭，曾就读于巴黎大学文理学院．图灵是他们的次子．
　　图灵的父亲在印度工作，母亲也常去印度，孩子们经常住在一位朋友家中．图灵少年时就表现出独特的直觉创造能力和对数学的爱好．1926年，他考入伦敦有名的舍本(Sherborne)公学，受到良好的中等教育．他在中学期间表现出对自然科学的极大兴趣和敏锐的数学头脑．1927年末，年仅15岁的图灵为了帮助母亲理解A．爱因斯坦(Einstein)的相对论，写了爱因斯坦的一部著作的内容提要，表现出他已具备非同凡响的数学水平和科学理解力．他对自然科学的兴趣使他在1930年和1931年两次获得他的一位同学C．莫科姆(Morcom)的父母设立的自然科学奖，获奖工作中有一篇论文题为“亚硫酸盐和卤化物在酸性溶液中的反应”(The reaction of sulphurous salt upon halogenide in acidsolution)，受到政府派来的督学的赞赏．对自然科学的兴趣为他后来的一些研究奠定了基础．他的数学能力使他在念中学时获得过国王爱德华六世数学金盾奖章．
　　1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金．在剑桥，他的数学能力得到充分的发展．1935年，他的第一篇数学论文“左右殆周期性的等价”(Equivalence on leftand right almost Priodicity)发表于《伦敦数学会杂志》(J．Loud．Math．Soc．)上．同一年，他还写出“论高斯误差函数”(On theGaussian error unction)一文．这一论文使他由一名大学生直接当选为国王学院的研究员，并于次年荣获英国著名的史密斯(Smith)数学奖，成为国王学院声名显赫的毕业生之一．
　　1936年5月，图灵写出了表述他的最重要的数学成果的论文“论可计算数及其在判定问题中的应用”(On computable numbers，with an application to the Entscheidungsproblem)，该文于1937年在《伦敦数学会文集》(Proc．Loud．Math．Soc．)第42期上发表后，立即引起广泛的注意．文中，他分析了计算的过程，给出了理论上可计算任何“可计算序列”——某种0和1的序列——的“通用”计算机概念，并利用这一概念解决了D．希尔伯特(Hil-lbert)提出的一个著名的判定问题．1937年，图灵发表的另一篇文章“可计算性与λ可定义性”(Computability andλ-definability)则拓广了A．丘奇(Church)提出的“丘奇论点”，形成“丘奇-图灵论点”，对计算理论的严格化，对计算机科学的形成和发展都具有奠基性的意义．
　　1936年9月，图灵应邀到美国普林斯顿高级研究院学习，并与丘奇一同工作．在美国期间，他对群论作了一些研究，并撰写了博士论文，1938年在普林斯顿获博士学位，其论文题目为“以序数为基础的逻辑系统”(Systems of logic based on ordinals)， 1939年正式发表，在数理逻辑研究中产生了深远的影响．
　　1938年夏，图灵回到英国，仍在剑桥大学国王学院任研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制工作．第二次世界大战打断了他的正常研究工作，1939年秋，他应召到英国外交部通信处从事军事工作，主要是破译敌方密码的工作．由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作．他的工作取得了极好的成就，因而于1945年获政府的最高奖——大英帝国荣誉勋章(O．B．E．勋章)．人们认为，通用计算机的概念就是图灵提出来的．
　　1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作，具体研制出新的计算机来．这一想法得到当局的支持．同年，图灵被录用为泰丁顿(Teddington)国家物理研究所的研究人员，开始从事“自动计算机”(ACE)的逻辑设计和具体研制工作．这一年，图灵写出一份长达50页的关于ACE的设计说明书(Proposals for developmentin the mathematlcs divison of an ACE)．这一说明书在保密了27年之后，于1972年正式发表．在图灵的设计思想指导下，1950年制出了ACE样机，1958年制成大型ACE机．
　　1948年，图灵接受了曼彻斯特大学的高级讲师职务，并被指定为曼彻斯特自动数字计算机(Madam)项目的负责人助理，具体领导该项目数学方面的工作．作为这一工作的总结，1950年图灵编写并出版了《曼彻斯特电子计算机程序员手册》(The programmers’handbook for the Manchester electronic computer)．这期间，他继续进行数理逻辑方面的理论研究．
　　早在1947年，图灵就提出过自动程序设计的思想，1950年，他提出关于机器思维的问题，他的论文“计算机和智能(Computingmachiery and intelligence)，引起了广泛的注意和深远的影响．1956年，在收入一部文集时此文改名为“机器能够思维吗？”(Cana machine think？)，至今仍是研究人工智能的首选读物之一．
　　1951年，图灵当选为英国皇家学会会员．1952年，他辞去剑桥大学国王学院研究员的职务，专心在曼彻斯特大学工作．除了日常工作和研究工作之外，他还指导一些博士研究生，还担任了制造曼彻斯特自动数字计算机的一家公司——弗兰蒂公司(Ferran-ti’S)——的顾问．
　　图灵少年时就形成的对自然科学的兴趣一直使他乐于思考自然科学问题．40年代末他表现出对生物学的浓厚兴趣，1951年，他写成长篇专论“形态形成的化学基础”(The chemical basis of morPhogenesis)于次年发表，他利用数学工具深刻地阐释了生物形态和生物化学的问题，对生物数学的发展起了直接的推动作用．
　　图灵思想活跃，但性格较内向．他爱好体育，在剑桥上学时就当过赛艇划手，40年代以后更把长跑当作主要的锻炼和休息形式．他在国家物理学研究所的运动会上得过1英里跑和3英里跑的冠军；还得过3英里跑的俱乐部冠军；1947年，他参加了英国业余体联举办的马拉松冠军赛并进入了前15名，此时他已名扬四海，报纸上称他为“电子运动员”．图灵终身未婚．1954年6月7日，图灵可能由于偶然事故——氰化钾中毒卒于威姆斯洛他自己的寓所中．
　　图灵在科学、特别在数理逻辑和计算机科学方面，取得了举世瞩目的成就，他的一些科学成果，构成了现代计算机技术的基础．
　　1．可计算性理论
　　计算，可以说是人类最先遇到的数学课题，并且在漫长的历史年代里，成为人们社会生活中不可或缺的工具．那么，什么是计算呢？直观地看，计算一般是指运用事先规定的规则，将一组数值变换为另一(所需的)数值的过程．对某一类问题，如果能找到一组确定的规则，按这组规则，当给出这类问题中的任一具体问题后，就可以完全机械地在有限步内求出结果，则说这类问题是可计算的．这种规则就是算法，这类可计算问题也可称之为存在算法的问题．这就是直观上的能行可计算或算法可计算的概念．
　　在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来．似乎正是为了证明一切科学命题，至少是一切数学命题存在算法，G．W．莱布尼茨(Leibniz)开创了数理逻辑的研究工作．但是20世纪初，人们发现有许多问题已经过长期研究，仍然找不到算法，例如希尔伯特第10问题，半群的字的问题等．于是人们开始怀疑，是否对这些问题来说，根本就不存在算法，即它们是不可计算的．这种不存在性当然需要证明，这时人们才发现，无论对算法还是对可计算性，都没有精确的定义！按前述对直观的可计算性的陈述，根本无法作出不存在算法的证明，因为“完全机械地”指什么？“确定的规则”又指什么？仍然是不明确的．实际上，没有明确的定义也不能抽象地证明某类问题存在算法，不过存在算法的问题一般是通过构造出算法来确证的，因而可以不涉及算法的精确定义问题．
　　解决问题的需要促使人们不断作出探索．1934年，K．哥德尔(Godel)在J．埃尔布朗(Herbrand)的启示下提出了一般递归函数的概念，并指出：凡算法可计算函数都是一般递归函数，反之亦然．1936年，C．克林(Kleene)又加以具体化．因此，算法可计算函数的一般递归函数定义后来被称为埃尔布朗-哥德尔-克林定义．同年，丘奇证明了他提出的λ可定义函数与一般递归函数是等价的，并提出算法可计算函数等同于一般递归函数或λ可定义函数，这就是著名的“丘奇论点”．
　　用一般递归函数虽给出了可计算函数的严格数学定义，但在具体的计算过程中，就某一步运算而言，选用什么初始函数和基本运算仍有不确定性．为消除所有的不确定性，图灵在他的“论可计算数及其在判定问题中的应用”一文中从一个全新的角度定义了可计算函数．他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械(能行)的程序都可以归约为这些动作．这种简单的方法是以一个抽象自动机概念为基础的，其结果是：算法可计算函数就是这种自动机能计算的函数．这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，对后世产生了巨大的影响，这种“自动机”后来被人们称为“图灵机”．
　　图灵机是一种自动机的数学模型，它是一条两端(或一端)无限延长的纸带，上面划成方格，每个方格中可以印上某字母表中的一个字母(亦可为空格，记为S0)；又有一个读写头，它具有有限个内部状态．任何时刻读写头都注视着纸带上的某一个方格，并根据注视方格的内容以及读写头当时的内部状态而执行变换规则所规定的动作．每个图灵机都有一组变换规则，它们具有下列三种形状之一：
qiaRqi，qiaLqi，qiabqj．
　　意思是：当读写头处于状态qi时如果注视格的内容为字母a则读写头右移一格，或左移一格，或印下字母b(即把注视格的内容由a改成b．a，b可为S0)．
　　图灵把可计算函数定义为图灵机可计算函数．1937年，图灵在他的“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法(能行)可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数．这就是“丘奇-图灵论点”，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用．
　　图灵机的概念有十分独特的意义：如果把图灵机的内部状态解释为指令，用字母表的字来表示，与输出字输入字同样存贮在机器里，那就成为电子计算机了．由此开创了“自动机”这一学科分支，促进了电子计算机的研制工作．
　　与此同时，图灵还提出了通用图灵机的概念，它相当于通用计算机的解释程序，这一点直接促进了后来通用计算机的设计和研制工作，图灵自己也参加了这一工作．
　　在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决．这种思想开启了后来计算机科学中计算复杂性理论的先河．
　　2．判定问题
　　所谓“判定问题”指判定所谓“大量问题”是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质(如是否真，是否可满足或是否有解等，随大量问题本身的性质而定)的问题．
　　判定问题与可计算性问题有密切的联系，二者可以相互定义：对一类问题若能找到确定的算法以判定其是否具有某种性质，则称这类问题是能行可判定的，或可解的；否则是不可判定的，或不可解的．二者又是有区别的：判定问题是要确定是否存在一个算法，使对一类问题的每一个特例都能对某一性质给以一个“是”或“否”的解答；可计算性问题则是找出一个算法，从而求出一些具体的客体来．
　　图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如果问题A可判定，则停机问题可判定．”从而由“停机问题是不可判定的”推出“问题A是不可判定的”．
　　所谓停机指图灵机内部达到一个结果状态、指令表上没有的状态或符号对偶，从而导致计算终止．在每一时刻，机器所处的状态，纸带上已被写上符号的所有格子以及机器当前注视的格子位置，统称为机器的格局．图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列．此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机．在结束状态下停机所达到的格局是最终格局，此最终格局(如果存在)就包含机器的计算结果．所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机？图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础．
　　1937年，图灵用他的方法解决了著名的希尔伯特判定问题：狭谓词演算(亦称一阶逻辑)公式的可满足性的判定问题．他用一阶逻辑中的公式对图灵机进行编码，再由图灵机停机问题的不可判定性推出一阶逻辑的不可判定性．他在此处创用的“编码法”成为后来人们证明一阶逻辑的公式类的不可判定性的主要方法之一．
　　在判定问题上，图灵的另一成果是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”及相对递归的概念．运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较．在此基础上，E．波斯特(Post)提出了不可解度这一重要概念，这方面的工作后来有重大的进展．
　　图灵参与解决的另一个著名的判定问题是“半群的字的问题”，它是A．图埃(Thue)在1914年提出来的：对任意给定的字母表和字典，是否存在一种算法能判定两个任意给定的字是否等价［给出有限个不同的称为字母的符号，便给出了字母表，字母的有限序列称为该字母表上的字．把有限个成对的字(A1，B1)，…，(An，Bn)称为字典．如果两个字R和S使用有限次字典之后可以彼此变换，则称这两个字是等价的］？1947年，波斯特和A．A．马尔科夫(Markov)用图灵的编码法证明了这一问题是不可判定的．1950年，图灵进一步证明，满足消元律的半群的字的问题也是不可判定的．
　　3．电子计算机
　　电子计算机的出现和广泛应用是20世纪新技术革命的主要标志之一．很长时期中人们一直认为，第一台电子计算机是美国人按J．W．莫奇利(Mauchly)提出的方案于1946年制成的“电子数字积分和自动计算机”(ENIAC)．图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，但此项工作严格保密．直到70年代，内情才有所披露．从一些文件来看，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的CO-LOSSUS(巨人)机，这台机器的设计采用了图灵提出的某些概念．它用了1500个电子管，采用了光电管阅读器；利用穿孔纸带输入；并采用了电子管双稳态线路，执行计数、二进制算术及布尔代数逻辑运算，巨人机共生产了10台，用它们出色地完成了密码破译工作．
　　1946年ENIAC投入运行，以它的计算速度(每秒5000次运算)而震惊了世界．但是在它未完工之前，一些人，包括它的主要设计者就认识到，它的控制方式已不适用了：ENIAC并不是像现在的计算机那样用程序来进行控制，而是利用硬件即利用插线板和转换开关所连接的逻辑电路来控制运算．这样一来，这台机器固然可以在几分钟内作完极复杂的运算，但要改变一下运算题目，却要花十几小时甚至几十小时才能做好准备．因此，如何用程序自动控制运算就成为提高电子计算机效率的关键性问题．
　　1945年初，J．冯诺伊曼(von Neumann)、莫奇利等人提出了著名的EDVAC［electronic discret variable automatic comp-uter(离散变量自动电子计算机)］方案，提出关于存贮程序控制的电子计算机的总体设想，指出这种计算机应由计算器、控制器、存贮器及输入、输出装置等五个部分组成(后来形成了左右电子计算机40余年的所谓“冯诺伊曼方式”)，但没有提出进一步的结构设计．1945年底图灵写出的关于ACE的设计说明书中，最先给出了存贮程序控制计算机的结构设计(图灵后来参与研制的Madam机则是当时世界上存贮量最大的电子计算机)．在图灵的这份说明书中还最先提出了指令寄存器和指令地址寄存器的概念，提出了子程序和子程序库的思想，这都是现代电子计算中最基本的概念和思想．令人吃惊的是，在这份说明书中，图灵已提出了“仿真系统”的思想，所谓仿真系统，指机器可以没有固定的指令系统，但它能够模拟许多具有不同指令系统的计算机的功能．英国的ACE机只采用了图灵的部分思想，而出于保密的需要，图灵的ACE设计说明书，直到1972年才得以发表．这期间，人们不得不重新发现图灵已经发现过的东西，恰恰也是在1972年，人们才制成具有仿真系统的计算机．
　　4．人工智能
　　图灵是人工智能研究的先驱者之一，实际上，图灵机，尤其是通用图灵机作为一种非数值符号计算的模型，就蕴含了构造某种具有一定的智能行为的人工系统以实现脑力劳动部分自动化的思想，这正是人工智能的研究目标．而且正是从图灵机概念出发，在第二次世界大战时的军事工作期间，图灵在业余时间里经常考虑并与一些同事探讨“思维机器”的问题，并且进行了“机器下象棋”一类的初步研究工作．
　　1947年，图灵在一次关于计算机的会议上作了题为“智能机器”(intelligent machinery)的报告，详细地阐述了他关于思维机器的思想，第一次从科学的角度指出：“与人脑的活动方式极为相似的机器是可以制造出来的．”在该报告中，图灵提出了自动程序设计的思想，即借助证明来构造程序的思想．现在自动程序设计已成为人工智能的基本课题之一．图灵这一报告中的思想极为深刻、新奇，似乎超出了当时人们的想象力．1959年，这一报告编入图灵的著作选集首次发表时，似乎仍未引起人们的重视．只是当1969年，这一报告再次发表，人工智能已有了相当进展，尤其是R．J．瓦丁格(Waldingger)于1969年重新提出自动程序设计的概念，人们才开始理解了图灵这一报告的开创性意义．
　　1950年，图灵发表了著名的“计算机和智能”的论文．这篇文章对智能给出一个行为主义的定义，并设计了著名的“图灵测验”，即一个人在不接触对象的情况下，同对象进行一系列的问答(可借助电传打写机)，如果他根据这些问答无法判断对象是人还是计算机，那么就可以认为这个计算机具有同人相当的智力，图灵还预言，20世纪末将会出现这样的机器．1956年图灵的这篇文章以“机器能够思维吗？”为题重新发表．此时，人工智能也进入了实践研制阶段．图灵的机器智能思想无疑是人工智能的直接起源之一．而且随人工智能领域的深入研究，人们越来越认识到图灵思想的深刻性：它们至今仍然是人工智能的主要思想之一．
　　5．其他成果
　　图灵思想活跃，他的创造力也是多方面的．据同事们回忆，他在战时的秘密工作中，曾创造好几种新的统计技术，但都未形成论文发表，后来又重新为他人所创建，由A．瓦尔德(Wald)重新发现并提出的“序贯分析”就是其中之一．他对群论也有所研究．在“形态形成的化学基础”一文中，他用相当深奥而独特的数学方法，研究了决定生物的颜色或形态的化学物质(他称之为成形素)在形成平面形态(如奶牛体表的花斑)和立体形态(如放射形虫和叶序的分布方式)中的分布规律性，试图阐释“物理化学规律可以充分解释许多形态形成的事实”这一思想．在生物学界，80年代才开始探讨这一课题．图灵还进行了后来被称为“数学胚胎学”的奠基性研究工作．他还试图用数学方法研究人脑的构造问题，例如估算出一个具有给定数目的神经元的大脑中能存贮多少信息的问题等．这些，至今仍然是吸引着众多科学家的新颖课题．
　　人们认为，图灵是一位科学史上罕见的具有非凡洞察力的奇才：他的独创性成果使他生前就已名扬四海，而他深刻的预见使他死后倍受敬佩．当人们发现后人的一些独立研究成果似乎不过是在证明图灵思想超越时代的程度时，怎能不为他的英年早逝感到由衷的惋惜呢！为了纪念他对计算机科学的巨大贡献，美国计算机协会从60年代起设立一年一度的图灵奖，以表彰在计算机科学中做出突出贡献的人．