可判定性：一个语言L，是一个集合，且其补集为
。当L是图灵机可识别时，语言L则称为半可判定。当语言L不是图灵机可识别，则为不可判定语言。当且仅当L和都是图灵机可识别的时候，L才能称为可判定语言。
数理逻辑中的一个重要问题。它表现为寻求一种能行的方法、一种机械的程序或者算法，从而能够对某类问题中的任何一个在有穷步骤内确定是否具有某一特定的性质。例如，命题逻辑的任一公式是不是常真这个问题，就可以在有穷步内按照一定的程序用真值表判定。如果对某类问题已经获得这种能行的方法，就说明这类问题是可判定的，或者说其判定问题是可解的；如能够证明某类问题不可能存在这样的方法，就说这类问题不是能行可判定的。判定问题有不同的陈述。从语义方面考虑，判定问题是要确定一公式是否常真，亦即是否普遍有效，或者可否满足；在语法方面，它是要确定某一公式是可证，还是可否证。
逻辑系统的判定问题 命题逻辑的任一公式是否常真以及是否可证都是能行可判定的。20世纪30年代美国数学家A.丘奇和英国的A.M.图林分别证明了谓词逻辑的判定问题是不可解的。对谓词逻辑公式可以用前束范式分类，前束范式是一公式，其中一切量词都未被否定地处于公式的最前方，谓词逻辑的每一公式都和一前束范式等值或者可以互推。有些前束范式类是可判定的，例如只含有全称量词的前束范式。1962年A.S.柯尔、E.F.摩尔和美籍华人学者王浩证明了不可判定的谓词逻辑公式都可以归约为凬ヨ凬式。这种不可判定的公式类型被称为归纳类。
在数学系统里，C.H.朗格弗德于1927年证明了自然数的线性序理论的判定问题是可解的。1929年，M.普利斯贝格证明了自然数的加法理论的判定问题是可解的。50年代初，A.塔尔斯基解决了初等几何理论的判定问题。1970年，苏联学者Ю.В.马季亚谢维奇证明了 D.希尔伯特所提出的23个著名数学问题中的第10个问题是不可解的。希尔伯特第10个问题是指寻找一个算法，用它能确定一任给的整系数多项式方程
p(x1,...,xn)=0
是否有整数解。结果证明，这样的算法是不存在的。
证明一个理论的判定问题可解，只需给出一个算法，并证明这算法就是所要求的，问题就解决了。要证明一个理论的判定问题是不可解的，首先需要把算法（机械程序）概念精确化，并给出算法概念的严格的数学定义，使一切算法的类成为明确的数学对象，从而能用严格的数学方法证明对某个理论来说不存在解决它的判定问题的算法。判定问题的研究推动了对算法理论或称可计算性理论的研究，促进了递归函数论（见递归论）和图林机器理论的建立。
能行性和可行性 从计算复杂性方面对可解的判定问题的研究证明，一些理论虽然原则上是可判定的，但它的判定程序（算法）所需的计算步数太大，以致在实践上是不可行的。例如，就可判定的自然数的加法理论来说，已经证明，对于该理论的每一判定算法，都有长度（即符号数目）为
n的语句（公式），使得依据该算法判定此语句是否可证需要计算
22cn步（c为>0的常数）。假如取n=10，那末即使使用每秒运算一亿次的高速计算机作判定,也需要很多亿个世纪。一个重要的问题是:是否存在某些可判定的理论。而且其判定方法是快速的,在实践上是可行的。对于这个问题迄今未能作出肯定的或否定的回答。70年代以来，通过研究命题逻辑的判定方法的复杂性，发现了许多已知的组合型的判定问题都可化归为命题逻辑的判定问题，如果能找到判定命题逻辑中的公式是否为重言式的快速算法，则可随之而获得一大批判定问题的快速算法。但迄今这仍是悬案，既未能找到命题逻辑的快速判定算法，也未能证明不存在它的快速判定算法。
1936年，图灵作出了他一生最重要的科学贡献，他在其著名的论文《论可计算数在判定问题中的应用（On Computer numbers with an Application to the Entscheidungs -problem）》一文中，以布尔代数[i]为基础，将逻辑中的任意命题（即可用数学符号）用一种通用的机器来表示和完成，并能按照一定的规则推导出结论。这篇论文被誉为现代计算机原理开山之作,它描述了一种假想的可实现通用计算的机器，后人称之为“图灵机”。 冯·诺依曼 1903年12月28日生于匈牙利，1957年2月8日死于美国。我想知道计算机的 人一定对他不会陌生，它可以称为计算机之父了，现在我们面前计算机内采用的体系结构就是以他的命名的冯·诺依曼结构。
冯·诺依曼小时就十分聪明，1936到1938图灵（另一位伟大的计算机科学家）是普林斯顿大学数学系的研究生，冯·诺依曼邀请图灵当他的助手，可是图灵钟情于剑桥而未能如冯·诺依曼所愿，一年后，二次世界大战使图灵卷入了战争，1934年图灵曾经发表的论文“On Computable Numbers with an Application to the Entscheidungs-problem”。不可不提，在这篇论文中，图灵提出了通用机的概念，冯·诺依曼应该知道了这个思想，至少后来他是不是应用了这个思想却不得而知。冯·诺依曼迅速发现了这种后来被称之为计算机的通用机器的用处在于解决一些实际问题，而不是一个摆设，因为战争的原因冯·诺依曼开始接触到许多数学的分支，使他开始萌生了使用一台机器进行计算的想法，虽然我们现在都知道第一台计算机ENIAC有他的努力，可是在此之前他碰到的第一台计算机器是Harvard Mark I (ASCC)计算器。冯·诺依曼有一种非凡的沟通能力，能够在不同的科学家之间担任一个中介者的角色，虽然这些科学家并不想让别人知道自己的秘密。冯·诺依曼建造的机器名为IAS机，一些由国家实验室建造的计算机不过是IAS机的复本而已。
战后冯·诺依曼继续致力于IAS机的开发工作，并帮助解决氢弹研制中的计算问题。在他死后，它在计算机界的名声并不大，以至于他的传记作家对他在计算机上的贡献也只一笔带过。 “Entscheidungs”是德文，意为“decision”，中文“判定”。希尔伯特23问题中的一个。问题陈述如下：
寻找一种算法，这种算法的输入为–>一个数学命题和描述这个数学问题的语言的全部信息，输出–>根据这个数学问题正确与否输出“是”或“否”。这个算法不需要对它的结论给出任何另外的证明，只需要给出“是”或“否”的回答，且回答必需正确。这个问题来源于莱布尼兹（Gottfried
Leibniz，就是开创微积分的人之一，用“高数”折腾无数中华学子）。他建立了一个机械式计算机，想用来判断一个数学命题的真假。但他突然意识到需要一种规则的语言将数学命题描述清楚，于是就忙着处理这个问题去了。当然最后将这个问题被证明无解了。给出回答的是Church和Turing两个人，他们分别从两个不同方向对这个问题的无解性给出了回答。
Church开创了一种 叫λ
calculus的理论，用来定义“algorithm”，即什么是算法。
Turing推出了他的一个思想模型“图灵机”用来定义算法，后来被证明与Church的 λ
calculus理论是等价的。
最后Church把Entscheidungs
problem划归为自己的理论范畴内，并证明了这个问题的无解。Turing把图灵机的不可解问题——Halting
Problem——约化成了Entscheidungs problem。
人们现在将Church和Turing的结论称为：Church-Turing
Thesis。
Turing, A.M. (1936).
On Computable Numbers, with an Application to the Entscheidungs problem.
Proceedings of the London Mathematical Society. No.2, Vol.42:
230–65.
邱奇-图灵论题
| 邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写都计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言大程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。 论题之等价形式本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求： 一个方法由有限多多简单和精确的指令组成，这些指令可由有限多的符号来描述。 该方法总会在有限的步骤内产生出一个结果。 基本上人可以仅用纸张和铅笔来执行。 该方法的执行不需人类的智慧来理解和执行这些指令。 此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。 “有效方法”这个想法在直觉上是清楚的，但却没有在形式上加以定义，因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。 (如需欧几里得算法之外的范例，请参见数论中的有效结果。) 论题之起源在他1936年年的论文“论可计算数字，及其在判定性问题(Entscheidungsproblem--德语，译者注)中的应用”中，阿兰·图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中，他证明了“判定性问题”是无法解决的。几个月之前，阿隆佐·邱奇在“关于判定性问题的解释”(A Note on the Entscheidungsproblem)一文中证明出了一个相似的论题，但他采用但是递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐·邱奇和史蒂芬·克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)，而递归函数由库尔特·歌德尔(Kurt G?del)和雅克斯·赫尔不兰特(Jacques Herbrand) (G?del 1934, Herbrand 1932)提出的。这两个机制描述的是同一集合的函数，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数(Turing 1936, 263ff).y 论题之成功之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机器(register machine), 埃米尔·波斯特(Emill Post)的波斯特体系, 组合可定义性(combinatory definability)以及马可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇.图灵论题是正确的。但是，该论题不据有数学定理一般的地位，也无法被证明;如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算, 所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算 (或简写为可计算)这一定义良好的概念. 由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题几经不是那么重要了。 论题之哲学内涵邱奇.图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇.图灵论题和物理学之间的关系，还有超计算性(hypercomputation)的可能性。应用到物理学上，改论题有很多可能的意义： 宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇.图灵论题. 宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。 宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰·卢卡斯 (和罗格·本罗泽(Roger Penrose) 曾经建议说人的心灵可能是量子超计算的结果。 实际上在这三类之外或其中还有许多其他的技术上的可能性，但这三类只是为了阐述这一概念。 |
补充材料
• Hofstadter,
Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter
17.
参考文献
• Church, A., 1932, "A set of Postulates for the Foundation
of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church,
A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal
of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the
Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church,
A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University
Press.
• Gödel, K., 1934, "On Undecidable Propositions of
Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the
Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The
Undecidable, New York: Raven.
• Herbrand, J., 1932, "Sur la
non-contradiction de l\'arithmetique", Journal fur die reine und angewandte
Mathematik, 166, 1-8.
• Kleene, S.C., 1935, "A Theory of Positive
Integers in Formal Logic", American Journal of Mathematics, 57, 153-173,
219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness",
Duke Mathematical Journal 2, 340-353.
• Markov, A.A., 1960, "The Theory
of Algorithms", American Mathematical Society Translations, series 2, 15,
1-14.
• Turing, A.M., 1936, "On Computable Numbers, with an Application
to the Entscheidungsproblem", Proceedings of the London Mathematical Society,
Series 2, 42 (1936-37), pp.230-265.
• Pour-El, M.B. & Richards,
J.I., 1989, Computability in Analysis and Physics, Springer
Verlag.
正如美国电脑界有冯·诺依曼一样，在英国电脑的进展中，也有一个有巨大影响力的天才，他就是阿伦·图灵（Alan
Turing）。此人对于电脑技术的发展，有着无可替代的影响。
英国现代计算机的起步的是从纳粹德国的“谜”开始的。“谜”（Enigma）是一种密码电报机，由德国人在一战和二战之间研制成功。“谜”能把日常语言变为代码，通过无线电或电话线路秘密传送。它是一个木箱子，配有一台打字机，箱上有26个闪烁不停的小灯泡，与打字机键盘的26个字母相对应。“谜”的设计无懈可击，有一套极精密的解码设置，非一般的电报密码所能比拟。在内行人看来，平白如话，但在旁人，又是无从索解的天书。因此，这台看似平常的机器，有了“谜”的称号。这样，德国的“谜”引起了英国情报部门高度的兴趣。常规的解码方式奈何不了“谜”，怎么办？
这时，天才的数学家图灵出现了。1931年图灵进入剑桥大学国王学院，开始了他的数学天涯。一到那里，图灵开始崭露头角，毕业后去美国普林斯顿大学攻读博士学位，在那里就发明过一个解码器（Encipher），二战爆发后回到剑桥。
在剑桥，图灵是一个妇孺皆知的怪才，常有出人意表的举动。他每天骑自行车到离公寓3公里的一个叫布雷奇莱公园（Bletchley
Park）的地方上班，因常患过敏性鼻炎，一遇花粉，鼻涕不止，图灵就常戴防毒面具骑车上班，招摇过市，成为剑桥的一大奇观。
他的自行车链条经常在半道上掉落，要是换了别人，早就去车铺修理了。而图灵偏不，他在琢磨，发现这链条总是踏到一定的圈数时下滑，图灵在骑车时就特别留心计算，于是能做到在链条下滑前一刹那戛然停车！让旁人叹服不已，以为是在玩杂耍。后来他居然在踏脚旁装了一个小巧的机械计数器，到圈数时就停，好换换脑筋想些别的问题。图灵的脑袋转得比自行车飞轮还快。
用图灵的脑袋来破译德国的“谜”看来不是什么难事。二战爆发后，图灵成为英国外交部通信部门战时公务员，主要负责解码。他果然不负众望，成功破译了“谜”。而德国人还蒙在鼓里，还以为他们的“谜”能一直迷下去，照用不误，泄露了大量的核心机密，在战事上屡屡遭挫，战后，图灵被授予帝国勋章。至于图灵如何破译“谜”的，由于英国政府严格的保密法令，一直没有公之于世。所以图灵破译“谜”也成为一个“谜”。
早在30年代初，图灵就发表了一篇著名的论文《论数字计算在决断难题中的应用》，他提出了一种十分简单但运算能力极强的理想计算装置，用它来计算所有能想象得到的可计算函数。它由一个控制器和一根假设两端无界的工作带组成，工作带起着存储器的作用，它被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，控制带有一个读写头，读写头可以读出控制器访问的格子上的符号，也能改写和抹去这一符号。
这一装置只是一种理想的计算模型，或者说是一种理想中的计算机。正如飞机的真正成功得力于空气动力学一样，图灵的这一思想奠定了整个现代计算机的理论基础。这就是电脑史上与“冯·诺依曼机器”齐名的“图灵机”。
图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。
此后图灵在国家物理学实验室（NPL）工作，并继续为数字式计算机努力，在那里人发明了自动计算机（Automatic
Computing
Engine，ACE），在这一时期他开始探索计算机与自然的关系。他写了一篇名为《智能机》的文章于1969发表，这时便开始有了人工智能的雏形。
图灵相信机器可以模拟人的智力，他也深知让人们接受这一想法的困难，今天仍然有许多人认为人的大脑是不可能用机器模仿的。而在图灵认为，这样的机器一定是存在的。图灵经常和其它科学家发生争论，争论的问题就是机器实现人类智能的问题，在今天我们看来这没有什么，但是在当时这可不太容易被人接受。他经常问他的同事，你们能不能找到一个计算机不能回答的问题，当时计算机处理多选问题已经可以了，可是对于文章的处理还根本不可能，但今天的发展证明了图灵的远见，今天的计算机已经可以读写一些简单的文章了。
图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器，它于1950写文章提出了著名的“图灵测试”，测试是让人类考官通过键盘向一个人和一个机器发问，这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后，这位人类考官不能确定谁是人谁是机器，那这个机器就有智力了。这个测试在我们想起来十分简单，可是伟大的思想就源于这种简单的事物之中。
现在已经有软件可以通过图灵测试的子测试，软件这个人类智慧的机器反映应该可以解决一些人类智力的问题。在完成ACE之前，图灵离开了NPL，它在曼彻斯特大学开发曼彻斯特自动计算机（Manchester
Automatic Digital
Machine，MADAM）。他相信在2000年前一定可以制造出可以模拟人类智力的机器，图灵开始创立算法，并使用MADAM继续他的工作。
图灵对生物也十分感兴趣，他希望了解生物的各个器官为什么是这个样子而不是那个样子，他不相信达尔文的进化论，他觉得生物的发展与进化没什么关系。对于生物学，他也用它钟爱的数学进行研究，它的研究对他进行计算机的研究有促进作用。它把生物的变化也看做是一种程序，也就是图灵机的基本概念，按程序进行。最后，这位伟大的计算机先驱于1954年6月7日去世，他终生未娶。
约翰.麦卡锡
--"人工智能之父"和LISP语言的发明人
1971年的图灵奖授予提出"人工智能"这一术语并使之成为一个重要的学科领域的斯坦福大学教授约翰.
麦卡锡（ John
McCarthy)。
麦卡锡1927年9月4日生于波士顿。他的父亲是一个爱尔兰移民，做过木匠和渔夫，同时也是一个发明家和工会积极分子，拥有捻船缝机和桔汁冷冻机两项专利。麦卡锡的母亲是来自立陶宛的犹太人，热心于*女*权运动，当过记者。夫妻两人在20世纪30年代都曾参加美国gcd。受父母的影响，麦卡锡对社会问题也比较关注，参与过在加州的Palo
Alto 创办自由大学的活动，倡议过修改"人*权*法*案"（the Bill of
Rights，这是美国于1789年通过的对美国宪法的第一次修正案）。但与他在计算机科学上所做的工作和贡献相比，麦卡锡主要还是一个科学家而非社会活动家。此外，麦卡锡还喜欢攀登、跳伞、驾驶滑翔机等有刺激性和危险性的运动，曾和他的第二任妻子维拉.沃特森(Vera
Watson)一起攀登过世界上不少大山高峰。沃特森是一位程序员，也是世界知名的女登山运动员，是第一位独自攀上西半球第一高峰、位于阿根廷和智利边界的安第斯山脉的阿空加瓜山（海拔6960米）的女性，后来在一次攀登位于尼泊尔中部的阿那波尔那峰（海拔8
075米）的妇女探险活动中不幸遇难牺牲。
麦卡锡是一个天赋很高的人，还在上初中时，他就弄了一份加州理工大学的课程目录，按目录自学了大学低年级的高等数学教材，做了教材上的所有练习题。这使他1944年进入加州理工学院以后可以免修头两年的数学，并使他虽因战时环境（第二次世界大战当时正在进行之中，美国也在珍珠港事件后宣布参战）要在军队中充任一个小职员，占去了部分时间，仍得以在1948年按时完成学业。然后到普林斯顿大学研究生院深造，于1951年取得数学博士学位。麦卡锡留校工作两年以后转至斯坦福大学，也只呆了两年就去达特茅斯学院任教（达特茅斯学院位于新罕布什尔州的汉诺威）。在那里，他发起了并成功举办了成为人工智能起点的有历史意义的"达特茅斯会议"。1958年麦卡锡到MIT任职，与明斯基(L.
Minsky,1969年图灵奖获得者)一起组建了世界上第一个人工智能实验室，并第一个提出了将计算机的批处理方式改造成为能同时允许数十甚至上百用户使用的分时方式（time-sharing）的建议，并推动MIT成立组织开展研究。其结果就是实现了世界上最早的分时系统--基于IBM
7094的CTSS和其后的MULTICS。麦卡锡虽因主持该课题的负责人产生矛盾而于1962年离开MIT重返斯坦福，未能将此项目坚持到底，但学术界仍公认他是分时概念的创始人。麦卡锡到斯坦福后参加了一个基于DEC
PDP -1的分时系统的开发，并在那里组建了第二个人工智能实验室。
麦卡锡对人工智能的兴趣始于他当研究生的时候。1948年9月，他参加了一个"脑行为机制"的专题讨论会，会上，冯.诺伊曼发表了一篇关于自复制自动机制论文，提出了可以复制自身的机器的设想，这激起了麦卡锡的极大兴趣和好奇心，自此就开始尝试在计算机上模拟人的智能。1949年他向冯.诺伊曼谈了自己的想法，后者极表赞成和支持，鼓励他搞下去。在达特茅斯会议前后，麦卡锡的主要研究方向是计算机下棋。下棋程序的关键之一是如何减少计算机需要考虑的棋步。麦卡锡经过艰苦探索，终于发明了著名的α-β搜索法中，麦卡锡将结合的产生与求评价函数值（或称返上值或倒推值）两者巧妙地结合起来，从而使某些子树结点根本不必产生与搜索（这谓之"修剪"--pruning或cutoff）。之所以称为α-β搜索法，是因为将处于取最大值级的结点的返上值或候选返上值PBV（Provisional
Back-up
value）称为该结点的α值，而将处于取最小值级的结点的候选返上值或返上值称为该结点的β值。这样，在求得某结点以下的α值时，就可与其先辈结点的α值相比较，若α≥β，
则可终止该结点以下的搜索，即从该结点处加以修剪，这叫β修剪；而在求得某结点以下的β值时，就可与其先辈结点的α值相比较，若β≤α，则可终止该结点以下的搜索，即从该结点处加以修剪，这叫α修剪。为了说明α-β修剪，我们举一个最简单的例子。设在取火柴棍的游戏中，A、B两人轮流从N根火柴中取1根或2根，不得多取，也不能不取。取走最后一根火柴者胜。用A(n)、B(n)表示轮到A或B时有n根火柴的状态，当n
=
5时轮到A取，则如下图所示，A有两种可能，一是取2根火柴进入B（3），另一是取1根火柴进入B（4）。显然，进入B（3）后，不管B取几根，A必胜，故A必走这一步，余下的分支不必再搜索了。α-β搜索法至今仍是解决人工智能问题中一种常用的高效方法。
至于达特茅斯会议，当东道主的麦卡锡是主要发起人，另外3个发起人是当时在哈佛大学的明斯基（1969年图灵奖获得者），IBM公司的罗杰斯特(N.
Rochster)，信息论的创造人香农。麦卡锡发起这个会议时的目标非常宏伟，是想通过10来个人2个有共同努力设计出一台具有真正智能的机器。会议的经费是洛克菲勒基金会资助的，包括每个代表1200美元加上外地代表的往返车票。会议的原始目标虽然由于不切实际而不可能实现，但由于麦卡锡在下棋程序尤其是α-β搜索法上所取得的成功，以及卡内基-梅隆大学的西蒙(H.
A.Simon)和纽厄尔（A.
Newell,这两人是1975年图灵奖获得者）带来了已能证明数学名著《数学原理》一书第二章52个定理中的38个定理的启发式程序"逻辑理论家"LT（Logic
Theorist）,明斯基带来的名为Snarc的学习机的雏形（主要学习如何通过迷宫），这使会议参加者仍能充满信心地宣布"人工智能"这一崭新学科的诞生。
1959年，麦卡锡基于阿隆索.邱奇(Alonzo
Church)的λ-演算和西蒙、纽厄尔首创的"表结构"，开发了著名的LISP语言（LISt Processing
language），成为人工智能界第一个最广泛流行的语言。LISP是一种函数式的符号处理语言，其程序由一些函数子程序组成。在函数的构造上，和数学上递归函数的构造方法十分类似，即从几个基本函数出发，通过一定的手段构成新的函数。LISP语言还具有自编译能力。具体说来，LISP有以下几个主要特点：
1．计算用的符号表达式而不是数； 2．具有表处理能力，即用链表形式表示所有的数据；
3．控制结构基于函数的复合，以形成更复杂的函数； 4．用递归作为描述问题和过程的方法；
5．用LISP语言书写的EVAL函数既可作为LISP语言的解释程序，又可以作为语言本身的形式定义；
6．程序本身也同所有其他数据一样用表结构形式表示。
已经证明，LISP的这些特点是解决人工智能核心问题的关键。此外，精巧的表机制也是进一步简化LISP程序设计的方便而有力的工具，因此，LISP自发明以来，已经被广泛用于数学中的符号微积分计算，定理证明，谓词演算，博奕论等领域。它和后来由英国伦敦大学的青年学生柯瓦连斯基（R.
Kowaliski）提出、由法国马赛大学考尔麦劳厄（A.
Colmerauer）所领导的研究小组于1973年首先实现的逻辑式语言PROLOG(PROgramming in
LOGic)并称为人工智能的两大语言，对人工智能的发展起了十分深远的意义也吸引了负责设计Algol语言的国际委员会，麦卡锡因此而被吸收为该委员会的成员。Algol中后来采纳了LISP关于递归和条件表达式这些思想。
麦卡锡在20世纪50年代末研究的另一个课题是如何程序能接受劝告从而改善其自身的性能。为此他提出过一个名为Advice
Taker的系统的设想。有资料说，这是世界上第一个体现知识获取工具思想的系统，1968年建成。实际上，这个系统并未最后完成，只是完成了一部分，用LISP语言建立起了一个具有常识(common
sense)的软件，能理解告诉它的是什么，并能评估其行动的后果。但正是在Advice
Taker的开发过程中，启发麦卡锡提出了用"分时系统"代替"批处理系统"的建议，使计算机的使用方式引发了一场革命。
除了人工智能方面的研究和贡献这外，麦卡锡也是最早对程序逻辑进行研究并取得成果的学者之一。１963年他发表的论文"计算的数学理论的一个基础"一文（收录于P.
Braffort和D. Hirschberg编辑的《计算机程序设计和形式系统》--Computer Programming and Formal
Systems, North Holland,
33-70页）集中反映了他这方面的成果。麦卡锡在这篇论文中系统地论述了程序设计语言形式化的重要性，以及它同程序正确性、语言的正确实现等问题的关系，并提出在形式语义研究中使用抽象语法和状态向量等方法，开创了"程序逻辑(logics
of
programs)研究的先河。程序逻辑就是一种"语言"，用这种语言可以无二义地表达程序的各种性质，其语义规定了该语言中各种表达式的意义，而它的一组规则则用同意义相关的方式去操作这些表达式以计算该语言中的各种断言(assertation)的真值。研究程序的逻辑对于帮助人们了解软件是否合理十分重要，它可以用于程序的逻辑对于帮助人们了解软件是否合理十分重要，它可以用于程序验证(program
verification)，自动程序设计，为优化和审计而进行的程序分析等方面。麦卡锡在上述论文中提出的方法是用递归函数作为程序的模型。他以两个链表(list)的"附加"(append)操作为例说明可以用递归的方法定义这个函数，并可以用形式化的方法证明链表的附加操作是满足结合律的(associative
law ),即x @ (y @ z) = (x @ y) @
z。麦卡锡进而证明了用一系列递归定义的函数就完全可能建造大型的软件系统，并用归纳法证明这些系统所具有的性质。麦卡锡所提出的方法是有关程序逻辑研究中第一个比较系统而成熟的方法，曾被广泛地采用。
20世纪70年代以后，麦卡锡又开始研究非单调逻辑。在经典逻辑中，由已知事实推出的结论，决不会在已知事实增加时反而丧失其有效性，因此是"单调的"(monotonic)。但在人类思维过程中，由于信息的不完全和认识的局限性，常常有随着事物的发展变化，原有结论被否定和取消的情况，这就导致了所?"非单调逻辑"(nonmonotonic
logic)。非单调逻辑中有一类是基于最小化语义的最小化非单调逻辑。1980年，麦卡锡在一篇论文中提出了"限制逻辑"或称"限界逻辑"，成为这类非单调逻辑中比较成功的一个体系(见J.
McCarthy：Circumscription--a form of nonmonotonic reasoning. Artificial
Intelligence
,Vol.13，1980，27-39页)。限制逻辑的基本思想是："限制"某个谓词P也就是排除以P的原有事实为基础所建立的大部分模型，而只保留有关P的最小模型。这与人类思考问题时总是在某些条件限制下考虑，也就是只考虑所涉及的个体或关系，而决不去涉及其他个体或关系，是比较相符的。1986年，麦卡锡在AI杂志上就限制逻辑的应用发表了进一步的研究论文："限制逻辑在常识知识形式化中的应用"(Applications
of Circumscription to Formalizing Common Sense Knowledge, AI,
Vol.28，1986，89-116页)，对倡导常识推理和常识研究起了十分重要的作用。
麦卡锡的主要著作有：
《自动机研究》（Automata Studies, Princeton Uni. Pr.,1956,与香农合编）
《信息学：科学美国人之书》(Information：A Scientific American Book, Freeman, 1966)
《形式化的常识：麦卡锡论文选集》(Formalizing Common Sense：Papers by John McCarthy , Ablex
Pub.
Co., 1990, 蒝. Lifschitz 编辑)
除了获得图灵奖以外，麦卡锡在1988年获得由日本INAMORI基金会所设立的KYOTO奖，这个奖主要奖励在高科技方面作出杰出贡献的科学家，麦卡锡是这个奖的第5位获得者。1990年麦卡锡获得美国全国科学奖章
(National Medal of Scien- -ce)。 麦卡锡的图灵奖演说题为"人工智能研究的现状"(The
Present State of Research on Artificial
Intelligence)。但不知什么原因，这篇演说没有发表。在《前20年的图灵奖演说集》(ACM Turing Award
Lectures--The First 20 Years：1966-1985 ，ACM
Pr.)中，则以"附录"(postscript)的形式约请麦卡锡另写了一篇"人工苣一般原理"(Generality
in Artificial
Intelligence),刊于该书257-268页。
麦卡锡现仍在斯坦福大学计算机科学系任教，其电子信箱为： [email protected] 出自《ACM图灵奖——计算机发展史的缩影》（高等教育出版社）
Rule of Simplicity
(by C.A.R. Hoare) -
-
"There
are a number of ways of constructing a software design.
One way is to make it
so simple that there are obviously no deficiencies,
and the other way is to
make it so complicated that there are no obvious deficiencies." -- C.A.R.
Hoare
查尔斯·霍尔
---从QUICKSORT、CASE到程序设计语言程序设计语言的公理化
学过“数据结构”或“算法设计与分析”的人都知道著名的快速排序算法QUICKSORT；编过程序的人大概也都用过实现条件转移的最方便的语句CASE语句。但是你知道这个算法和这个语句是谁发明的吗?它们的发明者就是1990年IEEE计算机先驱奖和1980年图灵奖的获得者英国牛津大学计算机科学家查尔斯·霍尔(Charles
AntonyRichard
Hoare)。当然霍尔之所以获得这两项大奖决不仅仅是因为他发明了QUICKSORT和CASE，而是因为他在计算机科学技术的发展中，尤其是在程序设计语言的定义和设计、数据结构和算法、操作系统等许多方面都起了重要的作用，有一系列发明创造，QUICKSORT和CASE只是其中的一小部分而已。
霍尔于1934年1月11日诞生于英国南部。在坎特伯雷(Canter·bury)的国王学校(King’s
Sch001)度过中学阶段以后，进入牛津的莫顿学院(Merton
College)学习数学，1960年取得硕士学位。之后他进入伦敦一家不大的计算机生产厂家Elliott Brothers公司，为该公司的Elliott
803计算机编写库子程序，从此开始他的计算机生涯。QUICK，SORT就是他在那个时候用原有的SHELLSORT(以算法的发明人D．L．Shell命名的通过调换并移动数据项实现排序的一种算法，发明于1959年)编程时分析了它的缺点而发明出来的。QUICKSORT具有“快刀斩乱麻”的特点，能迅速地对乱序作大幅度调整，特别适合于因多次追加、删除而变得杂乱无章的数据集合。QUICKSORT是利用“分治法”(divide
and
conquer)进行算法设计的一个成功范例，它的发明是霍尔在计算机方面的天才的第一次显露，受到老板的赞赏和重视。第二年，霍尔接受了一个新的任务，为公司的新机型Elliott
503设计一个新的高级语言。但就在其时，他弄到了一份Algol
60报告的复印件，还参加了一个由狄克斯特拉(E．W．D耻stra，首届计算机先驱奖获得者)等人在布赖顿举办的Algol
60培训班，感到与其自己没有把握地去设计一个新的语言，还不如将比较成熟的Algol 60在Elliott
503上加以实现。霍尔和他的同事们的这个想法获得公司同意以后，由霍尔主持设计与实现了Algol
60的一个子集的版本。霍尔在开发初首先制定了明确的目标，即系统要安全可靠，生成的目标码要简洁，工作区数据要紧凑，过程和函数的人口和出口要清晰、严密等，还明确了整个编译过程采用一次扫描等原则。这样，ElliottAl-gol的开发十分顺利与成功，它在1963年中推出以后大受欢迎，成为世界各国所开发的Algol
60的各种版本中在效率、可靠性和方便性等方面的性能指标都首屈一指的一个版本，霍尔本人也从此受到国际学术界的重视。国际信息处理联盟IFIP后来任命霍尔为2．1工作组(WorkingGroup
2．1)的负责人，这个工作组的任务是维护和发展Algol。霍尔果然不负众望，主持设计了Algol
X以继承与发展Algol60。正是在AlgolX的设计中，霍尔发明了CASE语句。CASE语句具有如下形式的语法结构：
CASE E of
C1:S1；
C2:S2；
.
.
.
Cn-1:Sn-1;
Otherwise:Sn
End
其中E是一个表达式，称为“选择子”(Selector)，每个Ci的值为常数，称为“分情形标号”，Si则为可执行语句。CASE语句的含义是：若E的值等于某个Ci的值，则执行其后的Si(i=1，2，3，…，n—1)，否则执行Sn。某个Si或S。执行完之后，整个CASE语句也就执行完毕。由于CASE语句构成多路分支，程序结构清晰、直观，所以CASE语句后来几乎成为程序设计语言的标准，被各种语言广泛采用。在C语言中，没有独立的CASE语句，但它的SWITCH语句(开关语句)实际上是在CASE语句的基础上形成的：
switch E
{case
C1:S1；
case
C2:S2；
.
.
.
case
Cn-1:Sn-1;
[default:Sn]
不同之处有二：一是C；可以是表达式，但计算结果必须仍是常数；二是E的结果若不等于某个Ci(i=1，2，3，…，n—1)的值，则视有无default子句，若有，执行Sn；若无，则什么也不执行，控制转向SWITCH后的语句。显然，这些都是对CASE语句的进一步改进。
霍尔于1968年离开Elliott，离开产业界，原因是作为学者他对程序设计浯言的形式化定义这类更偏重于学术性和理论性的课题更感兴趣。离开Elliott以后，他任职过一年英国国家计算中心主任，发现自己也不适于从事行政管理，因此又转入爱尔兰的昆土大学(Queen’s
University)，从事教学和研究，1977年转入牛津大学。离开Elliott以后，霍尔在计算机科学理论的研究中发挥其特长，作出了许多创造性的重大贡献。首先是1969年10月，霍尔在Communications
of ACM上发表了他那篇有里程碑意义的论文“计算机程序设计的公理基础”(An Axiomatic Basis for Computer
Programming)。在这篇论文中，霍尔提出了程序设计语言的公理化定义方法，即公理语义学(axiomatic
semantics)，也就是用一组公理和一组规则描写语言应有的性质，从而使语言与具体实现的机器无关，而且也易于证明程序的正确性。这是继麦卡锡(J．McCarthy，1985年计算机先驱奖获得者)在1963年提出用递归函数定义程序、弗洛伊德(R．W．Floyd，1991年计算机先驱奖获得者)在1967年提出基于程序流程图的归纳断言法以后，在程序逻辑研究中所取得的又一个重大技术进展。霍尔提出的方法在逻辑上与弗洛伊德提出的方法类似，但不是用流程图而是用代数法，即控制流用以下一些结构表示：
begin al；a2；a3；…；an end
if p
then a1 else a2
while p do a
后面为了方便，我们用到第一个结构时省略首尾的begin和end。
相应于弗洛伊德的验证条件，霍尔引入下列符号：
p{a}q
其意义是：如果在执行。之前P(叫做precondition)成立，则当α执行完了后q(叫做postcondition)成立。
霍尔给出了以下一组证明规则(proof rule)或叫推导规则：
p’ pp{a}qq→q’
1.
p’{a}q’
这个规则中的p’→和q’→q是普通数理逻辑中的断言命题，表示若p’(或q’)成立，则p(或q)成立。这个规则表示，若横线以上的p’→p、p{a}q、q→q’成立，则横线以下的p’{a}q1成立。
2．
P(e){x:=e}p(x)
这个规则表示，如果在将e赋给x之前p(e)成立，则其后p(x)成立。
3．
P{a}qq{b}r
p{a;b}r
这个规则表示的是“传递律”(transitive
law)，即如果执行α之前p成立，α执行完了以后q成立；而如果执行b之前q成立，b执行完了以后r成立，则若在动作序列。和^执行之前P成立，则a和b执行完了以后r成立。
4. p∧r{a}qp∧～r(b)q
p{if r then a else b}q
这个规则中的∧和～是一般数理逻辑中的合取(conjunction)和否定(negation)连接词。这个规则定义了if-then-else的执行取决于precondition
r的值。
5.
p∧q{a}p
p{while q do a}p∧～q
这个规则定义了while循环：p是循环不变量（loop invariant），而q是终止循环的条件。
下面我们举一个例子说明如何用霍尔建立的系统验证程序的正确性。设有计算n的阶乘n！的如下程序：
A: x:1;B
B: while y>0 do
C
C:
x:y×x;y:=y-1
则通过下列霍尔断言可以证明上述程序是正确的，因为这些断言都是真的，而且在霍尔的系统中是可以被证明的，而最后一个断言正是我们所要寻求的结论，因此它们形成对上述阶乘程序正确性的说明。
i.
y>0∧x×y! =n! {x:=y×x}y>0∧x×(y-1)! =n!
[首先y>0∧x×y!
=n!→y>0∧(y×x)×(y-1)! =n!]
然后用规则（2），用x代替y×x]
ii. y>0∧x×(y-1)!
=n!{y:=y-1}y≥0∧x×y! =n!
[类似（i），利用规则（2）]
iii．y>0∧x×y! =n!
{C}y≤0∧x×y! =n!
[对(i)和(ii)用规则(3)]
iv．Y≥0∧y=n∧x=1{B}x=n!
[因为] y=n∧x=1→x×y!
=n!
又因为0！ =1，所以Y≥0∧x×y!
=n! ∧y≤0→y=0∧x=n! →x×y! =n!
根据（iii），利用规则（5），令（5）中p=y≤0∧x×y!
=n!，q=y>0，孥可得(iv)]
v.
y≥0∧y=n{x:=1}y≥0∧y!=n∧x=1
[因为p{x:=1}p∧x=1]
vi.
y≥0∧y=n{A}x=n!
[对（V）和(Vi)利用规则(3)]
因为(vi)中的precondition正好是n的初始条件，而postcondition给出了所需结果，这样就证明了程序可算出n!。
为了给出证明，应该从程序的最后一行开始逐步后推。在这个例子中，(iii)步是最关键的，其中y≥0∧x×y! =n!就是循环不变量或归纳假设(induction
hypothesis)。
利用霍尔提出的这种方法，已经成功地描述了PASCAL等语言，说明了这个方法的巨大威力。但应该指出的是，霍尔的这个方法是不完备的，因为霍尔在开发和建立这个系统时并没有追求系统的完备性，而更多地追求系统的实用性。
在数据类型、数据结构和操作系统设计等方面，霍尔也做了许多开创性的工作。目前广泛流行与应用着的许多概念都源于霍尔的工作。例如，关于抽象数据类型的规格说明(Specification，也叫规约)与其实现是否一致，就是由霍尔于1972年公式化了的。霍尔通过前后断言方法用已经定义了的(抽象)数据类型给出所要定义的新类型的抽象模型，这成为抽象数据类型规格说明的两种主要方法之一，即模型方法(另一方法为基于异调代数理论的代数方法)。对于操作系统的设计与实现十分关键的monitor(监控程序)的概念也是霍尔首先提出，并界定了它的作用与功能，即作为操作系统的核心，在把操作系统看做虚拟机扩充时，monitor是硬件的第一次扩充，它完成中断处理、进程控制与进程通信、存储区动态分配，建立软时钟，驱动设备通道，进行处理机调度。monitor为外面各层的设计提供良好的环境，并提高系统的安全性。
20世纪70年代后期，霍尔又深入研究了运行在不同的机器上的若干个程序之间如何互相通信、互相交换数据的问题，实现了面向分布式系统的程序设计语言CSP。在该语言中，一个并发系统由若干并行运行的顺序进程组成，每个进程不能对其他进程的变量赋值。进程之间只能通过一对通信原语实现协作：Q?x表示从进程Q输入一个值到变量x中；P!e表示把表达式e的值发送给进程户。当户进程执行Q?x，同时口进程执行户!‘时，发生通信，e的值从Q进程传送给户进程的变量x。CSP语言后来成为著名的并行处理语言OCCAM(由INMOS公司为Transputer开发)的基础。20世纪80年代中期，霍尔又和布鲁克斯(S．Brooks)等人合作，提出了“CSP理论”TCSP(Theory
Of Communicating Sequential
Processes)，它与上述CSP不同，但又有联系，这是一个代数演算系统，其基本成分是事件(或动作)。进程由事件和一组算子构造而成。TCSP采用“广播式通信”，而不像程序设计语言CSP中那样采用握手式通信，即只有当并行运行的各进程都执行同一动作时，才发生通信。此外，TCSP采用失败等价作为确定进程等价的准则，这就是著名的“失败语义”。利用失败可以构造TCSP的指称模型。霍尔为失败等价建立了一些公理系统，可以对语义上的等价关系进行形式推导。霍尔在这方面的工作开创了用代数方法研究通信并发系统的先河，形成了所谓“进程代数”(process
algebra)这一新的研究领域，产生了很重要的影响。
霍尔的论著极多，而且都很有份量，有很高的学术水平。有评论说，霍尔每发表一篇论文，几乎就要改变一次人们对程序设计的认识。这虽然是一种夸张的说法，但也说明霍尔的论著确实非常重要。ACM在1983年评选出最近四分之一个世纪中发表在Communications
of
ACM上的有里程碑式意义的25篇经典论文，只有两名学者各有2篇论文人选，霍尔就是其中之一(另一名是首届计算机先驱奖获得者狄克斯特拉)。霍尔人选的两篇论文分别是1969年10月的“计算机程序设计的公理基础”(An
Axiomatic Basis for Computer
Programming，这篇论文的要点我们前面已经介绍过了)，另一篇是1978年8月的“通信顺序进程”(Communicating Sequential
Processes)，该论文奠定了前述CSP语言的基础。CSP现在已推广为“混合通信／顷序进程”(Hybrid Communicating Sequential
Processes)。在这个语言中，有一种特殊的语句称为“连续构件”，可表示一个具体给定初值的微分方程；而原有的通信语句可用来表达事件的起源和发生；语言中的顺序算子、条件算子等则用来刻画连续构件和通信间的耦合关系。
值得指出的是，霍尔还和我国软件学者、中国科学院软件所的周巢尘研究员等合作，在20世纪80年代末由于Esprit的ProCos项目的需要而对基于时态逻辑的逻辑型混合计算模型进行了研究，在这个模型中引入了时段和切变的概念，建立了时段演算，已引起该领域同行的广泛重视。时段用以刻画系统在一个时间区间上的连续变化，而切变则表示事件的发生(离散变量的变化)。在单个时段上，借助连续数学(微分方程理论)推导系统的行为；而在相邻时段间，则用时态逻辑中切变算子的规则，推导系统行为的转化。这种混合计算模型对于设计要求绝对安全。
冯·诺依曼1903年12月28日生于匈牙利，1957年2月8日死于美国。我想知道计算机的人一定对他不会陌生，它可以称为计算机之父了，现在我们面前计算机内采用的体系结构就是以他的命名的冯·诺依曼结构。
冯·诺依曼小时就十分聪明，6岁时就能够心算8位数字的除法，它在匈牙利接受了他的初等教育，并于18岁发表了第一篇论文！在1925年取得化学文凭后，他把兴趣转向了喜爱已久的数学，并于1928年取得博士学位，它在集合论等方面取得了引人注目的成就。1930年他应邀访问普林斯顿大学，这所大学的高等研究所于1933年建立，他成为最早的6位数学教授之一，直到他去世，它一直是这个研究所的数学教授。后来他为成为美国公民。
1936到1938图灵（另一位伟大的计算机科学家）是普林斯顿大学数学系的研究生，冯·诺依曼邀请图灵当他的助手，可是图灵钟情于剑桥而未能如冯·诺依曼所愿，一年后，二次世界大战使图灵卷入了战争，1934年图灵曾经发表的论文"On
Computable Numbers with an Application to the
Entscheidungs-problem"不可不提，在这篇论文中，图灵提出了通用机的概念，冯·诺依曼应该知道了这个思想，至少后来他是不是应用了这个思想却不得而知。
冯·诺依曼迅速发现了这种后来被称之为计算机的通用机器的用处在于解决一些实际问题，而不是一个摆设，因为战争的原因冯·诺依曼开始接触到许多数学的分支，使他开始萌生了使用一台机器进行计算的想法，虽然我们现在都知道第一台计算机ENIAC有他的努力，可是在此之前他碰到的第一台计算机器是Harvard
Mark I
(ASCC)计算器。冯·诺依曼有一种非凡的沟通能力，能够在不同的科学家之间担任一个中介者的角色，虽然这些科学家并不想让别人知道自己的秘密。冯·诺依曼建造的机器名为IAS机，一些由国家实验室建造的计算机不过是IAS机的复本而已。
战后冯·诺依曼继续致力于IAS机的开发工作，并帮助解决氢弹研制中的计算问题。在他死后，它在计算机界的名声并不大，以至于他的传记作家对他在计算机上的贡献也只一笔带过。
取自"http://60.190.84.214:100/wiki/index.php/冯·诺伊曼"
1936年，阿兰·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。
一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程
图灵机停机问题(The Halting Problem)的不可判定性
图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是NO.
这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在. 假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "halt"; 如果 M 不停机, H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:
function P(M) {
if (H(M)=="loop") return "halt";
else if (H(M)=="halt") while(true); // loop forever
}
因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机; 这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说, 图灵机停机问题是不可判定的(undecidable)。 图灵
世界上第一台电子计算机ENIAC,1946年2月诞生于美国宾夕法尼亚大学莫尔学院。但学术界公认，电子计算机的理论和模型是由英国数学家图灵在此前10年即1936年发表的一篇论文“论可计算数及其在判定问题中的应用”(On
Computable Numbers With an Application to the Entscheidungs
Problem)中奠定了基础的。因此，当美国计算机协会ACM在1966年纪念电子计算机诞生20周年，也就是图灵的有历史意义的论文发表30周年的时候，决定设立计算机界的第一个奖项(在此之前，作出杰出贡献的计算机科学家只能获得数学方面或电气工程方面的奖项)，并且很自然地把它命名为“图灵奖”以纪念这位计算机科学理论的奠基人。被称为“计算机界的诺贝尔奖”的这个奖设立至今，已经颁发了34届，共有40名计算机科学家获此殊荣。
阿伦·图灵(Alan
Mathison
Turing)1912年6月23日生于伦敦近郊的自治镇帕丁顿(Paddington，现归属伦敦Westminster区，英国议会大厦和世界闻名的威斯敏斯特大教堂就在这里)。图灵的父亲是英国在印度的行政机构的一名官员，母亲平常也在印度陪伴其丈夫。1926年图灵的父亲退休以后，因为退休金不高，为了节省，他们夫妇又选择在生活费用较低的法国居住，没有回英国定居，因此图灵和他的一个叫约翰的哥哥很少见到父母亲，他们是由从军队中退休的沃德(Ward)夫妇带大的。童年时缺乏父爱和母爱，也许正是图灵自幼起性格和行为就比较怪僻，并最终酿成悲剧结局的一个重要原因。图灵13岁进入寄宿的谢博恩中学(SherboumeSch001)，学习成绩并不特别好，只有数学例外，演算能力特别强。此外，就是擅长赛跑，我们现在还能看到图灵在运动会上参加赛跑中冲过终点时留下的照片。
1931年中学毕业以后，图灵想进剑桥大学最负盛名的“三圣学院”(Trinity
College)，但两次未被录取，只好进了剑桥的另外一所学院——“国王学院”(King’s
College)攻读数学。第一年的课比较浅，图灵很厌烦，没有好好学，结果在剑桥大学特设的一种叫Tripos的荣誉学位考试中只得了“二等”。好在他急起直追，最后毕业时的数学学位考试还是拿了第一等，取得这个成绩的学生在剑桥大学有一个特别的荣誉称号，叫Wrangler。图灵的学位论文课题是关于概率论的中心极限定理(the
Central Limit Theorem of
Probability)的。实际上，由于他在研究这个课题时对前人在这方面所做的工作一无所知，可以说是图灵自己又重新发现了这个定理。1936年图灵因就同一课题所发表的论文而获得史密斯奖(Smith
Prize)。
1935年，图灵开始对数理逻辑发生兴趣。数理逻辑(mathematical logic)又叫形式逻辑(formal 10gic)或符号逻辑(symbolic
logic)，是逻辑学的一个重要分支。数理逻辑用数学方法，也就是用符号和公式、公理的方法去研究人的思维过程、思维规律，其起源可追溯到17世纪德国的大数学家莱布尼茨(Gottfried
Wilhelm
Leibniz，1646—1716)，其目的是建立一种精确的、普遍的符号语言，并寻求一种推理演算，以便用演算去解决人如何推理的问题。在莱布尼茨的思想中，数理逻辑、数学和计算机三者均出于一个统一的目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。但莱布尼茨的这些思想和概念还比较模糊，不太清晰和明朗。两个多世纪来，许多数学家和逻辑学家沿着莱布尼茨的思路进行了大量实质性的工作，使数理逻辑逐步完善和发展起来，许多概念开始明朗起来。但是，“计算机”到底是怎样一种机器，应该由哪些部分组成，如何进行计算和工作，在图灵之前没有任何人清楚地说明过。正是图灵上述1936年那篇标题有些古怪(其中“判定问题”用的是“外文”——德文!)的论文第一次回答了这些问题，提出了一种计算机的抽象模型，利用这种计算机，可以把推理化作一些简单的机械动作。图灵提出的计算模型现在被大家称作“图灵机”(Turing
Machine)。
说来有趣，具有重大科学价值和历史意义的计算模型，并非图灵那篇论文的主题。图灵那篇论文主要是回答同样是德国大数学家的戴维·希尔伯特(David
I-Hilbert，1862—1943)在1900年举行的世界数学家大会上提出的著名的“23个数学难题”中的一个问题的，这个问题涉及逻辑的完备性，即是否所有的数学问题在原则上都是可解的。图灵的论文回答了这个问题：有些数学问题是不可解的。而自动计算机的理论模型则是图灵在其论文的一个脚注中“顺便”提出来的。这可正谓“歪打正着”——图灵这篇传世的论文主要是因为这个脚注，其正文的意义和重要性反而退居其次了。值得回味的是，在科学技术的发展史上，这样的事例并不鲜见。
图灵的论文发表以后，立刻引起了大洋彼岸的美国科学家的重视。年轻的英国数学家的深刻见解和重大创新令他的美国同行十分惊叹，普林斯顿大学立即向图灵发出邀请，于是图灵首次远涉重洋，到美国和邱奇合作，并于1938年在普林斯顿大学取得博士学位。他的博士论文课题是“基于序数的逻辑系统”(Systems
of logic Based ordinals)。在这里，图灵还研究了由乔治·布尔(George
Boole，1815—1864)于1854年创建的逻辑代数，自己动手用继电器搭逻辑门组成了乘法器。这方面的知识和经验为他后来破译德国人的密码打了一个很好的基础。在美国，图灵还遇到了计算机科学理论的另一位重要奠基人、出生在匈牙利的天才科学家冯·诺伊曼(John
yon
Neumann，1903—1957)。冯·诺伊曼因研究博奕论并把博奕论用于商业及军事方面而出名，1930年移居美国后也在普林斯顿大学任教。冯·诺伊曼对图灵十分欣赏并邀请他到他那里工作，但图灵没有接受这个邀请，1938年回到英国剑桥大学。在战争爆发以前，图灵从事的研究工作是Z函数的计算方法(method
for the calculation of the ZetaFunction)。
第二次世界大战爆发后，因图灵正值服役年龄，只能像其他科学家一样，为战争服务。1939年秋季开始，图灵就进入英国外交部设在布莱奇利(Bletchley，在伦敦东北约80km处)的科学研究机构中工作。由于高度机密，英国的保密制度又特别严格，图灵在战时工作的细节至今不得而知。从一些零星透露出来的资料看，图灵这个时期所做的主要工作是破译德军的密码。他用继电器做成被叫做“霹雳弹”(Bombe，因为继电器工作时发出“霹雳啪啦”的声音而得名)的译码机破译了德军的不少“恩尼格玛”(Enigma，这是德国使用的密码机的名称)密报，发现了德军的动向，特别是德军在大西洋上的潜艇的动向，为盟军战胜德国法西斯立了不少功劳。因此战后图灵被光荣授勋，被称为OBE(Officer
Order of the British
Empire，这是对非战斗人员的极高荣誉)。“霹雳弹”后来改用电子管，命名为“巨人”(Colossus)，内含1800多个电子管，被认为是第一台投入运行的数字电子计算机。但英国政府直到20世纪90年代初才解密“巨人”的资料。有人说第一台“巨人”就是由图灵监制的。
关于图灵在战时的表现，流传着不少故事。除了不修边幅、讲话木讷、孤僻等以外，最不可思议和令人难以置信的是，图灵由于对英国在战争中获胜没有信心，把所有的积蓄换成两块银条埋了起来，但后来却记不起埋在哪儿了。
战争期间，图灵曾在1942年因公务再次访问美国，会见了普林斯顿的老朋友，了解了美国在计算机研制方面的最新进展。战后，他没有接受他的母校国王学院的聘请，而去了英国国家物理实验室NPL(National
Physical Laboratory)新建立的“数学部”(Mathematics
Division)，开始了设计与建造电子计算机的宏大工程。他把自己在计算模型方面的理论研究成果和战时在脉冲技术和电子学方面的实践经验结合起来，提出了一个设计方案，这个方案经英国皇家学会的一些院士组成的“评估委员会”(review
committee)讨论通过，同意实行，并授权图灵自行招聘一些适当的工作人员。但在1946年5月以前，图灵一直未能找到称心的助手，因此长期“单枪匹马”。后来终于来了詹姆斯·威尔金森(James
Hardy
Wilkinson，1919—1986，他是1970年图灵奖获得者)。威尔金森也是剑桥大学的毕业生，战时在剑桥数学实验室的军械研究所工作，解决有关弹道方面的问题，精通计算数学。经过一次长谈，双方一拍即合，威尔金森成了图灵得力的助手。他们研制的计算机被起名为ACE(Automatic
Computing Engine)，这个名称是NPL数学部主任沃沫史莱(J．R．Womersley)起的，用以纪念查尔斯·巴贝奇(Charles
Babbage，1792—1871)的Analytical
Engine。威尔金森到来时，图灵设计的ACE已到了第五版。但图灵是一个不善于也不重视保管文档资料的人，前四版的设计早已不知丢到哪里去了。根据图灵的设计，ACE是一台串行定点计算机，字长32bit，主频1MHz，用水银延迟线作存储器，是一种存储程序式计算机。关于“存储程序”(stored
program)的概念，是现代电子计算机的最基本概念之一，也是现代电子计算机的最基本特征之一。ENIAC虽然是世界上第一台电子计算机，但不是存储程序式的，程序要通过外接电路板输入。冯·诺伊曼在ENIAC研制过程中就发现了这个问题，并提出了解决方案。
1945年6月30日，冯·诺伊曼发表了题为“关于离散变量自动电子计算机的草案”的长文，正式提出了存储程序的概念，因此存储程序式计算机被称为“冯·诺伊曼结构”，而他所建议的“离散变量自动电子计算机”也就是后来由宾夕法尼亚大学莫尔学院建成的EDVAC计算机(Electronic
Discrete Variable Automatic
Computer)。但图灵在设计ACE时的存储程序思想并非受冯·诺伊曼论文的影响，而是他自己的构思。冯·诺伊曼本人也从来没有说过存储程序的概念是他的发明，却不止一次地说过图灵是现代计算机设计思想的创始人。图灵在设计ACE时很重视机器速度问题，采取了一系列方法使机器在一定主频下能有较快的指令执行周期，比如后来被称为“最佳编码”(optimum
coding)或“等待时间最少的编码”(minimum latency
coding)的技术，就是ACE首创的。ACE的其他创造包括实现浮点运算的一组子程序(这是图灵交给威尔金森的第一个任务)及双倍字长指令等。
但是ACE计划的实现却遇到了很大困难。当时采取的是“设计”和“工程实施”分离的办法，设计由NPL负责，工程却由另一个政府部门即供应部(Ministry of
Supply)负责，那里有一些搞过雷达、从而对脉冲技术比较熟悉的工程技术人员。双方的难以磨合导致计划进度迟缓，使图灵心情极坏，而NPL的主任查尔斯·达尔文爵土(Sir
Charles
Darwin，提出“进化论”的著名生物学家达尔文的曾孙)是个不太听得进意见的人，眼看问题成堆仍一意孤行，直到1947年才勉强同意在NPL中成立一个电子学小组(Electronics
Group)实施ACE计划，领头的是托马斯博士(Dr．Thomas)。不幸的是，图灵和托马斯两人又互不相容，导致图灵于1948年离开NPL。图灵离开NPL以后，威尔金森接手负责这个项目，采取了一些措施，此外环境条件也有所改善，ACE的样机即Pilot
ACE得以在1950年5月完成。Pilot ACE不是根据图灵在离开NPL时留下的第八版完成的，而是根据早先的第五版设计实现的。Pilot
ACE后来由英国电气公司EEC(English Electric Company)生产了约30台，其商品名为DEUCE.Pilot
ACE(DEUCE)和剑桥大学的莫里斯·威尔克斯(Maurice Vincent
Wilkes，1967年图灵奖获得者)研制的EDSAC(LEO)计算机使英国的计算机技术水平和产业化程度在20世纪50年代处于世界领先水平，可以和美国平起平坐，其中图灵的功劳是不可抹杀的，虽然他没有亲自把ACE的开发负责到底。
离开NPL以后，图灵到曼彻斯特大学新成立的皇家学会计算实验室(Royal
Society Computing
Laboratory)当副主任。曼彻斯特大学在计算机发展史上曾经起过重大的作用，以威廉斯管的发明人F．C．Williams(1911—1977)和汤姆·基尔蓬(Tom
Kilburn)为首的研究小组曾在1948年6月开发出了被称为世界上第一台存储程序式计算机的MARK I，其原型则被称为“婴儿机”(Baby
Machine)。注意，20世纪40年代曾经出现过两个被称为MARK I的计算机，一个是这里所说的MARK I，另一个是美国哈佛大学的霍沃德·艾肯(Howard
Aiken，1900---1973)在IBM的支持下于1944年开发成功的机电式MARK
I，这也正是IBM走上计算机产业之路的开始。为了区别，常常把前者称为“曼彻斯特MARK I”，而把后者称为"IBM MARK I”。曼彻斯特MARK
I后来由Ferranti公司商品化，其第一台于1951年2月安装于曼彻斯特大学，有资料把它说成是世界上第一个商品化计算机型号。图灵加盟曼彻斯特大学不但为它提供了强大的理论支持，也为它做了许多实际工作，据资料记载，图灵在这里曾和其他人合作，设计了纸带输入／输出系统，还编写了程序设计手册。因此，有些图灵传记中说图灵到曼彻斯特大学以后并未参与计算机的实际开发工作，是不太确切的。在这段时间里图灵为计算机科学所作出的又一个杰出贡献是他在1950年10月发表的论文“计算机和智能”(Computing
Machinery and
Intelligence)。在这篇经典的论文中，图灵进一步阐明了他认为计算机可以有智能的思想，并提出了测试机器是否有智能的方法，他称之为“模仿游戏”(lmitation
Game)，而大家现在称之为“图灵测试”(Turing
Test)。在这个测试中，让一个提问者通过电传打字机(现在可以通过计算机键盘)在远处同人或计算机相联系，提出各种各样问题。提问者根据对方的回答确定对方是人还是计算机。如果在提出足够多的问题后提问者仍无法确定对方是人还是计算机，那末就可以认为机器具有人的智能。对自己的论点的正确性，图灵固然有十分的把握，但对它的实现的前景，图灵只是作了非常审慎的估计。图灵预言，在50年以内，计算机可以被编出程序来有效地玩这个游戏，给提问者5min的提问时间，让他作出恰当的判断的机会不多于70％。今年正好是图灵预言以后的50年。对图灵预言是否已经实现，学术界有不同的看法。有人认为图灵预言早就已经实现，因为随着计算机技术的迅猛发展和人工智能技术的进展，计算机早已有了相当程度的智能，其明显标志是计算机会下棋，而且愈来愈精，近年来甚至把卡斯帕罗夫这样的国际特级大师都打败了。另外一种意见则认为图灵预言尚未实现，计算机要通过图灵测试还有待时日。有人估计要30年以后才能出现真正具有人那样智能的计算机。不管专家们意见如何相左，图灵在这个问题上的高瞻远瞩同样是他的伟大天才的一个印证，这是没有疑问的。
在曼彻斯特大学期间，图灵发表的论文中还包括对黎曼(BernardRiemann，1826—1866)Z函数的进一步研究成果，这是他战前曾经感兴趣而研究过的一个课题。这个时期，他对生物学和化学也产生了兴趣，曾经发表有关器官形成的化学基础的论文，探讨海星为什么呈五轴对称，原肠胚在特定的点上形成沟槽等现象。
由于图灵的一系列杰出贡献和重大创造，1951年他被选为英国皇家学会院士。但这之后，他就因私生活方面的问题而陷入困境。图灵是一位同性恋者。在曼彻斯特，他和一位19岁的所谓“街头青年”默里(Amold
Murray)有染。默里把他的一个同伙带到图灵住处，这个同伙本是惯偷，临走时顺手牵羊拿走了图灵一些不太值钱的东西。图灵不知就里，报了案，警察侦破后在审讯中得知了图灵和默里的关系。20世纪50年代，社会对同性恋不像现在这样比较宽容，而被认为严重伤风败俗。1952年图灵被法院传讯，指控行为“极端不当”(grossindecency)。但由于他战后受过勋，社会地位比较高，而且是一个名人，因此没有判他人狱，而是给予一年监外察看，并给予药物治疗，注射雌性荷尔蒙。两年以后，1954年6月7日，离开他的42周岁生日不到两个星期，图灵因吃了在氰化物溶液中浸泡过的苹果而在家中死去。图灵的母亲曾力图使官方宣布图灵为意外死亡，但未被理睬；外界一直说图灵是服毒自杀。但图灵的同事始终认为图灵的死是一个不解的谜，因为对图灵的荷尔蒙治疗早已在一年前结束，这虽然为图灵留下了污点，但图灵毕竟已度过了这场变故，而且他的事业并未受到影响。他既没有留下任何字条，也没有任何线索暗示他要走这一步。不管如何众说纷纭，划时代的科学奇才图灵就这样在他壮年时期无声无息地离开了这个世界，一颗光芒四射的巨星从此陨落，为世人留下了无限的惋惜。
图灵去世后12年开始设立的图灵奖是美国计算机协会ACM(Association for Computing
Machinery)设立的第一个奖项。ACM成立于1947年，也就是世界上第一台电子计算机ENIAC诞生以后的第二年，美国一些有远见的科学家意识到它对于社会进步和人类文明的巨大意义，因此发起成立了这个协会，以推动计算机科学技术的发展和学术交流。
ACM于1947年9月15日在纽约的哥伦比亚大学成立之初的名称是“东部计算机协会”(Eastern
Association for Computing
Machinery)，后来才把Eastern这个词去掉而成为ACM。它的章程和附则是两年后才通过的。章程规定协会的目的有三：
1．推进信息处理科学和技术，包括计算机、计算技术和程序设计语言的研究、设计、开发和应用，也包括过程的自动控制和模拟。
2．促进信息处理科学和技术在专业人员和大众中的自由交流。
3．维护信息处理科学和技术从业人员的权益。
ACM建立以来，积极地开展了活动，目前已成为计算机界最有影响的两大国际性学术组织之一(另一为IEEE的计算机协会，即IEEE Computer
Society)。一些知名的计算机科学家，包括图灵奖获得者佩利、哈明和ENIAC的主要设计者之一莫奇利等都担任过ACM的主席。它下面又建立了几十个专业委员会(正式名称是所谓SIG---Special
Interest
Group)，几乎每个SIG都有自己的杂志。据笔者不完全统计，由ACM出版社出版的定期、不定期刊物有40多种，覆盖了计算机科学技术的几乎所有领域。
图灵奖是ACM于1966年第一个设立的奖项，专门奖励那些在计算机科学研究中做出创造性贡献、推动了计算机科学技术发展的杰出科学家。虽然没有明确规定，但从实际执行过程来看，图灵奖偏重于在计算机科学理论和软件方面作出贡献的科学家。奖金金额不算太高，设奖初期为2万美元，1989年起增至2万5千美元，奖金通常由计算机界的一些大企业提供(通过与ACM签订协议)。由于图灵奖对获奖条件要求极高，评奖程序又极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。从1966年到1999年的34届图灵奖，共计有40名科学家获此殊荣，其中美国学者最多，此外还有英国、瑞土、荷兰、以色列等国少数学者。值得指出的是，迄今为止的图灵奖获得者名单中，不要说没有一个中国人(包括美籍华裔学者)，连法国、德国、日本这样一些发达国家的学者也一个都没有，这是令人遗憾的。当然，如同任何奖都不可能绝对客观、公正、公平一样，图灵奖出现的这种不平衡是可以理解的，因为这个组织毕竟发源于美国，总部也设在美国，受美国人控制；就计算机科学技术而言，确实也是美国的水平最高，贡献最突出。我们只能这样评论：每个图灵奖获得者确实都是出类拔萃的；但出类拔萃的计算机科学家还有很多由于种种原因而没有获得图灵奖。我们相信，只要中国的计算机学者不断努力，勇于创新，随着中国改革开放的逐步深入和对外学术交流的加强，总有一天，会有中国学者昂首走上图灵奖的领奖台。
图灵”趣话
小晏
对于每一个行业和领域来说，几乎都存在一两项令其领域内所有人视为“终极荣誉”的大奖，例如电影业的奥斯卡奖、新闻领域的普利策奖，数学领域的沃尔夫奖和费尔兹奖等等。随着计算机通讯业的迅猛发展，“图灵”这个词频频出现在各个场合，尤其是去年比尔.盖茨携微软高层人员来华一行，期间多次提到“图灵奖”一词，而且大家对获得该奖项的人士更是恭敬有加，好奇之余，我便查阅资料，不想却发现了许多趣事，于是写来与大家分享。
“图灵（Turing）奖”是美国计算机协会（ACM，Association
for Computer Machinery）干
1966年设立的，专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家。设立的初衷是因为计算机技术的飞速发展，尤其到20世纪60年代，其已成为一个独立的有影响的学科，信息产业亦逐步形成，但在这一产业中却一直没有一项类似“诺贝尔”、“普利策”等的奖项来促进该学科的进一步发展，为了弥补这一缺陷，于是“图灵”奖便应运而生，它被公认为计算机界的“诺贝尔”奖。
“图 灵”为 何
如此 幸 运
不少人梦寐以求的国际计算机的最高奖项——图灵奖，为何它如此幸运，真是说来话长。
阿兰·图灵（Alan
Turing），1912年6月23日出生于英国伦敦，他被认为成二十世纪最著名的数学家之一，谁也没有想到他的名字会和计算机产业挂钩。
20世纪的数学界正在热烈的讨论本世纪最伟大的科学发现之一
——昆特.哥德尔的不完全性定理，在那以前，数学家们总认为，一个数学问题虽然要找到答案也许会很困难，但理论上总有一个确定的答案，一个数学命题，要么是真的，要么是假的。而哥德尔的不完全定理指出：在一个稍微复杂一点的的数学公理系统中，总存在那样的命题，我们既不能证明它是真的，也不能证明它是假的。数学家们大吃一惊，发现以往大家认为绝对严密的数学中，原来有令人如此不安的不确定性。每个逻辑学家都在苦苦思索，试图为陷入了危机的数学找到一条出路，这些逻辑学家包括当时在剑桥的贝特朗.罗素(
Bertrand Russell ) 、阿尔弗雷德.怀特海（Alfred Whitehead）、路德维格.维特斯根坦 ( Ludwig
Wittgenstein)
等著名的逻辑学家。这时的图灵正在剑桥求学，他也同样为此问题陷入了困境。
1936年，图灵作出了他一生最重要的科学贡献，他在其著名的论文《论可计算数在判定问题中的应用（On
Computer numbers with an Application to the Entscheidungs
-problem）》一文中，以布尔代数[i]为基础，将逻辑中的任意命题（即可用数学符号）用一种通用的机器来表示和完成，并能按照一定的规则推导出结论。这篇论文被誉为现代计算机原理开山之作,它描述了一种假想的可实现通用计算的机器，后人称之为“图灵机”。
这种假想的机器由一个控制器和一个两端无限长的工作带组成。工作带被划分成一个个大小相同的方格，方格内记载着给定字母表上的符号。控制器带有读写头并且能在工作带上按要求左右移动。随着控制器的移动，其上的读写头可读出方格上的符号，也能改写方格上的符号。这种机器能进行多种运算并可用于证明一些著名的定理。这是最早给出的通用计算机的模型。图灵还从理论上证明了这种假想机的可能性。尽管图灵机当时还只是一纸空文，但其思想奠定了整个现代计算机发展的理论基础。
1945年，图灵被调往英国国家物理研究所工作。他结合自己多年的理论研究和战时制造密码破译机的经验，起草了一份关于研制自动计算机器（ACE：Automatic
Computer Engine
）的报告，以期实现他曾提出的通用计算机的设计思想。通过长期研究和深入思考，图灵预言，总有一天计算机可通过编程获得能与人类竞争的智能。1950年10月，图灵发表了题为《机器能思考吗？》的论文，在计算机科学界引起巨大震撼，为人工智能学的创立奠定了基础。同年，图灵花费4万英镑，用了约800个电子管的ACE样机研制成功，它的存储容量比爱尼亚克[ii]大了许多。在公开演示会上，被认为是当时世界上速度最快、功能最强的计算机之一。图灵还设计了著名的“模仿游戏试验”，后人称之为“图灵测试”。该实验把被提问的一个人和一台计算机分别隔离在两间屋子，让提问者用人和计算机都能接受的方式来进行问答测试。如果提问者分不清回答者是人还是机器，那就证明计算机已具备人的智能（1993年美国波士顿计算机博物馆举行的著名的“图灵测试”
[iii]充分验证了图灵的预言）。
这让我想起前几年IBM公司研制的计算机“深蓝”与国际象棋世界冠军卡斯帕罗夫进行的那场人机大战，最终以“深蓝”战胜卡斯帕罗夫而宣告结束，让我们不得不佩服图灵的天才预言。
现代计算机之父冯·诺依曼[iv]生前曾多次谦虚地说：如果不考虑巴贝奇[v]等人早先提出的有关思想，现代计算机的概念当属于阿兰·图灵。冯·诺依曼能把“计算机之父”的桂冠戴在比自己小10岁的图灵头上，足见图灵对计算机科学影响之巨大。
毒 液 浸 透 苹 果，如 睡 之 死 渗 入 ……
身为一名数学家,
图灵模型研制计算机的梦想在第二次世界大战的爆发中粉碎。当时，德国法西斯正对英伦三岛狂轰滥炸，图灵的祖国危在旦夕,怀着一腔报国热情，图灵前往英国外交部承担“超级机密”研究工作，即主持对德军通讯密码的破译工作。图灵便和历史上著名的布莱奇利公园以及加密电子机械装置ENIGMA联系在了一起。
ENIGMA是德国发明家亚瑟.谢尔比乌斯（Arthur
Scherbius）发明的一种加密电子器,它被证明是有史以来最可靠的加密系统之一，二战期间它开始被德军大量用于铁路、企业当中。英国第40局（英国政府负责破译密码的间谍机构）开始恐慌，因为出现了大量他们无法破译的电文。在整整13年里，英国人和法国人都认为ENIGMA是不可破译的。针对这一情况，40局新设了它的机构——英国政府代码及加密学校（GC&CS
,Government Code and Cipher
School），总部坐落在白金汉郡的布莱奇利公园。在布莱奇利公园有一大批为破译ENIGMA作出卓越贡献的人们，图灵无疑是他们当中最值得叙述的一个。图灵发明了绰号为“炸弹”
（Bombes）的解密机器，他被看成一位天才解密分析专家。战争结束，布莱奇利公园被关闭，“炸弹”被拆毁，所有战时有关密码分析和破译的档案资料都被销毁，直到1967年波兰出版第一本关于波兰破译ENIGMA方面的书，以及1974年温特伯坦姆写的《超级机密The
Ultra
Secret》一书出版，人们才知道图灵在分析解密方面的贡献。
1938年迪斯尼公司著名的动画片《白雪公主和七个小矮人》上映，图灵也观看了这部影片，在后来的日子里，他的同事常常听见他哼电影中巫婆王后泡制毒苹果的台词：“毒液浸透苹果如睡之死渗入……”而图灵的一生正是在这首歌词中结束。
图灵在他生命的最后时光，没有机会看到自己被当作一个解密英雄来尊敬，相反，由于他同性恋的性倾向而倍受折磨。1952年因小偷入室行窃，图灵向警察报了案，但他却忘了向警察掩藏他和另一位男士同居的事实，同年他被警方逮捕，以“有伤风化罪”罪名遭到起诉，并被判为有罪。而这期间，他不得不忍受报纸媒体对他案件的公开全面报道。性倾向被公开，私生活曝光于大众，政府也取消了他情报部门的工作。他的脾气变的躁怒不安，性格阴沉郁悒。1954年6月8日，人们在图灵的寓所发现了他的尸体。他在自己的住处服用沾过氰化物的苹果而自杀。临死的前夜，也许图灵的耳边还回响着那首歌：“毒液浸透苹果如睡之死渗入……”
迄今为止，作为计算机界“诺贝尔奖”的图灵奖已走过了36个春秋。40多位图灵奖得主均对计算机科学与技术的发展创新做出了杰出贡献。他们在珍惜自己所获崇高荣誉的同时，也深切怀念阿兰·图灵这位在计算机创新史上永放光芒的先驱。
--------------------------------------------------------------------------------
[i]
1854年，英国数学家乔治·布尔（George
Boode）出版了名著《布尔代数》。书中用“真”、“假”两种逻辑值和“与”、“或”、“非”三种逻辑运算把形式逻辑归结为一种代数。
[ii]
“爱尼亚克”是世界第一台实用数字电子计算机，1946年2月15日在宾西法尼亚大学正式投入运行。
[iii]该次测试评判员与封闭在密室的计算机或人进行15分钟的交谈，然后根据交谈的印象判断交谈对方是人还是计算机。其中“PC理疗3号”
让评判员误认为“他”是一名聊天高手，而另有两位评判员误将一位小姐指认为计算机。所以充分证明了图灵预言的正确性。
[iv] 约翰·冯·诺依曼 （ John
Von
Nouma，1903－1957），美藉匈牙利人。提出了著名的"冯·诺依曼机"设想，其中心就是有存储程序原则——指令和数据一起存储．这个概念被誉为\'计算机发展史上的一个里程碑"，它标志着电子计算机时代的真正开始，指导着以后的计算机设计。
[v] 查尔斯·巴贝奇, 英国人。
他写出了世界上第一部关于计算机程序的专著，他发明的解析机是现代电子计算机的雏形。
