历史版本2:阿兰·图灵 返回词条

阿兰·图灵（Alan Turing 1912-1954）：人工智能之父

入选理由 阿兰·图灵，可与美国的冯·诺伊曼相媲美的电脑天才。在他短暂的生涯中，在量子力学、数理逻辑、生物学、化学方面都有深入的研究，在晚年还开创了一门新学科——非线性力学。他是天才的数学家和计算机理论专家。24岁提出图灵机理论，31岁参与COLOSSUS的研制，33岁设想仿真系统，35岁提出自动程序设计概念，38岁设计“图灵测验”。这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。当然，他最高的成就还是在电脑和人工智能方面，是这一领域开天辟地的大师。

姓名（中文） 阿兰·图灵
姓名（英文） Alan Turing
出生年月 1912年6月23日－1954年6月8日
出生国家、地点 英国伦敦
教育背景 1938年5月，在普林斯顿获得博士学位
1934年，获剑桥大学国王学院数学学士学位
职业背景 1951年，当选为英国皇家学会会员
1950年，到曼彻斯特大学任教
1947年，加入皇家学会电脑实验室
1945年，英国国家物理研究所担任高级研究员
1938年，恢复剑桥研究生院的学籍

阿兰·图灵（Alan Turing）这个名字无论是在计算机领域、数学领域、人工智能领域还是哲学、逻辑学等领域，都可谓“掷地有声”。图灵是计算机逻辑的奠基者，许多人工智能的重要方法也源自这位伟大的科学家。他在24岁时提出了图灵机理论，31岁参与了Colossus（二战时，英国破解德国通讯密码的计算机）的研制，33岁时构思了仿真系统，35岁提出自动程序设计概念，38岁设计了“图灵测试”，在后来还创造了一门新学科—非线性力学。虽然图灵去世时只有42岁，但在其短暂而离奇的生涯中的那些科技成就，已让后人享用不尽。人们仰望着这位伟大的英国科学家，把“计算机之父”、“人工智能之父”、“破译之父”等等头衔都加冕在了他身上，甚至认为，他在技术上的贡献及对未来世界的影响几乎可与牛顿、爱因斯坦等巨人比肩。

   

 英国现代计算机的起步是从德国的密码电报机——Enigma（谜）开始的，而解开这个谜的不是别人，正是阿兰•图灵，一个在计算机界响当当的人物，可与美国的冯•诺伊曼相媲美的电脑天才。在他短暂的生涯中，图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究，在晚年还开创了一门新学科——非线性力学。
    图灵英年早逝。在他42年的人生历程中，他的创造力是丰富多彩的，他是天才的数学家和计算机理论专家。24岁提出图灵机理论，31岁参与COLOSSUS的研制，33岁设想仿真系统，35岁提出自动程序设计概念，38岁设计“图灵测验”。这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。特别是在60年代后形成的人工智能新领域中，图灵的理论观点具有重大的科学价值。
    当然，他最高的成就还是在电脑和人工智能方面，是这一领域开天辟地的大师。为表彰他的贡献，专门设有一个一年一度的“图灵奖”，颁发给最优秀的电脑科学家。这枚奖章就象“诺贝尔奖”一样，为获奖者带来至高无上的荣誉。而阿兰•图灵本人，更被人们推崇为人工智能之父，在计算机业十倍速变化的历史画卷中永远占有一席之地。他的惊世才华和盛年夭折，也给他的个人生活涂上了谜一样的传奇色彩。
    图灵还是一位世界级的马拉松选手，最好成绩为2小时46分03秒，只比1948年奥运会冠军的成绩慢11分钟。在1948年的一个国内比赛中，他超过了曾经在奥运会上获得银牌的Tom Richards，获得冠军。

    阿兰•图灵，1912年6月23日出生于英国伦敦。其祖父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平平。因此图灵的家庭教育，对他以后在数学及计算机方面的成就并没有多少帮助。

   小时候的图灵生性活泼好动，很早就表现出对科学的探索精神。据他母亲回忆，3岁时，小图灵就进行了他的首次实验，尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里，等待长出更多的木头人。到了8岁，他更开始尝试写一部科学著作，题目为《关于一种显微镜》。在这部很短的书中，天才儿童图灵拼错了很多单词，句法也有些问题，但写得还能让人看懂，很像那么一回事儿。在书的开头和结尾，他都用同一句话“首先你必须知道光是直的”作前后呼应，但中间的内容却很短，短得破了科学著作的记录。图灵曾说：“我似乎总想从最普通的东西中弄出些名堂。”就连和小朋友们玩足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这样能够有机会计算球飞出边界的角度。他的老师认为：“图灵的头脑思维可以像袋鼠一样进行跳跃。”
    图灵对科学显现出明显的兴趣，他很早就在一个地下实验室开始琢磨干点什么了。在给母亲的信中，他写道：“我好像总想用自然界中最普通的东西，再通过最简单的方式制造点什么。”13岁的图灵进入瑟堡学校学习。他的老师说，图灵看上去非常邋遢。但他对化学、天文学、无线电和密码学的兴趣令人印象深刻。他无法适应学校的种种戒律。一方面，他的人文课程学习成绩极不理想；另一方面，他又在数理课程展现出才华。对他非同常人的表现，老师评价说，图灵在公立学校上学纯粹是浪费时间。此外，图灵还有一个小秘密，他在中学读书时有一个初恋情人，是他16岁的同学毛肯（Morcom）。图灵后来回忆说，他与毛肯相爱的两年时光，是一生中最幸福的日子。同样热爱科学的毛肯对图灵影响很大。毛肯在与图灵相恋两年后因病去世。但图灵认为毛肯的精神一直鞭策自己发愤努力。
    图灵是个天才。他16岁就开始研究爱因斯坦的相对论。1931年，图灵考入剑桥大学国王学院，开始他的数学生涯，研究量子力学、概率论和逻辑学。在校期间，图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。他对由剑桥大学的罗素和怀特海创立的数理逻辑很感冒。数理逻辑的创建，主要是为了对付“悖论”。

    “悖论”(parodox)是人类思维中最猾狡的两面派，最早起源于古希腊克里特岛上有个叫爱皮梅尼特的“智者”，他说：“所有的克里特岛人都说谎”。我们可以把它简化为：“我说的这句话是假话”。这就出现一种两面都无法自圆的怪圈：如果他没有说谎，那他这句话是错的，他是在说谎；如果他真的在说谎，那他说自己在说谎是对的，所以他又没有说谎。罗素和怀特海把它从逻辑、集合论以及数论中驱逐出去，最后又想尽办法归入《数学原理》之中。图灵一上大学，就迷上了《数学原理》。在1931年，著名的“哥德尔定理”出现后（该定理认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论），天才的图灵在数理逻辑大本营的剑桥大学提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个按一个地解决所有的数学问题。
    大学毕业后，图灵去美国普林斯顿大学攻读博士学位，还顺手发明过一个解码器。在那里，他遇见了冯•诺依曼，后者对他的论文击节赞赏，并随后由此提出了“存储程序”概念。图灵学成后又回到他的母校任教。在短短的时间里，图灵就发表了几篇很有分量的数学论文，为他赢得了很大的声誉。                   
    1946年长跑中的图灵      世界级的马拉松成绩（1947年8月25日《时代》周刊） 

    在剑桥，图灵可称得上是一个怪才，一举一动常常出人意料。他是个单身汉和长跑运动员。在他的同事和学生中间，这位衣着随便、不打领带的著名教授，不善言辞，有些木讷害羞，常咬指甲。图灵几乎没有什么朋友，从他自己来说，他只与那些和他智力相当的人交往；而对别人来说，图灵口吃的毛病，神经质的微笑以及古怪的生活方式使大家无法和他交谈。但他更多地以自己杰出的才智赢得了人们的敬意。他读书时的同窗还记得他不合规范的行为：骑车时在腰间挂一个闹钟，用来调整自己的速度。

    图灵常常不刮胡子，因为他害怕刮伤自己，而他见血就晕。图灵每天骑自行车上班，因为患过敏性鼻炎，一遇到花粉，就会鼻涕不止，大打喷嚏。他就常常在上班途中戴防毒面具，招摇过市，这早已成为剑桥的一大奇观。图灵的自行车经常半路掉链子，但他就是不肯去车铺修理。每次骑车时，他总是嘴里念念有词，在心里细细计算，这链条也怪，总是转到一定的圈数就滑落了。而图灵竟然能够做到在链条下滑前一刹那停车。让旁观者佩服不已，以为图灵在玩杂技。后来图灵又居然在脚踏旁装了一个小巧的机械记数器，到圈数时就停，歇口气换换脑子，再重新来过。
    1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想象得到的可计算函数。装置由一个控制器和一根假设两端无界的工作带（起存储器的作用）组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写头，可读出控制器所访问的格子上的符号，也能改写或抹去这一符号，最后便会得出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。这篇论文在纸上谈了一把兵，创造出一个“图灵机”来。但现代通用电脑确实是用相应的程序来完成任何设定好的任务。这一理论奠定了整个现代计算机的理论基础。“图灵机”更在电脑史上与“冯•诺伊曼机”齐名，被永远载入计算机的发展史中。
    图灵机理论不仅解决了纯数学基础理论问题，一个巨大的“意外”收获则是，理论上证明了研制通用数字计算机的可行性。虽然早在100年前的1834年，巴贝奇（Chark Babbage，1792～1871）就设计制造了“分析机”以说明具体的数字计算，但他的失败之处是没能证明“必然可行”。图灵机理论不仅证明了研制“通用机”的可行性，而且比世界上第一台由德国人朱斯（K•Zuze）于1941年制造的通用程序控制计算机Z－3整整早5年。这不得不使人惊叹这一理论的深刻意义。
    1938年5月，图灵在普林斯顿获得博士学位，当时他还不满26岁。他的学位论文被命名为“基于序数的逻辑系统”。当时的数学家冯•诺依曼邀请他留在高等学术研究院作自己的助手，被拒绝了。图灵在1938年回到英国，恢复自己在剑桥研究生院的学籍。

    正当图灵的理论研究工作进一步深入时，战争爆发了。他被派往布雷契莱庄园承担“超级机密”研究。当时的布雷契莱庄园是一所“政府密码学校”，即战时的英国情报破译中心。在这座幽静的维多利亚式建筑里，表面上鸟语花香、人迹罕见，其实每天都有12000多名志愿者在这里夜以继日地工作，截获、整理、破译德国的军事情报，有些结果甚至直达丘吉尔首相本人手中。在这里，图灵被人们称为“教授”，没有人知道他的真名。

     当时德国有一个名为“Enigma”（谜）的通信密码机，破译高手们绞尽脑汁也难以破解。这个难题交到了图灵手中，他率领着大约200多名精干人员进行密码分析，其中甚至还包括象棋冠军亚历山大。分析和计算非常复杂，26个字母在“Enigma”机中能替代8万亿个谜文字母。如果改动接线，变化会超过2.5千万亿亿。最后多亏波兰同行们提供了一台真正的“Enigma”，图灵才凭借着他的天才设想设计出一种破译机。这台机器主要由继电器构成，还用了80个电子管，由光电阅读器直接读入密码，每秒可读字符2000个，运行起来咔嚓咔嚓直响。它被图灵戏称为“罗宾逊”，至今没人能搞懂图灵究竟如何指挥它工作。但“罗宾逊”的确神通广大，在它的密报下，德国飞机一再落入圈套，死无葬身之地。
    据说在1940年，希特勒下令实施入侵英国的“海狮”行动，第一战就是全歼英国皇家空军。当时英国空军所剩飞机总共不到700架，而德国空军光轰炸机就有1000多架，飞机总数为英军的三倍以上。德军飞行员也全部训练有素，按空中力量对比，英军确非德军对手。哪想到战斗一开始，德军飞机总是莫名其妙被英军飞机半道拦截。屡屡受挫的德国空军恼羞成怒，又发动了规模浩大的“海狮行动”的总攻击。1000多架德军飞机如蝗虫般冲着目的地伦敦呼啸而来，结果还没飞过英吉利海峡，就被英军截击。苦战一天后，德军仓皇逃窜，不得不将“海狮行动”无限期推迟。还有一种传闻说，“罗宾逊”帮助英国获取了德国的极度机密情报，英国如果利用这个情报并采取相应措施，能挽救很多人的生命。但丘吉尔否定了这项计划，因为害怕被德国人察觉“罗宾逊”的存在。
    不过图灵也闹过一个笑话，在开战前，他考虑到德国可能会入侵英国，就着手为这种想法做准备：把所有的钱换成了银子，再把银子用婴儿车运到考虑好的地点，分两个地方进行藏宝工作。这次藏宝导致了两个不幸：图灵在藏宝时伤着了背，而且在战争结束后，他忘记了藏宝的地点！

    1945年，图灵带着大英帝国授予的荣誉勋章，来到英国国家物理研究所担任高级研究员。两年后，图灵写了一份内部报告，提出了“自动程序”的概念，但由于英国政府严密死板的保密法令，这份报告一直不见天日，1969年美国的瓦丁格（Woldingger）发表了同样成果，英国才连忙亮出压在箱底的宝贝，终于在1970年给图灵的报告“解密”。图灵的这份报告后来收入爱丁堡大学编的《机器智能》论文集中。由于有了布雷契莱的经验，图灵提交了一份“自动计算机”的设计方案，领导一批优秀的电子工程师，着手制造一种名叫ACE的新型电脑，它大约用了800个电子管，成本约为4万英镑。1950年，ACE电脑就横空出世，开始公开露面，为感兴趣的人们玩一些“小把戏”，赢得阵阵喝彩。图灵在介绍ACE的内存装置时说：“它可以很容易把一本书的10页内容记住。”显然，ACE是当时世界上最快最强劲的电子计算机之一。     
    1946年，在纽曼博士的动议下，皇家学会成立电脑实验室。纽曼博士是皇家学会会员，又是当年破译小组的成员，正是他对“赫斯•鲁滨逊”的制造起了关键作用。皇家学会的这一新实验室不在伦敦，而是设在曼彻斯特大学，由纽曼博士牵头负责。1946年7月，研制基金到位，纽曼博士开始招募人选。
    阿伦•图灵也在次年9月加盟电脑实验室。一时间，曼彻斯特大学群英会萃。实验室设在一幢维多利亚时代的老房子里，条件十分简陋，但有图灵他们的到来，也算是蓬荜生辉了。在1948年6月就出了一台小的模型机，大家都爱叫它“婴儿”（Baby）。这台模型机用阴极射线管来解决存储问题，能存储32个字，每一字有32位字长。这是第一台能完全执行存储程序的电子计算机的模型，能在1.5秒内轻松算出230-1除以31的答案。

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

    与冯·诺依曼同时代的富兰克尔（Frankel，冯氏同事）在回忆中说：冯·诺依曼没有说过“存储程序”型计算机的概念是他的发明，却不止一次地说过，图灵是现代计算机设计思想的创始人。当有人将“电子计算机之父”的头衔戴在冯·诺依曼头上时，他谦逊地说，真正的计算机之父应该是图灵。当然，冯·诺依曼问之无愧，而图灵也有“人工智能之父”的桂冠。他俩是计算机历史浩瀚星空中相互映照的两颗巨星。   
    早在1945年，图灵就提出“仿真系统”的思想，并有一份详细的报告，想建造一台没有固定指令系统的电脑，它能够模拟其他不同指令系统的电脑的功能，但这份报告直到1972年才公布。这说明图灵在二战结束后就开始了后来被称为“人工智能”领域的探索，他开始关注人的神经网络和电脑计算之间的关联。
    1950年，图灵又来到曼彻斯特大学任教，同时还担任该大学自动计算机项目的头头。就在这一年的十月，他又发表了另一篇题为《机器能思考吗？》的论文，成为划时代之作。也正是这篇文章，为图灵赢得了一顶桂冠——“人工智能之父”。在这篇论文里，图灵第一次提出“机器思维”的概念。他逐条反驳了机器不能思维的论调，做出了肯定的回答。并对智能问题从行为主义的角度给出了定义，由此提出一假想：即一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力，即这台计算机是能思维的。这就是著名的“图灵测试”（Turing Testing）。当时全世界只有几台电脑，根本无法通过这一测试。但图灵预言，在本世纪末，一定会有电脑通过“图灵测试”。终于他的预言在IBM的“深蓝”身上得到彻底实现。当然，卡斯帕罗夫和“深蓝”之间不是猜谜式的泛泛而谈，而是你输我赢的彼此较量。
    阿兰•图灵曾在著作中写道：“与其大费周章去造一个模拟成人大脑的程序，为何不尝试模拟一个儿童大脑？如果再对这儿童模拟大脑进行适当的教育，即可得到成人大脑。”这就是他的“电脑宝宝”理论。
    现在他的“电脑宝宝”已经不单单是理论了，一名叫霍尔（Hal）的，正在实现他的梦想。这个霍尔只是一连串十进位数：一个被像小孩子一样被养大的电脑程序。刚出生时，霍尔的“脑子”和婴儿一样“纯洁”，那时它只是一个对奖励（肯定结果）有“天生”饥渴的字母识别程序。现在，他的语言能力已经骗过了专家。看过霍尔与“母亲”的对话记录后，儿童语言学家断定他是一个智力正常的孩子。他的“母亲”说：“霍尔是个好奇心强，非常聪明的孩子，对新知识无限饥渴。”她教霍尔认识颜色、食物、动物，给他读睡前故事。霍尔的词汇量每天都在扩大，学习潜质惊人。“妈妈”会在与“霍尔”的对话（通过打字键盘）中纠正他的错误。霍尔“天生”对这种纠正深恶痛绝，总想方设法避免重复错误。现在，霍尔已经会要求“妈妈”带他上公园玩球，他的句法有着斯巴达军令式的简洁：“Ball now park Mommy”。霍尔最近听了一个关于狩猎公园里的动物的故事，从那以后，他学会在去公园玩耍的句子后面加上一句“猴子喜欢香蕉，”以提醒妈妈带一些香蕉。而以上发生的这一切，都是霍尔18个月的作为，真不知道10年以后，他会成为一个什么样的“神童”！

    1951年，图灵以他杰出的贡献被当选为英国皇家学会会员。就在他事业步入辉煌之际，灾难降临了。1952年，图灵遭到警方拘捕，原因是他是一个同性恋者。与其他一些智慧超群的人物一样，图灵在个人生活方式上也“与众不同”。当时，人们对同性恋还没有像现在这样宽容，而是把这种行为当作一桩伤风败俗的罪孽。事情的败露是这样的，当时有一位叫琼•克拉克（Joan Clarke）的姑娘爱上了图灵，图灵也对对方很有好感，并向对方求婚，琼欣然接受。但不久，图灵自己退缩了，告诉琼，他是同性恋者。在1948年，图灵就由于同性恋倾向，离开了当时属于高度保密的英国国家物理实验室（NPL）。但也有人说，图灵是被英国军事情报部门“开除”出去的，对于这位天才的离去，许多人叹惜不已。
    1952年3月31日，图灵更因为和曼彻斯特当地一位青年有染，被警方逮捕。在法庭上，图灵既不否认也不为自己辩解。在庄严的法庭上，他郑重其事地告诉人们他的行为没有错，结果被判有罪。在入狱和治疗两者中间，图灵选择了注射激素，来治疗所谓的“性欲倒错”。此后图灵开始研究生物学、化学，还和一位心理医生有很深的交往，那时他的脾气已变得躁怒不安，性格更为阴沉怪僻。1953年3月他因为接待过一位被英国警方注意的挪威客人，成为警方的目标，甚至去希腊度假时也被跟踪。
    1954年6月8日，图灵42岁，正逢进入他生命中最辉煌的创造顶峰。一天早晨，女管家走进他的卧室，发现台灯还亮着，床头上还有个苹果，只咬了一小半，图灵沉睡在床上，一切都和往常一样。但这一次，图灵是永远地睡着了，不会再醒来……经过解剖，法医断定是剧毒氰化物致死，那个苹果是在氰化物溶液中浸泡过的。图灵的母亲则说他是在做化学实验时，不小心沾上的，她的“艾伦”从小就有咬指甲的习惯。但外界的说法是服毒自杀。一代天才就这样走完了人生。

