图灵与图灵机的故事

苹果电脑公司的标志是一个被吃了一口的苹果以纪念伟大的计算科学先驱：图灵。

【概述】

阿兰•麦席森•图灵（AlanMathisonTuring，1912.6.23—1954.6.7），英国数学家、逻辑学家，他被视为计算机之父。1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。

1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(TuringMachine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。“图灵机”与“冯•诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。

【生平】

◆故事从谜开始

英国现代计算机的起步是从德国的密码电报机——Enigma(谜)开始的，而解开这个谜的不是别人，正是阿兰•图灵，一个在计算机界响当当的人物，可与美国的冯•诺依曼相媲美的电脑天才。在他短暂的生涯中，图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究，在晚年还开创了一门新学科——非线性力学。

图灵英年早逝。在他42年的人生历程中，他的创造力是丰富多彩的，他是天才的数学家和计算机理论专家。24岁提出图灵机理论，31岁参与COLOSSUS的研制，33岁设想仿真系统，35岁提出自动程序设计概念，38岁设计“图灵测验”。这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。特别是在60年代后当然，图灵最高的成就还是在电脑和人工智能方面，他是这一领域开天辟地的大师。为表彰他的贡献，专门设有一个一年一度的“图灵奖”，颁发给最优秀的电脑科学家。这枚奖章就像“诺贝尔奖”一样，为计算机界的获奖者带来至高无上的荣誉。而阿兰•图灵本人，更被人们推崇为人工智能之父，在计算机业十倍速变化的历史画卷中永远占有一席之地。他的惊世才华和盛年夭折，也给他的个人生活涂上了谜一样的传奇色彩。

◆神童图灵

图灵1912年6月23日出生于英国伦敦。其祖父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平平。因此，图灵的家庭教育，对他以后在数学及计算机方面的成就并没有多少帮助。小时候的图灵生性活泼好动，很早就表现出对科学的探索精神。据他母亲回忆，3岁时，小图灵就进行了他的首次实验，尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里，等待长出更多的木头人。到了8岁，他更开始尝试写一部科学著作，题目为《关于一种显微镜》。在这部很短的书中，天才儿童图灵拼错了很多单词，句法也有些问题，但写得还能让人看懂，很像那么一回事儿。在书的开头和结尾，他都用同一句话“首先你必须知道光是直的”作前后呼应，但中间的内容却很短，短得破了科学著作的记录。图灵曾说：“我似乎总想从最普通的东西中弄出些名堂。”就连和小朋友们玩足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这样能有机会去计算球飞出边界的角度。他的老师认为：“图灵的头脑思维可以像袋鼠一样进行跳跃。”图灵是个天才。他16岁就开始研究爱因斯坦的相对论。1931年，图灵考入剑桥大学国王学院，开始他的数学生涯，研究量子力学、概率论和逻辑学。在校期间，图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴趣。数理逻辑的创建，主要源于古希腊克里特岛上有个叫爱皮梅尼特的“智者”，他说：“所有的克里特岛人都说谎”。我们可以把它简化为：“我说的这句话是假话”。这就出现一种两面都无法自圆的怪圈：如果他没有说谎，那他这句话是错的，他是在说谎；如果他真的在说谎，那他说自己在说谎是对的，所以他又没有说谎。罗素和怀特海把它从逻辑、集合论以及数论中驱逐出去，最后又想尽办法归入《数学原理》之中。

图灵一上大学，就迷上了《数学原理》。在1931年，著名的“哥德尔定理”出现后(该定理认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论)，天才的图灵在数理逻辑大本营的剑桥大学提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。大学毕业后，图灵去美国普林斯顿大学攻读博士学位，还顺手发明过一个解码器。在那里，他遇见了冯•诺依曼，后者对他的论文击节赞赏，并随后由此提出了“存储程序”概念。图灵学成后又回到他的母校任教。在短短的时间里，图灵就发表了几篇很有份量的数学论文，为他赢得了很大的声誉。

◆怪才图灵

在剑桥，图灵可称得上是一个怪才，一举一动常常出人意料。他是个单身汉和长跑运动员。在他的同事和学生中间，这位衣着随便、不打领带的著名教授，不善言辞，有些木讷、害羞，常咬指甲，但他更多地以自己杰出的才智赢得了人们的敬意。图灵每天骑自行车上班，因为患过敏性鼻炎，一遇到花粉，就会鼻涕不止，大打喷嚏。于是，他就常常在上班途中戴防毒面具，招摇过市，这早已成为剑桥的一大奇观。图灵的自行车经常半路掉链子，但他就是不肯去车铺修理。每次骑车时，他总是嘴里念念有词，在心里细细计算，这链条也怪，总是转到一定的圈数就滑落了，而图灵竟然能够做到在链条下滑前一刹那停车，让旁观者佩服不已，以为图灵在玩杂技。后来图灵又居然在脚踏车旁装了一个小巧的机械记数器，到圈数时就停，歇口气换换脑子，再重新运动起来。

1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(TuringMachine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的工作带(起存储器的作用)组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。这篇论文在纸上谈了一把兵，创造出一个“图灵机”来。但现代通用电脑确实是用相应的程序来完成任何设定好的任务。这一理论奠定了整个现代计算机的理论基础。“图灵机”更在电脑史上与“冯•诺依曼机”齐名，被永远载入计算机的发展史中。

图灵机理论不仅解决了纯数学基础理论问题，一个巨大的“意外”收获则是，理论上证明了研制通用数字计算机的可行性。虽然早在100年前的1834年，巴贝奇(CharkBabbage，1792～1871)就设计制造了“分析机”以说明具体的数字计算，但他的失败之处是没能证明“必然可行”。图灵机理论不仅证明了研制“通用机”的可行性，而且比世界上第一台由德国人朱斯(K•Zuze)于1941年制造的通用程序控制计算机Z-3整整早5年。这不得不使人惊叹这一理论的深刻意义。

◆谜语图灵

正当图灵的理论研究工作进一步深入时，战争爆发了。他被派往布雷契莱庄园承担“超级机密”研究。当时的布雷契莱庄园是一所“政府密码学校”，即战时的英国情报破译中心。在这座幽静的维多利亚式建筑里，表面上鸟语花香、人迹罕见，其实每天都有12000多名志愿者在这里夜以继日地工作，截获、整理、破译德国的军事情报，有些结果甚至直达丘吉尔首相本人手中。在这里，图灵被人们称为“教授”，没有人知道他的真名。当时德国有一个名为“Enigma”（谜）的通信密码机，破译高手们绞尽脑汁也难以破解。这个难题交到了图灵手中，他率领着大约200多名精干人员进行密码分析，其中甚至还包括象棋冠军亚历山大。分析和计算工作非常复杂，26个字母在“Enigma”机中能替代8万亿个谜文字母。如果改动接线，变化会超过2.5千万亿亿。最后多亏波兰同行们提供了一台真正的“Enigma”，图灵才凭借着他的天才设想设计出一种破译机。这台机器主要由继电器构成，还用了80个电子管，由光电阅读器直接读入密码，每秒可读字符2000个，运行起来咔嚓咔嚓直响。它被图灵戏称为“罗宾逊”，至今没人能搞懂图灵究竟如何指挥它工作。但"罗宾逊"的确神通广大，在它的密报下，德国飞机一再落入圈套，死无葬身之地。

1945年，图灵带着大英帝国授予的荣誉勋章，来到英国国家物理研究所担任高级研究员。两年后，图灵写了一份内部报告，提出了"自动程序"的概念，但由于英国政府严密、死板的保密法令，这份报告一直不见天日。1969年，美国的瓦丁格(Woldingger)发表了同样成果，英国才连忙亮出压在箱底的宝贝，终于在1970年给图灵的报告“解密”。图灵的这份报告后来收入爱丁堡大学编的《机器智能》论文集中。由于有了布雷契莱的经验，图灵提交了一份“自动计算机”的设计方案，领导一批优秀的电子工程师，着手制造一种名叫ACE的新型电脑。它大约用了800个电子管，成本约为4万英镑。1950年，ACE电脑就横空出世，开始公开露面，为感兴趣的人们玩一些“小把戏”，赢得阵阵喝彩。图灵在介绍ACE的内存装置时说：“它可以很容易把一本书的10页内容记住。”显然，ACE是当时世界上最快、最强劲的电子计算机之一。

1946年，在纽曼博士的动议下，皇家学会成立电脑实验室。纽曼博士是皇家学会会员，又是当年破译小组的成员，正是他对“赫斯•鲁宾逊”的制造起了关键作用。皇家学会的这一新实验室不在伦敦，而是设在曼彻斯特大学，由纽曼博士牵头负责。1946年7月，研制基金到位，纽曼博士开始招募人选。阿兰•图灵也在次年9月加盟电脑实验室。一时间，曼彻斯特大学群英会萃。实验室设在一幢维多利亚时代的老房子里，条件十分简陋，但因图灵他们的到来，也算是蓬荜生辉了。在1948年6月，这里造出了一台小的模型机，大家都爱叫它“婴儿”(Baby)。这台模型机用阴极射线管来解决存储问题，能存储32个字，每一字有32位字长。这是第一台能完全执行存储程序的电子计算机的模型。

◆大师图灵

到了1949年10月，各项改进工作都已展开，夹在两层存储器之间的自动控制系统已正常运转，并能在程序的控制下，实现磁鼓和阴极射线管存储单元间信息交互。图灵设计出一些协同电路来做输入和输出的外设。有关电动打字设备也是图灵通过老关系从他战时供职的外交部通信部门弄过来的，其中甚至包括一个战后从德国人那里收缴来的穿孔纸带键盘。这样，整个模型机已大功告成。在整个试验阶段，大家忙上忙下。1949年底，模型机交付给曼彻斯特当地的一家叫弗兰尼蒂(Ferranti)的电子公司，开始正式建造。1951年2月完工，通称“迈可1型”。它有4000个电子管，72000个电阻器，2500个电容器，能在0.1秒内开平方根、求对数和三角函数的运算。比起先前的模型机，“迈可1型”功能更为齐全，静电存储器的内存容量已翻倍，能存256个40位字长字，分别存在8个阴极射线管中，而磁鼓的容量能扩容到16384个字，真是一项了不起的工程。

与冯•诺依曼同时代的富兰克尔(Frankel，冯氏同事)在回忆中说：冯•诺依曼没有说过"存储程序"型计算机的概念是他的发明，却不止一次地说过，图灵是现代计算机设计思想的创始人。当有人将"电子计算机之父"的头衔戴在冯•诺依曼头上时，他谦逊地说，真正的计算机之父应该是图灵。当然，冯•诺依曼问之无愧，而图灵也有“人工智能之父”的桂冠。他俩是计算机历史浩瀚星空中相互映照的两颗巨星。

早在1945年，图灵就提出“仿真系统”的思想，并有一份详细的报告，想建造一台没有固定指令系统的电脑。它能够模拟其他不同指令系统的电脑的功能，但这份报告直到1972年才公布。这说明图灵在二战结束后就开始了后来被称为“人工智能”领域的探索，他开始关注人的神经网络和电脑计算之间的关联。

1950年，图灵又来到曼彻斯特大学任教，同时还担任该大学自动计算机项目的负责人。就在这一年的十月，他又发表了另一篇题为《机器能思考吗？》的论文，成为划时代之作。也正是这篇文章，为图灵赢得了一顶桂冠——“人工智能之父”。在这篇论文里，图灵第一次提出“机器思维”的概念。他逐条反驳了机器不能思维的论调，做出了肯定的回答。他还对智能问题从行为主义的角度给出了定义，由此提出一假想：即一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力，即这台计算机是能思维的。这就是著名的“图灵测试”(TuringTesting)。当时全世界只有几台电脑，根本无法通过这一测试。但图灵预言，在本世纪末，一定会有电脑通过“图灵测试”。终于他的预言在IBM的“深蓝”身上得到彻底实现。当然，卡斯帕罗夫和“深蓝”之间不是猜谜式的泛泛而谈，而是你输我赢的彼此较量。

◆故事以谜结束

1951年，图灵以他杰出的贡献被当选为英国皇家学会会员。就在他事业步入辉煌之际，灾难降临了。1952年，图灵遭到警方拘捕，原因是他是一个同性恋者。与其他一些智慧超群的人物一样，图灵在个人生活方式上也“与众不同”。当时，人们对同性恋还没有像现在这样宽容，而是把这种行为当作一桩伤风败俗的罪孽。事情的败露是这样的，当时有一位叫琼•克拉克(JoanClarke)的姑娘爱上了图灵，图灵也对对方很有好感，并向对方求婚，琼欣然接受。但不久，图灵自己退缩了，告诉琼，他是同性恋者。在1948年，图灵就由于同性恋倾向，离开了当时属于高度保密的英国国家物理实验室(NPL)。但也有人说，图灵是被英国军事情报部门“开除”出去的，对于这位天才的离去，许多人怅惜不已。

1952年3月31日，图灵更因为和曼彻斯特当地一位青年有染，被警方逮捕。在法庭上，图灵既不否认，也不为自己辨解。在庄严的法庭上，他郑重其事地告诉人们：他的行为没有错，结果被判有罪。在入狱和治疗两者中间，图灵选择了注射激素，来治疗所谓的“性欲倒错”。此后图灵开始研究生物学、化学，还和一位心理医生有很深的交往。那时，他的脾气已变得躁怒不安，性格更为阴沉怪僻。1953年3月，他因为接待过一位被英国警方注意的挪威客人，成为警方的目标，甚至去希腊度假时也被跟踪。

1954年6月8日，图灵42岁，正逢进入他生命中最辉煌的创造顶峰。一天早晨，女管家走进他的卧室，发现台灯还亮着，床头上还有个苹果，只咬了一小半，图灵沉睡在床上，一切都和往常一样。但这一次，图灵是永远地睡着了，不会再醒来……经过解剖，法医断定是剧毒氰化物致死，那个苹果是在氰化物溶液中浸泡过的。图灵的母亲则说他是在做化学实验时，不小心沾上的，她的"艾伦"从小就有咬指甲的习惯。但外界的说法是服毒自杀，一代天才就这样走完了人生。

【图灵奖】

“图灵奖”是美国计算机协会（ACM，AssociationforComputerMachinery）于1966年设立的，专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家。设立的初衷是因为计算机技术的飞速发展，尤其到20世纪60年代，其已成为一个独立的有影响的学科，信息产业亦逐步形成，但在这一产业中却一直没有一项类似“诺贝尔”、“普利策”等的奖项来促进该学科的进一步发展，为了弥补这一缺陷，于是“图灵”奖便应运而生，它被公认为计算机界的“诺贝尔”奖。

图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图灵奖由Google公司赞助，奖金为100,000美元。

每年，美国计算机协会将要求提名人推荐本年度的图灵奖候选人，并附加一份200到500字的文章，说明被提名者为什么应获此奖。任何人都可成为提名人。美国计算机协会将组成评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。

截止至2005年，获此殊荣的华人仅有一位，他是2000年图灵奖得主姚期智。

【图灵机】

1936年，阿兰•图灵提出了一种抽象的计算模型──图灵机(TuringMachine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；

把注意力从纸的一个位置移动到另一个位置；

而在每个阶段，人要决定下一步的动作，依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0,1,2,...，纸带的右端可以无限伸展。

一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。