图灵：谜样的计算机科学之父

从二十世纪后半开始，电子计算机对人类文明产生惊天动地的变革，一个「信息时代」的文明阶段已经正式展开。把作为计算机理论创始者的图灵称为「计算机科学之父」，应该是恰当的。

我认为艾伦‧麦昔森‧图灵（Alan MathisonTuring，图一）是二十世纪对人类文明最有影响的科学家之一，不过我也要声明，这样的评价也许还没有得到普遍的认同。但是我确信随着时代的推进，图灵在科学史上的地位会日渐崇隆。

图一：图灵（A.M. Turing, 1912～54）

在电子计算机还没有制造出来的时候，图灵把计算机的原理与能力极限，都已经界定分析清楚。他的思想深深影响了计算机科学的发展轨迹，也成为人工智能研究的动力。从二十世纪后半开始，电子计算机对人类文明产生惊天动地的变革，一个「信息时代」的文明新阶段已经正式展开，虽然前景充满了难以预料的因素，但是人类有信心期待一个乐观的未来。把作为计算机理论创始者的图灵称为「计算机科学之父」，应该算是恰当的。

苍白少年

图灵在一九一二年六月二十三日诞生于伦敦，他的父亲当时在英属印度任公务员，而母亲也出身于居住在印度的英国中上层家庭。因此图灵在十四岁他父亲从印度退休返乡前，就一直和哥哥寄养在一些英国本土家庭。成长在这种比较缺乏亲情的环境里，对图灵的性格造成某些负面的影响。他有轻微的口吃，又难和别人打成一片，而且凡事自己料理，机乎有些离群索居的倾向。

图灵在学校里的表现平平，他只喜欢课外做一些简单的化学实验。后来勉强挤进一所培养社会中坚份子的所谓「公学校」(Public School)，在十六岁时认识了学长克里斯多福‧牟康 (ChristopherMorcom)。他深受牟康的吸引，也刺激他发展沟通与竞争的技能。但是在一九三○年二月牟康突然不幸过世，图灵非常受打击，有三年时间他写信给牟康的母亲，说他常常思考人的心灵，特别像牟康的心灵，如何能嵌入肉身？死后是不是能从物质中脱离开来？

一九三一年图灵进入剑桥大学国王学院就读，次年他学习了冯诺依曼 (J. von Neumann) 研究量子力学逻辑基础的新著，使他逐渐学会严格思维的求知方式。然而也就是在国王学院的环境里，他的同性恋倾向日渐明显，这对他日后的人生造成重大的影响。

判定可算

一九三三年图灵自习罗素 (B. Russell) 与怀特海 (A.N. Whitehead) 的巨作《数学原理》(PrincipiaMathematica)，开始进军数理逻辑的领域。罗素与怀特海准备为数学的真理寻求一个严谨的基础，而逻辑正是他们想用来达成目标的利器。虽然他们作出开创性的贡献，但是逻辑的形式体系如何承载数学的真理，并没有得到满意的解决。出乎当时许多专家的预料，一九三一年刚出道的哥德尔 (K.Gödel) 彻底粉碎了罗素等人的美梦。他著名的「不完备定理」证明在任何无矛盾的形式数论系统里，一定找得到真命题，它自已以及它的否定命题，都无法依据系统里的推理法则，得到形式的证明。简单来说，就是任何无矛盾的逻辑系统，从本质上没有能力捕捉人类所能理解的全部数学真理。

一九三五年图灵由剑桥拓朴学家纽曼 (M.H.A. Newman) 的讲课中知道，虽然有哥德尔的出人意料的结果，但是希尔伯特 (D. Hilbert) 所提的另一个相关问题却仍然没有解决。所谓「判定性 (decidability) 问题」（德文原名是 Entscheidungs problem）是要问有没有明确的方法，至少在原则上能判定任何给定的命题，可否在初阶逻辑系统里得到证明。