英文名: Alan Turing

资源格式: DVDRip
版本: 7月15日增加《The Turing Test》
发行时间: 2005年
地区: 美国
语言: 英语
简介:

阿兰·图灵（Alan Turing）这个名字无论是在计算机领域、数学领域、人工智能领域还是哲学、逻辑学等领域，都可谓“掷地有声”。图灵是计算机逻辑的奠基者，许多人工智能的重要方法也源自这位伟大的科学家。他在24岁时提出了图灵机理论，31岁参与了Colossus（二战时，英国破解德国通讯密码的计算机）的研制，33岁时构思了仿真系统，35岁提出自动程序设计概念，38岁设计了“图灵测试”，在后来还创造了一门新学科—非线性力学。虽然图灵去世时只有42岁，但在其短暂而离奇的生涯中的那些科技成就，已让后人享用不尽。人们仰望着这位伟大的英国科学家，把“计算机之父”、“人工智能之父”、“破译之父”等等头衔都加冕在了他身上，甚至认为，他在技术上的贡献及对未来世界的影响几乎可与牛顿、爱因斯坦等巨人比肩。

　　1912年，图灵出生在伦敦一个缺少亲情的家庭里。少年图灵的性格迥异，他内向、腼腆、胆小、软弱并患有轻度口吃，不被人接受，更不擅与人打交道。他小时候学业平平，除了一些简单的化学实验和数学题外，并无太多闪光之处。图灵的人生转机出现在他19岁进入英国剑桥皇家学院学习时，从那时起，他对数字的兴趣便一发不可收拾。在剑桥的图灵就已经是一个妇孺皆知的怪才。他的自行车链条经常在半路上掉落，要是换了别人，早就拿到车铺去修理了，而他居然在脚踏板旁装了一个小巧的机械计数器，到圈数时就停，然后歇口气换换脑子，再重新运动起来。

　　1936年，图灵在一篇名为《可计算数学》的论文中首次提出了有关计算机的理论，其中 最重要的三点为后世带来了极其深远的影响：计算机的抽象定义、“通用计算机(Universal Machine)”的设想，以及“存在任何计算机都无法解决的问题”的想法。之后，“图灵机”（Turing Machine）便诞生了。

　　当时的图灵机还只能计算有限的实数，但它的符号记录方法为以后的计算机发展奠定了基础理论，基于此，人类首次产生了符号处理的概念，并开始把研究重点转向了“可改变的编码程序”上，这就是今天软件的前身。图灵论文中的“用有限的指令和有限的存储空间可算尽一切可算之物”理论让当时所有的科学家震惊，他也因此赢得了科学界的“史密斯奖”，美国《国防软件工程杂志》也将他评为百年来影响软件发展的十位大师之一。然而，这对他来说还只是个开始。

　　1939年第二次世界大战爆发，正在为英国国家密码机构工作的图灵和其他科学家一起着手研究如何破解敌人的密码，他果然不负众望，成功破译了德国军方使用的着名通信密码系统“Enigma”（谜）。于是第一台电子图灵机被设计制造出来，做出重大贡献的图灵获得了政府颁发的OBE奖。

　　二战后，图灵被英国国家物理实验室邀请参加计算机的设计工作。1950年，图灵的一篇里程碑式的论文《机器能思考吗？》又为人类带来了一个新学科—人工智能。为了证明机器是否能够思考，他又发明了“图灵测试”（Turing Test），图灵测试在今天仍被沿用。他指出，最好的人工智能研究应该着眼于为机器编制程序，而不是制造机器。而他在论文中预测的计算机发展过程中将会出现的一些问题，至今仍未被解决。