要回答这个问题，必须先清楚而具说服性地界定什么是「明确的方法」。图灵舍弃一般逻辑学家用各种推理系统规范方法的思路，采用了一种截然不同的途径，最终得以用否定的答案解决「判定性问题」。他在一九三六年四月告诉纽曼自己的结果，但得知美国著名逻辑学家丘奇 (A. Church) 已经宣布解决了「判定性问题」，图灵不幸丧失了发现的优先权。图灵把他得到的结果写成〈论可计算数及其在判定性问题上之应用〉("OnComputable Numbers, with an Application to the Entscheidungsproblem", 以下简称〈可计算数〉）一文，在该年五月送交《符号逻辑学报》(Journal ofSymnbolic Logic)，而在十一月号（其实是次年一月）正式刊登发表。

图灵虽然没有得到第一名，但〈可计算数〉是一篇画时代的巨著，其内容的深刻以及对后世的影响，都超越与覆盖了丘奇的成果。图灵在这篇论文中至少有三项极重要的创见：

(一)发明与定义一种抽象的计算机；

(二)证明万用计算机 (universal machine) 的存在性；

(三)证明存在有任何计算机都不能解决的问题。

图灵机器

图灵面对的首要问题是，有哪些可能的程序可用来计算一个数？他采取的途径是：

(一)仔细分析我们的直观，从而定义出合适的计算机；

(二)证明别人尝试过的方法和他的方法等价，但是他的方法更接近直观；

(三)给出大量各式各样的数，证明它们在新的意义下是可以计算的。

在分析直观方面，图灵解析一位计算者的状态，（他称为 computer 那时电子计算机尚未问世。）从中抽离出最本质的要素，然后模拟定义一个理论的计算机。这个机器能变换的状态是有限的，因为图灵认为计算者的心灵不应该有无穷多状态，否则有些状态会任意接近，以致无法区分其间的差异。机器具备一条要多长就有多长的纸带，纸带画分成一个个小方格。另外有有限个符号，用以写在小方格上来记录计算过程。机器在每一刻的动作，取决于当时机器的状态与所扫瞄的小方格上的符号。机器的基本动作包括：

(一) 在小方格上写一个符号，如果原来已经有符号，就把那个符号遮掉；

(二) 擦掉原来写在小方格上的符号；

(三) 把纸带向左或向右移动一格。

图灵定义理论计算机的方法有相当大的弹性，如果采取一些变化并不会影响可以计算的范围，因此现在把这一类的理论计算机都称为图灵机器（Turing machine，下文简称图灵机，图二）。乍看起来令人怀疑这么简单的计算工具能算多少东西？当然从如此原始的基础出发，要想计算日常使用的数学对象，必然会经过冗长的步骤。但图灵的重点不在要花多少精力，而在可不可能做到。最终图灵以极具说服力的论证让人相信，所有可计算的数都能用图灵机计算。

图二：图灵机器 (Turing machine)。

在了解其计算机功能的过程中，图灵体会到定义一个计算机的方法也是机械性的，因此可以用符号记录下来。如此便能定义一个所谓的万用计算机，它可以模拟任何其他图灵机的计算过程。万用计算机把想模拟的图灵机的定义符号当作输入吃进来，然后在想要计算的输入值上，一方面解读被仿真机器的指令，一方面依样画葫芦执行，最后得出同样的结果。万用图灵机赋予当代存储程序 (stored program) 电子计算机的理论基础，使得人类在机械发明史上，首次有可能利用软件的变化，大量扩充硬件的使用效率。

当我们深刻体认出图灵机的威力时，我们会产生一个跟刚开始时态度相反的问题：还有什么是图灵机不可能计算的呢？当我们启动图灵机开始计算某个输入值时，最怕的是它一直运作不停，老是给不出答案而抵达停机的最终状态。图灵机的定义方法，并不保证每次计算都会在有限时间内完成。于是我们很自然便想知道，有没有可能造一个特殊的图灵机，来判断任何图灵机一旦在任何输入值上开动，是否计算最后会停止。这就是所谓的「停机问题」 (halting problem)。因为所有的图灵机可以有效地、机械化地逐一列队，图灵便得以使用对角线论证法 (diagonalargument) 证明不可能存在这种特殊的图灵机，也就是说「停机问题」是无解的，再从这里就可以继续推论出「判定性问题」也是无解的。

图灵机的正面应用绝不局限在可计算数的范围，事实上，通过各种编码的程序，可以想象的任何机械化演算过程，似乎原则上都可以在图灵机上执行。因此有人主张一切可计算的均是图灵机可计算的，这也就是一般所谓的「丘奇－图灵论点」(Church-TuringThesis)。不过随着人类对高速及大量计算的经验累积，这个论点也有重新检讨的需求了。

图灵机的定义，从「认识」的心理图像上来说，最接近直观的机械性运算特性。经过后人的继续开拓，引入计算复杂度的考虑，终于发现计算机理论内最核心也最困难的「P=NP?」问题。因此图灵的贡献超越其他的逻辑学家，成为计算机科学的始祖。

破解密码

一九三六年九月图灵渡海到美国普林斯敦大学读研究所，他在十二月时公开演讲他的计算理论，但是几乎没什么人来听讲。

当〈可计算数〉刊出时，也没有引起大家的重视，只有两个人向他索取抽印本。到一九三八年六月图灵在丘奇指导下获得了博士学位。因为图灵怀念剑桥大学的环境，他辞谢了冯诺依曼邀请他担任助理的机会，也拒绝了他父亲的建议，要他留在美国回避希特勒渡海攻击英伦的危险，他毅然决然地返回国王学院。图灵除了从理论上研究计算机外，他也喜欢动手操作机具。他在普林斯顿时，就曾尝试制作用继电器乘二进制数的密码机。回到英国后，图灵更秘密参加了政府破解密码部门的工作。

一九三九年九月三日英国正式对纳粹德国宣战，破解德国军事密码的任务愈发重要与迫切。特别是德国潜舰在大西洋上横行，而德国海军使用代号「谜语」(Enigma) 的密码系统号称不可破解，造成盟军非常大的威胁。最终图灵因为他在计算理论的经验，以及统计方法的巧妙运用，成功地破解了「谜语」系统。德国人在不知情的状况下，军事通讯彻底曝光，很快失去了大西洋的制海权。因为快速破解密码的需求，英国情报部门加强研制电子的计算机具。图灵不仅开始学习电子方面的技术，并且暗地里计划制造一台电子的万用图灵机，也就是真正的现在所谓的电子计算机。

二次世界大战后，美国方面由于冯诺依曼的积极推动，开始电子计算机的研制。英国受到这种发展的刺激。也在一九四六年以图灵的设计为基础，成立了「自动计算引擎」（AutomaticComputing Engine，简称 ACE）计划。虽然图灵在计划里担任首席科学家，也开创了一些包括程序语言设计的新想法，但是他对工程方面毫无影响力，结果 ACE 计划完全泡汤。此时图灵当年的老师纽曼在曼彻斯特大学建立基地，并且从皇家学会谋得一笔巨款制造计算机。纽曼请了一位雷达工程师威廉斯 (F.C. Williams)，帮他实现图灵式的存储程序计算机，而在一九四八年六月成功地让图灵的构想变成实物。

人工智能

图灵担任计算机实验室的副主任，但是图灵没有实权。因为当时英国政府急于发展计算机，用在制造原子弹的任务上，所以威廉斯趁势打造自己的王国，把纽曼原来的方案凉在一边。而图灵大才小用，只能做些杂七杂八的事。不过在这一片混乱中，图灵于一九五○年发表了一篇思虑清晰的哲学论文：〈计算机械与智能〉 (ComputingMachinery and Intelligence)，是人工智能研究上，一篇具历史性的文献。

图灵讨论的问题是如何分析机器会不会思想，他采取的方法不是思辩性的分析，而是建议一种可操作的评判标准。他提出所谓的模仿游戏 (Imitation Game) 来分析计算机的思考水平，这个游戏的布局如下：在一个房间里安置一台计算机和一位助理，在另一个房间里有一位询问者。询问者分别与计算机及助理以通讯管道连接起来，并且利用键盘敲击出荧光幕上的文字交谈。

询问者事先并不知道哪一个通话的对象是计算机，他用各种各样的问题查探二者的真实，游戏终结时询问者要决定哪一个是计算机。在游戏过程中，计算机尽量要让询问者猜不出自己的真实身份，而助理的作用在协助询问者做出正确的判断。现在一般称呼这种类型的游戏为图灵测试 (Turing test)，如果计算机能以高成功率瞒骗过询问者，我们就可以说计算机已有人脑思维的功能。

图灵自己很乐观地认为在二十世纪末，计算机的功能已经强大到多数人不能否认它有思考能力。但是目前电子计算机的功能，虽然已经发挥到连图灵也不见得想象得出的地步，然而定期在世界各地举行的图灵测验比赛，至今仍然无法让计算机展现接近人的思考能力。不过图灵的想法与信心不仅刺激了人工智能的研究，也使心理学产生变革，更间接催生了当代的认知科学。人脑到底是不是计算机，也成为研究人类心灵与意识上争论不休的问题。

天妒英才

图灵在曼彻斯特安居下来，他开始对生物成长时形态的变化感觉兴趣。他认为化学反应与扩散的非线性方程式，会导致对称的起始形态，逐渐成长出不对称的复杂面貌。他似乎也是最先把计算机引入数学研究的人，他使用计算机的数值仿真，观察他所假设的化学反应。一九五一年他因为图灵机的贡献当选皇家学会院士，他同时发表了另一项高度原创性的论文〈形态发生的化学基础〉(The ChemicalBasis of Morphogenesis)。这又是一篇超前时代太多的杰作，虽然当时并未引起什么注意，但是现在看来，它却是当今炙手可热的非线性动力学的开山工作之一。

一九五二年三月图灵因为他的男伴偷了东西潜逃，报警后反而被警方送上法庭审判，因为那个年代同性恋在英国还算是犯罪的。图灵不愿做任何辩护，也不认为自己的行为有错。他面对法庭给他的两种选择，坐牢或是接受荷尔蒙矫正时，他宁愿挑后者。但是这种粗暴的处理方法，不仅使图灵戏说自己快长出了乳房，其实更严重的是已经搅乱了他的心灵。

图灵本来还继续秘密地帮英国情报机构工作，但是冷战时期的严峻环境，使得同性恋者无法通过安全检查，图灵也因而被判出局。他那种不太符合一般社会规矩的行为模式，更是让安全单位放心不下。一九五四年六月八日，去他家里打扫的清洁工发现图灵已经长眠不醒，他的床边还留有咬了一半的苹果。虽然验尸结果说是服氰化物自杀，他母亲坚信图灵又在搞化学实验，不小心把残留手上的药物沾在苹果上吃进了肚子，现在更有人怀疑图灵说不定是冷战时期保密防谍的牺牲品。

图灵一生的际遇并未与他的贡献成正比，哥德尔比他更孤僻，但是生前就获得显赫的名声，也不像他英年早逝。除了有皇家学会院士的头衔外，图灵没有在学术的权力核心逗留过，更没有交往多少学术权贵。虽然在逻辑与计算机科学的领域里，他死后较快获得肯定，美国计算机协会 (Association forComputing Machinery) 从一九六六年起设立图灵奖，做为对计算科学有贡献人士的最高奖项。但是直到一九八三年另一位同性恋的牛津数学家安德鲁．哈吉斯 (Andrew Hodges)，替他写了一本脍炙人口的传记《谜样的图灵》(Alan Turing: The Enigma)，英美大众才对他有较全貌的认识。以这本书为蓝图的舞台剧「破解密码」(Breaking theCode)，于一九八六至八八年在英美两地上演，也相当轰动，深受人们喜爱。此外，英国 BBC 更于一九九六年把它拍成电影。2014年，好莱坞拍摄《模仿游戏》（The Imitation Game），由大家熟悉的卷福（本尼迪克特·康伯巴奇）出演图灵。

一九九八年六月二十二日，英国下议院通过修改法条，使得十六岁以上同性或异性间的自愿性行为均属合法。第二天，图灵诞生的房子正式被指定为英国的历史遗产，哈吉斯在揭开纪念碑仪式的献词里，替图灵的人生作了一句最好的结语：「法律会杀人，但是精神赋予生命。」 (the law killsbut the spirit gives life.)