　　尽管才华横溢的图灵在许多领域都有着不凡的成就，但因其在计算机和人工智能方面的突出贡献，人们还是喜欢称他为“人工智能之父”或“计算机之父”。同样有着“计算机之父”称号的冯·诺依曼的助手弗兰克尔在一封信中写到：“……计算机的基本概念属于图灵。按照我的看法，冯·诺依曼的基本作用是使世界认识了由图灵引入的计算机基本概念……”

　　为了纪念，图灵的事迹已被拍成影视剧，写成小说、诗歌等，以他名字命名的“图灵奖”也已成为计算机界的诺贝尔奖。牛津大学着名数学家安德鲁·哈吉斯在为图灵写的一部脍炙人口的传记《谜一样的图灵》（Alan Turing: The Enigma）中这样描述到：“图灵似乎是上天派来的一个使者，匆匆而来，匆匆而去，为人间留下了智慧，留下了深邃的思想，后人必须为之思索几十年、上百年甚至永远。”

　阿兰·麦席森·图灵 1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。他杰出的贡献使他成为计算机界的第一人，现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖”。上中学时，他在科学方面的才能就已经显示出来，这种才能仅仅限于非文科的学科上，他的导师希望这位聪明的孩子也能够在历史和文学上有所成就，但是都没有太大的建树。少年图灵感兴趣的是数学等学科。在加拿大他开始了他的职业数学生涯，在大学期间这位学生似乎对前人现成的理论并不感兴趣，什么东西都要自己来一次。大学毕业后，他前往美国普林斯顿大学也正是在那里，他制造出了以后称之为图灵机的东西。图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。

  图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《机器会思考吗？》（Can Machine Think?）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。至今，每年都有试验的比赛。

  二战时，图灵在英国通信部工作，他运用他的专业技能破译德国密码，这在当时十分不容易，因为德国人开发出一种用于计算的机器称为Enigma，它能够定期将密码改变，让破译者根本摸不到头绪。在通信部工作的时候，图灵和同事们一起使用一台称为COLOSSUS的设备破译德国的密码，COLOSSUS干得相当不错，COLOSSUS虽然是用马达和金属做的，与现在的数字式计算机根本不是一回事，但它是现代计算机重要的一步。二战后，图灵需要找一种放松自己的方法，于是他选择了长跑，他选择的一般都是他善长的。下图就是Enigma的照片。

  1945年到1948年，图灵在国家物理实验室，负责自动计算引擎(ACE)（Automatic Computing Engine，ACE）的工作 。 在这一时期他开始探索计算机与自然的关系。他写了一篇名为《智能机》的文章于1969发表，这时便开始有了人工智能的雏形。1949年，他成为曼切斯特大学计算机实验室的副主任，负责最早的真正的计算机---曼切斯特一号的软件工作。在这段时间，他继续作一些比较抽象的研究，如“计算机械和智能”。图灵在对人工智能的研究中，提出了一个叫做图灵试验的实验，尝试定出一个决定机器是否有感觉的标准。 1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。後來美國新墨西哥州洛斯阿拉莫斯国家实验室的研究群根據圖靈的理論，在MANIAC上設計出世界上第一個電腦程序的象棋。 

  图灵相信机器可以模拟人的智力，他也深知让人们接受这一想法的困难，今天仍然有许多人认为人的大脑是不可能用机器模仿的。而在图灵认为，这样的机器一定是存在的。图灵经常和其它科学家发生争论，争论的问题就是机器实现人类智能的问题，在今天我们看来这没有什么，但是在当时这可不太容易被人接受。他经常问他的同事，你们能不能找到一个计算机不能回答的问题，当时计算机处理多选问题已经可以了，可是对于文章的处理还根本不可能，但今天的发展证明了图灵的远见，今天的计算机已经可以读写一些简单的文章了。

  图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器，它于1950写文章提出了著名的“图灵测试”，测试是让人类考官通过键盘向一个人和一个机器发问，这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后，这位人类考官不能确定谁是人谁是机器，那这个机器就有智力了。这个测试在我们想起来十分简单，可是伟大的思想就源于这种简单的事物之中。

  现在已经有软件可以通过图灵测试的子测试，软件这个人类智慧的机器反映应该可以解决一些人类智力的问题。在完成ACE之前，图灵离开了NPL，它在曼彻斯特大学开发曼彻斯特自动计算机（Manchester Automatic Digital Machine，MADAM）。他相信在2000年前一定可以制造出可以模拟人类智力的机器，图灵开始创立算法，并使用MADAM继续他的工作。

  图灵对生物也十分感兴趣，他希望了解生物的各个器官为什么是这个样子而不是那个样子，他不相信达尔文的进化论，他觉得生物的发展与进化没什么关系。对于生物学，他也用它钟爱的数学进行研究，它的研究对他进行计算机的研究有促进作用。它把生物的变化也看做是一种程序，也就是图灵机的基本概念，按程序进行。最后，这位伟大的计算机先驱于1954年6月7日去世，他终生未娶。

宋方敏（南京大学，计算机软件新技术国家重点实验室，南京，210093）

§1.引言美国TIME杂志在1999年出版专卷介绍20世纪100个最伟大的智者，在计算机科学领域中英国数理逻辑学家Alan Turing列入其中（数学有Kurt Godel，物理有Albert Einstein,后来Einstein列为The person of the 20th century）。由于Turing对于人类的极出贡献，他成为20世纪最有影响科学家和思想家之一。本文介绍Alan Turing的生平和主要工作，以此纪念计算机科学的奠基人。

    §2. Turing评说在数理逻辑的神秘王国里，一个天才提出了质疑和构想——设计一台能够模拟人类思维演段的机器—— 一个天方夜谭？如果Turing所做的一切只是回答了神秘的数理逻辑领域里的一个令人苦恼的问题的话，那么就不会有什么理由让外行人记住他。但正相反，Turing使用他那给整个世界带来巨大影响的方法，向世人展示——“一个封闭的逻辑系统里的某些命题是不能在本系统内得到证明的”——这一曾令Kurt Godel名声大振的推论。这个年轻而前卫的剑桥大学学生所做的就是梦想着造一台假想的机器——一台简洁而精巧，打字机模样的，可以扫描或读入那些写在（理论上）无限长的磁带上的指令的机器。随着扫描器在磁带上移来移去——机器依据指令按序执行或跳转，从而，Turing提出，机器执行过程的输出可以重现人类的思维。这种受灵感启发的思想实验中的机器，连同Turing的另一个想法，很快获得了一个名字：Turing机。因为磁带上的指令可以控制机器的行为，所以通过更换相应的指令就可以让这台机器去完成所有这样的机器所能完成的任务。换句话说，通过扫描不同的磁带，同样的一台机器既可以算题，又能下棋，还会做其它的相对更自然的任一件事.于是,他的机器又赢得了一个更好听的新名字：通用Turing 机。
    随着指令的运行，这样一台十分原始的硬件组合可以完成令人惊讶的各种任务。这样的想法听起来可能吗？在1937年显然是无法想象的。那一年，Turing的学术论文On Computable Numbers, with an Application to the Entscheidungsproblem发表在伦敦数学会学报上。但是Turing的想法被很少的读者所理解,他们认为这些构思在理论上十分有趣和诱人，却没有人认识到Turing的机器为后来的电子数字计算机勾画出了蓝图。
    由于今天的计算机继承了如此之多的想法和技术上的创新，以至于我们无论将发明计算机的功劳归在谁的头上都是鲁莽的。但事实是，每敲击一次键盘或打开一扇窗口，抑或是运行一个字处理程序都是在一台Turing机的化身上工作。
    Turing 1937年的论文改变了他的一生，让一个腼腆而脆弱的男人更多地被卷入到尘世中去，最终走向一个悲剧式的结局。
    Alan Mathison Turing 1912年生于伦敦，是这个家庭的第二个孩子。他的父亲是印度British Civil Service的成员，但他的母亲认为这样的环境不利于孩子的成长。于是Alan和哥哥在英国的一个领养家庭中度过了他们的童年,除了偶尔回家看看，大部分时间和父母分开。也许就是这其间Turing的孤独感诱发了他一生对人脑机理的兴趣——当上帝赐予的这个世界显得贫瘠和令人不满的时候，怎样创造一个属于自己的世界呢？Turing从13岁起就读于Dorset的Sherbourne小学，在那里，他已经显示出了自己的数学天赋，尽管他的卷子总是因为杂乱无章而被批评。Turing在读小学的时候就发现了自己的同性恋倾向，并爱上了学校里的另一个小男孩——虽然Turing从未告诉过任何人——后来这个小男孩猝死于结核。这一事件粉碎了Turing的宗教信仰，使他成为了一个无神论者，并让他坚信所有的现象都有一个客观的解释。机器没有思想，而大脑中也没有灵魂。那么，思维和意识又是从何而来呢？在两次向剑桥大学Trinity College 这所令全世界的数学家们神往的学府申请资助失败之后，Turing 终于获得了 King’s College 的资助。在诸如 John Maynard Keynes 以及E.M. Forster 这些名家泰斗们的指引下，King’s College 为 Turing 提供了充分自由与宽松的环境。尽管他被King’s College的核心学术圈以行为不够检点的理由而拒之门外，Turing还是得到了巨大的发展。并且当他获得了学位证书之后，Turing成了King’s College的一名导师。而如果不是后来的Turing 机的诞生和二次大战的爆发，Turing恐怕只会在数理逻辑的世界里慢条斯理、优哉游哉地生活一辈子了。

    由于Turing发表的一系列论文，他被召入政府 Code and Cypher School。这所学院在一个叫做Bletchley Park的维多利亚风格的大厦里。这里囫囵吞枣似的聚集了那些被认为有可能攻破纳粹通信密码的人，包括数学家、国际象棋大师、古埃及研究学家等等。因为这项工程受到了严格的保密，Turing在这里的工作直到他去世后才得以公之于众。正如计算机的问世一般，Bletchley Park 的工作也是众人共同智慧的结晶。而Turing的角色更是重中之重——他设计了一台原始的类似计算机的机器，用以高速破译北大西洋上纳粹U-艇间通信的密码。
    二战后，Turing回到了剑桥，他希望能够重新拾回他所向往的宁静的研究生活。与此同时，国家物理实验室新近成立了一个数学分支——这个千载难逢的机遇使得Turing能够设计出真正的Turing machine（即ACE —— Automatic Computing Engine）—— Turing 欣然前往。然而事实并不如人意，官僚主义、繁文缛节，事不关己、高高挂起之风盛行于时。战争年代里的那种晨兴夜寐、攻苦食淡的精神早已荡然无存。Turing 的提议不是被束之高阁就是被全然否定。Turing 决定离开NPL，而后他在剑桥小憩，最终来到了曼彻斯特大学。这里的实验室正在根据他1937年提出的构想建造一台计算机。
    Turing自发表第一篇论文以来，就一直致力于拓展其关于会思考的机器的设想。他甚至提出，一台会思考的机器可以学习并编制指令。1950年，在著名的英国哲学期刊Mind上，Turing提出了“模仿测试”的概念（后来被称做“Turing测试”）。比如在一封闭的屋子里，一提问人可以向另一个人与一台机器发问。若提问人不能通过二者的回答辨别出哪一个是人，哪一个是机器的话，则这台机器就被认为能够象人类一样地“思考”。
    Turing在人工智能支持者的心目中仍是一位英雄——其原因部分来自于Turing对未来的一个乐观的估计：“未来的某一天，女士们带着她们的计算机在公园里散步，她们说：‘我的计算机告诉我这真是个快乐的早晨！’”不幸的是，美好的憧憬总让路于残酷的现实。在曼彻斯特的时候，一天他因遭抢劫而报警，那时他正和另一个同性恋男子在一起，而这个人很可能为罪犯所认识。Turing 从不隐瞒自己的同性恋倾向，但这次却使他身陷囹圄。同性恋在当时的英国仍是极重的罪名，1952年，Turing 被判决为“严重猥亵罪”。不久他被减刑，并被要求注射雌性荷尔蒙以去除其同性欲望。一次，Turing对他的朋友说：“我变得越来越有女人味了！”在1954年6月7日，Turing食注有氰化钾的苹果自尽, 当时他只有41岁。
    §3. Turing机简介Alan Turing 在1936提出了非凡的Turing机概念，从而定义出可计算性，Turing的思法是基于对人们用笔和纸来实现一个算法的分析，他把这样的过程看作下列两种非常简单的动作。
    （1）写上或擦去某个符号。
    （2）把注意从纸的某个部位转移到另一个部位。
    而在每个阶段，算法说明下一次要做的动作。这样就依赖于（a）行为者当前观注的纸上某个部位上的符号和（b）行为者思维的当前状态。为了达到实现算法的目的，假定这完全由此算法以及迄今为止的运算记录来确定。这可能为编入一个部分的记录，但这不反映行为者的心情、智力和理解力。而且由于行为者是有穷的，故他只能处于有穷个互异状态。当然行为者的状态能转为此阶段已执行的动作。Turing以此法设计一种有穷机器来执行算法，后来这类机器被称为Turing机。

    下面我们给出Turing机的定义。一个Turing机M是一个有穷装置其在一条纸带上执行运算。这条纸带向两端无限延伸且在两个方向上都已画上了无穷多个方格。（参见图１）图1纸带代表人类行为者算题时的纸，而每个方格代表即时运作的一个部分。在运算时只有有穷格被利用，但我们事先不知道要用多少个格子。纸带是无穷的代表人类在计算时可无限量提供白纸。在任何时刻，纸带上的每个方格要么空白，要么含某个符号，这些符号取自M的字母表固定的一列符号S1，S2……Sn。下以B表示空白且把B看作S。属于M的字母表。M有一个读头，它在任何时候都扫描着纸带的单个方格。（参见图２）Ｍ q 当前状态读头S3 S2 S1正被扫描的方格图２M可在纸带上进行三种简单动作：1.擦去正被扫描方格的符号且把它换成M字母表中的另一符号。
    2.把读头移至正被扫描方格的右边的方格。
    3.把读头移至正被扫描方格的左边的方格。
    在任何给定时刻，M处于某个状态，M的状态总共有有穷个，可设为q1,…,qm，在运作中，M的状态是可变的。我们可设想M的当前状态q展示于M的外体上（参见图2），认为此q既部分指导当今做了什么以及今后将做什么。
    在任何时刻M采取的行动取决于M的当前状态以及正被扫描的符号，这样的依赖关系被用M的说明来描述，M的说明Q是由有穷个四元组构成，每个四元组呈下形：qisjskql,qisjRql,qisjLqlp这里1≤i,l≤m,O≤j,k≤n,Q中的四元组qisjαql说明当M处于状态qi且正扫描于Sj时M将采取的动作如下：1.带上运算1.1.若α＝Sk则擦去Sj,同时在当前方格中写上Sk1.2.若α＝R，将读头向右移一格1.3.若α＝L，将读头向左移一格2.转成状态qlM的说明Q需要对每个对qisj至多存在一个呈形qisjαβ的四元组于Q中，否则会导到M下个动作的不确定。
    为了进行计算，必须为M提供一条纸带以及确定M当前所扫描的方格，而且指定M的初始状态。然后，假设M当前状态为qi且正扫描符号Sj,若在M的说明Q中，有呈形qisjαql的四元组，则M将如上所述地动作。这种动作将重复于新状态和正被扫描的符号，M将尽可能地如此进行下去。M的动作终止仅当其状态为qi且正扫描着Sj使Q中不存在呈形qisjαβ的Q元组，即Q中无四元组其指示下一步做什么，当然这种情况永不发生。
    例.该M的一个Turing机其字母表为{B，O，1}且其可能状态为q1和q2，M的说明为q10Rq1q110q2q20Rq2q21Rq1假设为M提供的纸带为1 1 1 1 1 1 1 1状态为q1α=q118α→q2017α→0q217α→01q116α→01q2015α→010q215α→0101q114α→……α→010101q111α→010101q201α→0101010q21α→01010101q1B0 1 0 1 0 1 0 1若为M提供的纸带的每个方格为0或1，则M不停机。
    由上例可看出，Turing机M是在纸带上实行算法的一个装置，算法的全部内容含于M的说明Q中理论上，Turing机被定义成某个Ｑ元组集合，而不是实际上构造的物理Turing机。
    为了把Turing机当作计算数论函数，我们首先在纸带上表示数，例如设Ｍ的字母表中含１，把１看作“小木棒”，用连续的n+1个“１”表示n。
    B 1 1 1 … 1 Bn+1个1约定， =1n+1,对于m元组（n,……,nm）,其对应的带表达式为定义：设f为从Ｎ到Ｎ的部分函数，Turing机Ｍ计算f(n)指若为Ｍ提供上面的纸带，初始状态为q１且箭头标出正扫描的方格，则=对于m元部分函数f(x1,…,xm),M计算f指M始于状态q１且提供如下纸带且由箭头指出正被扫描的方格：Ｂ 1 … 1 B 1 … 1 B … B 1 … 1 Bx1+1 x2+1 xm+1若Ｍ计算终止则f(x1, …,xm)为带上１的总数否则f(x1, …,xm)无定义。
    例 加法n+m可由如下的Turing机计算：Ｍ的字母表为{Ｂ，１}，Ｍ的说明Ｑ为q11Bq1q1BRq2q21Bq3q2BRq2情况１：n≠0q11n+1B1m+1→q1B1nB1m+1→Bq21nB1m+1→Bq3B1n-1B1m+1停。
    情况２：n=0q11B1m+1→q1BB1m+1→Bq2B1m+1→BBq21m+1→BBq3B1m定义：一个部分数论函数是Turing可计算的指存在Turing机其计算之。这样就定义了什么是可计算的。由以上知n+m是Turing的计算的，事实上Turing的计算能力非常强大，一切的递归函数都是Turing可计算的，可以证明任何一种程序设计语言所能计算的函数一定是Turing可计算的，为此现在人们接受Church-Turing论点：一切可直觉可计算的函数是Turing可计算的。  UID40 帖子1696 精华5 积分1332 阅读权限100 性别男 在线时间450 小时 注册时间2004-8-29 最后登录2009-5-21 查看详细资料 TOPEastsun阿赖耶版主个人空间 发短消息 加为好友 当前离线  2# 大 中 小 发表于 2005-9-1 15:14  只看该作者§4.Turing生平1912--Alan Turing出生于1912年6月23日，伦敦.他的父亲 Julius Mathison Turing，是印度British Civil Service成员。他经常在国外。Alan的母亲Ethel Sara Stoney是Madras铁路总工程师的女儿。Alan的父母在印度相遇，并在那儿结了婚。当Alan大约一岁时，他的母亲在印度与丈夫相聚。而Alan留在了英国，与这个家庭的朋友待在一起。之后,Alan被送入学校，但这似乎没有使其受到任何好处，因此，几个月后，他离开了学校。接下来，他又被送往Hazlehurst Preparatory学校，在那儿，他在许多课程上获得了中上的成绩，但他相当有主见。在学习生涯中他对棋类产生了兴趣，并且加入了辩论社。
    1926--他通过了常规入学考试，随后进入了学校。1926年，Turing恰遇大罢工，当罢工正进行中，他骑车60英里从家来到学校。虽然母亲坚定的认为他必须接受公立学校的教育，但Turing发现他很难成为学校所期望的那样。许多有独创思想的思想家发现学校是一个几乎无法理解的过程，Turing便是一例。他的天赋驱使他朝自己的方向发展而无需老师。
    Turing因书法而被批评，为英语而奋争，甚至在数学上他采用自己的方法而不用老师所教授的解题法。在Sherborne 期间，尽管是非常规的方法，Turing仍然赢得了几乎所有的数学奖。从早期起，Turing就对化学中的一个课题很感兴趣，他按自己的日程安排做试验，这使得他的老师很不高兴。 Turing的校长认为：如果他留在公立学校,他必须以接受教育为目标.如果他仅想成为科学专家，在公立学校就是浪费时间。这话远超出了对Turing自身的意义，他说明了图灵所遇到的学校体制。虽然，他的老师可能并不清楚他在自学些什么,但Turing在校期间学习了深奥的数学知识。他阅读了Einstein的关于相对论的论文，还通过Eddington的“物质世界的性质”了解量子力学。
    1928年，发生了影响Turing一生的事。他与Christopher Morcom年长其一岁的学生，产生了亲密的友谊，并且两人共同工作于科学事业。也许，这是Turing第一次找到一位有共同思想的人。可是Morcom于1930年2月去世。这对Turing是一个沉重的打击。在Morcom生病期间，Turing就有死亡的预感。他感到这是科学无法解释的。之后，他写到：这些事实是不难解释的，但我感到惊奇！1931--尽管学校这几年的艰难，Turing仍然1931年进入了剑桥皇家学院学习数学。这并非易事。1929年，Turing参加了奖学金考试，他赢得了一个展现机会而非奖学金。因对这一结果的不满，Turing在第二年又参加了考试，这一次他获得了奖学金。剑桥较其他学校对像这样的非常规学生而言是一个相对较舒适的环境。他现在更能探索自己的思想，在1933年他读了 的数学哲学入门。同时，他读了Neumann关于量子力学的1932年的文章。这是一个其一生反复研究过的课题。

    1933年，Turing开始对数理逻辑感兴趣。Turing读了一篇关于“数学和逻辑”的文章。他提出数学的纯逻辑的观点是不足的，数学命题具有多种解释，逻辑只是一种。1933年，德国希特勒上台，英国爆发了反战运动。Turing加入了反战运动，但他没有随波逐流去信仰某些主义。Turing毕业於1934年，在1935年的春天,他参加了Max Mewman的关于数学基础的高级教程。这一课程研究了Godel不完全性结果和Hilbert的可判定性问题。某种意义上来说，可判定性是一个简单的问题，亦即给定一个数学命题，是否能找到一个决定命题是真或假的算法。对于大多数命题来说，寻找这样一个算法是简单的。真正的难点在于证明对于确定的命题，这样的算法不存在。当给出了一个解决某一问题的算法，很明显它确实是一个算法，然而没有关于算法的足够严谨的定义使得可证明算法的不存在性。Turing开始对这些问题进行研究。1935年，图灵因一篇关于高斯的误差函数（证明概率理论的基本结果，亦即中心极限定理）的论文而当选为剑桥皇家学院的成员。虽然中心极限定理已被发现，但Turing并不知道，他独立的发现了它。1936年, Turing成为一位Smith 奖得主。
    1937--现在，Turing在剑桥的成就被用来说明他在概率理论上的工作。然而，自从他参加了Newman的课程后，他就开始做可判定性问题的研究了。1936年,他发表了On Computable Numbers, with an Application to the Entscheidungsproblem的学术文章。在这篇论文中，Turing引入了抽象机的概念（现被称为Turing机）。Turing机利用有限的规则（由一张有限表给出）及从带子上读入一个符号，从一种状态转换到另一状态。Turing机可输入或删除带子上的一个字符。Turing写到：记录下的一些字符将会形成正在计算的实数的小数的数字序列。其他的则只是一些粗略的符号用来”协助存储”，应被删除。
    他将可计算数定义为小数扩展位可通过Turing机从空白带子产生的实数。他指出那即可计算的，但由于仅可数的实数是可计算的，多数实数是不可计算的，因此，他给出了不可计算的数的描述，并指出由于他在限定条件下描述了一个不能在限定条件下描述的数，从而，这显得有些矛盾。但Turing明白这显然的矛盾的根源。给定指令表的Turing机是否输出无限序列的数（用另一Turing机实现）是无法判决的。
    虽然，这篇论文包含着对数学和计算机科学均有相当价值的观点，但在伦敦数学会学报上发表它却不是那么容易的。原因是Alonzo Church 於1936年在美国数学期刊上发表了一个初等数论不可解问题，同样证明对于算术无判定过程。Turing的方法与Church有相当的差别，但在伦敦数学会期刊出版它之前，Newman为此费尽唇舌。Turing的修改稿提到了Church 的结果于1936年4月首次完成，同年8月修改的论文，这篇修改稿於1937年发表。
    与Church讨论的好处在于，1936年Turing成为普林斯顿大学的研究生。在普林斯顿Church的指导下, Turing了解了研究的方法。1938年,他返回英国。1937年，Turing回英国度暑假邂逅Wittgenstein。他在普林斯顿的工作主要是基于序数的逻辑系统，发表于1939年。Newman 认为：这篇论文充满了有趣的设想和观点……他展现了Turing的直觉及数学证明方面的东西。
    在这篇论文发表之前，Turing发表了两篇更常规的数学论题方面的论文。一篇是讨论通过有限群逼近Lie群的方法，另一篇证明了扩展群的结果并给出了更简单和系统的方法。（Reinhold Baer首次证明了这一结果），Turing在Turing机上的工作最引人注目的是在现实技术所能构造之前，他已描述了现代计算机。他在1936年的论文中证明通用Turing机的存在：能用来做任何特殊目的的机器的工作，亦即若有恰当的指令输入，可进行任何计算。尽管对Turing来说，“计算机”是一个执行计算的人，但我们必须从他对广义Turing机的描述中看到我们今天的计算机加装有程序的带子即Turing机。在普林斯顿期间，Turing设想过构造计算机。1938年，他一回到剑桥就开始构造analogue mechanical device 用来研究Riemann 猜想，这是当今许多人认为的最难解决的数学问题。然而，在国家密码机构邀请他回来破译德国密码之后，他的工作呈现出新的面貌。
    1939--当1939年二战爆发，Turing立即在政府设在Bletchley公园的译码和解码部门进行工作。虽然官方对在那里开展的工作进行了严格的保密，但现在大部分内幕已被公开。Turing在密码学和计算机方面的天才帮助破译小组破译了不少密码，拯救了无数士兵的生命。那一段时间对于他是一生中最快乐的时间,充分发挥了他的才能。
    Turing和另一位数学家Welchman一起在波兰数学家早期工作的基础上发展了Bombe机，这台机从40年代末对所有从Luftwaffe的密码机发出的消息进行了译码。德国海军的密码机的编码很难被破译，但这正是Turing所感兴趣的挑战。在1941年中期，Turing在统计学和信息捕获方面的进展，使得德国海军的信号在Bletchley被破译。
    从1942年11月到1943年3月Turing在美国进行解码和一个语音保密系统的研究工作。德国人加密方式的改变意味着Bletchley失去了破译消息的能力。尽管Turing并没有直接参与到成功破译更多的密码工作中，但他的思想的重要性在这项工作中得到充分体现。1945年, Turing由于在战争中所作出的贡献而获得了OBE奖。
    1946--二战后，Turing被伦敦国家物理实验室邀请去参与计算机的设计。他在1946年提交了一份关于自动计算机器的报告。用现代人的观点看来，Turing当时所提出的设想是一份有关计算机的原始的详细设计。他为ACE(自动计算机器)设计的存储器的大小被当时大多数人认为是毫无希望和过于夸张的，以至于在这个项目被批准前被耽误了好一阵。
    在1947到1948学年Turing回到了剑桥，在那里他的研究兴趣不再是计算机和数学了，令人惊奇的是，他竟然研究神经学和生理学。在这期间，他并没有忘了计算机，而且他还为计算机编写代码。不过他的学术研究太广泛了，二战后他还认真研究了人类学。Walton运动俱乐部记录表明，Turing作为会员曾赢得了3英里和10英里的冠军。1947年他参加了A.A.A马拉松比赛，获得第15名。
    1948年Newman成为曼彻斯特大学的数学教授，在那里他为Turing提供学者基金。于是Turing从国家物理实验室回到了曼彻斯特。Newman写到：期望Turing能领导开展该项目中的数学工作。一段时间能继续工作下去，为已建造好的机器设计例行程序，然后当这些工作稳定后，继续数论分析方面的一般性问题研究。工作从由FC Williams 和 T Kilburn提出的计算机的构造开始。
    1950--1950年，Turing在计算机和人工智能方面作出了极为卓越的成就。1950年，Turing发表了里程碑式的论文“机器能思考吗？”，他预测了随着计算机发展将会出现的问题。他研究了人工智能领域的核心问题。时至今日人们还用他发表的这篇论文中所提出的Turing测试来尝试回答电脑是否具有智能。
    Turing没有忘记判定性问题是他那些具有深远意义的数学论文的起点。群论中的一个主要问题是：在一个有限群中给定任意一个字，是否存在一个算法判定这个字等于单位。Post已经证明半群中不存在这样一个算法。虽然一开始Turing已经证明了对于群有同样一个结论，但在就对他证明做一个讨论会上，他发现了一个错误。他从自己不完善的证明中发现一个消去的半群有不可解字问题。Turing在1950年发表了这个结果。1957年勃恩通过Turing的这篇论文中的思想证明了存在一个有不可解字问题的群。
    主要因为在他1936年提出的“Turing机”方面所做的工作，Turing在1951年当选为伦敦皇家学院的会员。到1951年为止，他致力于将数学应用到生物组织研究中去。1952年他公布了在地貌形成方面，关于在有机生命体中模式和组织的演化的一部分研究工作。
    1952--1952年Turing在警察局报告一宗同性恋事件的细节时被捕，他被指控违反了英国同性恋法令。而他去警察局是因为他遭到了勒索.1952年3月31日，他作为一位同性恋者被审判，他认为他自己没错，未给自己辩护。然而，他被判为有罪。当时，他只有两条路可走：坐牢或注射激素。他选择了后者，并继续他广泛的学术研究。
    他不仅在地貌形成的研究中有进一步进展，而且他还在量子理论和相对论的研究中提出了新的思想，即用旋量来表示初等粒子。在Bletchley公园的译码工作成了图灵在GCHQ进行译码和人工智能研究工作的基础。在冷战期间，译码成为一项重要的工作，Turing继续为GCHQ工作，尽管他在曼彻斯特的同事还没完全意识到这一点。在他被定罪后，他失去了安全保障。但更糟糕的是，安全部门的官员将他这位知识渊博，在GCHQ开展工作的学者定为安全方面的危险分子。由于学术需要，Turing有许多外国同事，但警察开始调查他的国外来访者。1953年Turing在希腊的一次度假引起了安全人员的恐慌。1954年6月7日，Turing在寓所身亡，他的床头有一个咬了一半的苹果，经解剖，发现是剧毒氰化物致死，那个苹果是在氰化物溶液中浸泡过的，经调查，Turing为自杀，但他母亲始终认为这是一个偶然事件。
    §5.结束语Turing不仅是一位数学家、逻辑学和计算机科学家，而且他更是一位哲学家，科学哲学家，他问出：“什么是计算”以及“机器能思考吗”使我们受到哲学精神的震撼，他虽然是这个尘世的匆匆过客，但他是勇敢的智者，他的发明将影响人类的思维，他是欧洲上空划过的灿烂的流星。他是人类历史上的大智者。人们将永远怀念他，美国ACM设Turing奖，以此纪念。

《IT史记》 ，方兴东、王俊秀，中信出版社，2004年
http://space.100e.com/myspace/Diary-48751
http://www.emsky.net/bbs/viewthread.php?tid=10347
http://en.wikipedia.org/wiki/Alan_Turing