◇◇新语丝(www.xys.org)(xys4.dxiong.com)(www.xysforum.org)(xys2.dropin.org)◇◇ 孤独的破译者和他的计算机器（修订稿） 作者：若奇 　　他出生于伦敦，在远离父母的环境中孤独地长大。从小学到中学，他由于性 格离群和糟糕的文科成绩而饱受诟病。但他却从学习数学，阅读相对论和量子力 学中获得莫大乐趣。从中学开始他可能不自觉地发展了同性恋的性取向。他的第 一个精神“恋人”，一位才华横溢、与他对自然科学有着同样热爱的高年级同学 的突然去世，对他打击甚深，既让他永远丧失了对宗教的信仰，也激发了他揭开 人类智能活动秘密的最初愿望。 　　在剑桥大学国王学院，他受到哥廷根数理逻辑学派的熏陶。大学毕业后的第 二年，24岁的他就以3６页的一篇传世之作奠定了他在计算机科学史上的地位。 二次大战中他领导英国情报机构“第八室”，为破解德国海军“恩尼格玛”密码 系统立下汗马功劳，对盟军在大西洋海战中取得压倒性优势贡献巨大。二战后他 在英国国家物理研究所设计的ACE计算机被认为是第一台真正意义上的现代计算 机。1950年他的另一篇开创性论文奠定了计算机人工智能的基础。他作为世界上 第一个计算机“个人”用户和第一个专职程序员，使用曼彻斯特大学“Mark-I” 计算机，单枪匹马地创立了另一门学科“形态发生学”。他兴趣广泛，多才多艺， 在数学，量子力学，地学，化学和生物学等方面都卓有建树。 　　他性格孤独，行为乖僻，有些害羞。因为他公开的同性恋取向，50年代初冷 战开始后他失去了从事国家机密活动的资格。1952年，40岁的他被依据当时英国 法律指控非法进行同性恋活动，他高傲而不肯为自己抗辩，但为了避免坐牢从而 得以继续他的研究，他不得不接受令他蒙羞的“激素治疗”。他身心俱焚，形吊 影单，1954年6月的一天，他被发现死于寓所的床上，身边有一只被咬去几口的 苹果。检验证明这只苹果被剧毒氰化物浸泡过。他的死充满疑云，但被警方判定 为自杀。也许，他以无声的抗议走完了他短暂，辉煌而悲剧的一生。他没有留下 一句遗言。 　　2009年9月10日，英国政府正式为他洗去沉冤。布朗首相代表英国政府向他 因同性恋遭受的不公道歉。他说，“我代表英国政府、以及所有因他的工作而自 由生活的人们向他说：‘我们很抱歉，你本应得到更多的奖赏。’” 　　这个人，就是天才的英国数学家阿兰?图灵（Alan Turing，1912-1954）。 　　二十世纪是人类历史上科学技术发展最快的世纪。100年间，涌现了大量对 世界产生重大的影响的科学和技术发现，包括量子力学，相对论，抗生素，基因 科学，飞机，电视等等。但是，在上个世纪结束的时候，如果要评选一项已经渗 透至人们日常生活的所有角落，对人类的工作和生活影响最大的本世纪科技发展 的话，则非计算机莫属。 　　如同提到经典力学人们必然联想起牛顿，提到相对论人们必然联想起爱因斯 坦，每项里程碑式的人类文明发展都有其领军巨匠大师。计算机的发展也不例外。 阿兰?图灵的名字永远与计算机科学联系在一起。作为人类创造性心智和抽象思 维的典范，“图灵机”亦将永垂科学青史。“图灵测试”仍是迄今为止公认的判 定计算机是否具有智能的标准。 　　为了理解图灵的主要贡献，让我们简单回顾一下19世纪20世纪之交数学界的 状况。 　　尽管数学在当时已经有了长足的发展，人们仍然对有关实数的一些基本性质 感到困惑。在解决实数是否可数的过程中，集合论创始人康托（Georg Cantor, 1845-1918）发展了包含无限元素的集合的理论。康托发现，无限集合的真子集 可以和原集合一样“大”，有可数的无限和不可数的无限等等，这些概念都不是 直观的。据说，康托因为思考这些无限的大小和可数性而走火入魔，后半生生活 在半疯的状态中，出入精神病院，在数学，音乐，哲学和神学之间游走。 　　人们意识到，为了更准确地理解世界，必须借助严格和可靠的工具。以欧几 里德几何原理为代表的公理化方法渐入佳境。 　　数学家们开始以前所未有的热情和异乎寻常的严格来重新构造数学的基础。 皮亚诺(Giuseppe Peano, 1858-1932)建立了以公理系统为基础的自然数的运算 系统。弗雷泽(Gottlob Frege, 1848-1925)则更进一步，在集合论和数理逻辑的 基础上建立了实数的运算系统。著名数学家，近代数学的代表人物，哥廷根学派 的掌门人希尔伯特(David Hilbert, 1862-1943)在实数系统的基础上将欧氏几何 全部重新推导，将其牢固地建立在前所未有的严格的数学根基上。 　　到了１９世纪行将结束的时候，数学大厦似乎已经构建得十分宏伟坚固。以 希尔伯特为代表的数学家们对解决残存的数学问题相当乐观。１９００年８月， 在巴黎召开的第二届世界数学家大会上，希尔伯特应邀致辞，他豪情满怀，信心 爆棚地宣称： 　　无论这些难题看起来多么难以解决，无论我们现在在它们面前如何困惑无助， 我们仍坚持这样一个信念：这些难题的解决一定会遵循有限的纯粹逻辑的过 程。。。每个数学问题都必然可解的这一信条是对数学家们的强有力激励。我们 听到来自内心的永恒召唤：我们面临难题。我们要去寻找它的解。通过纯粹推理， 我们一定能找到它。因为在数学中，绝对没有“我们不可能知道”！ 　　接着，他列举了他所认为新世纪应该解决的２３个数学难题（其中许多至今 仍未解决），并挑战他的数学同行在新世纪中解决它们。 　　不仅在数学界，而且在诸如物理，艺术，乃至社会方方面面，人们普遍抱有 乐观情绪，认为新的世纪会带来各种遗留问题的彻底解决。人类即将达到灿烂的 顶峰。 　　２０世纪带来的，却几乎是彻底的相反。 　　艺术上的反叛首先引人注目。抽象派的立体、残缺不全的几何图形颠覆了人 们对古典美的欣赏。音乐界从斯塔文斯基开始，喧闹而不和谐的“杂乱无章”， 使得晚期浪漫主义风格的瓦格纳和德彪西显得过于柔顺。物理学上的冲击来自１ ９０５年，爱因斯坦的几篇划时代论文彻底颠覆了牛顿经典力学对时空的认识。 １９１４年的一次世界大战粉碎了人类和平的梦想，同时催生了数十年的以失败 而告终的人类大规模社会主义试验。 　　在数学界，“破坏”也是料想不到的“天翻地覆”。 　　世纪初的进展似乎势如破竹。雄心勃勃的数学家罗素（Bertrand Russell, 1872-1970,就是那个从英国维多利亚女王时代开始发表数学论文，最终活到抗议 越战的诺贝尔文学奖获得者，大名鼎鼎的“哲学家”罗素），和他的导师怀特黑 (Alfred Whitehead, 1861-1947)，在１９１２－１９１３年分三卷出版了长达 两千多页的《数学原理》。罗素用了和牛顿的等身名著类似的书名，正是表现了 他的自信。几年前，他在思考集合论问题时提出了后来以他名字命名的“罗素悖 论”：一个只包含所有不含自身的集合的集合，包含不包含它自己？简单的比方 就是那个著名的“理发师悖论”：一个只给所有不给自己修面的人修面的理发师， 给不给自己修面？他写信给奠定了集合论基础的弗雷泽求教，立刻使得弗雷泽 “精神崩溃”，无法回避他毕生的工作存在这样无法自圆其说的“漏洞”。罗素 自己担起了为数学拨乱反正的重任。他试图将集合分成不同的类型，每个类型只 能包含特定的类型，从而避免类似理发师悖论那样由于自我引用导致的悖论。他 和怀特黑用了几十页的篇幅，最终成功地证明１＋１＝２（不是哥德巴赫猜想， 而是初等算术）！ 　　顺便提及，1957年，纽维尔(Allen Newell, 1927-1992)等人使用计算机证 明了《数学原理》中的许多定理。他们写信将结果报知罗素。罗素不无调侃地回 信说，“得知《数学原理》现在可以被机器写出，我十分惊喜。可惜我和怀特黑 在浪费十年心血写出此书之前不知道这一可能”。 　　希尔伯特进一步明确了公理系统的四大要素： 　　独立性：公理是最简约的，无冗余的。 　　一致性：从公理出发，按照推理规则，不会推出相互矛盾的命题。 　　完备性：从公理出发可以推出所有的真命题。 　　可判定性：存在一个有限步骤的一般过程，可以判定任意一个命题的可证明 性。 　　希尔伯特和他的学生艾克曼(Wilhelm Ackermann, 1896-1962)在《数理逻辑 原理》一书中建立了后来被称之为“一阶谓词演算”的逻辑系统，其中特别包括 了完备性和可判定性的的讨论。 　　奥地利人哥德尔(Kurt G?del, 1906-1978)的出现，先是给了希尔伯特们一 个志在必得的微笑，而后给了他们狠狠一击。 　　哥德尔在１９２９年首先证明，希尔伯特的一阶谓词逻辑系统确实是完备的， 能够导出所有真命题。可以想象希尔伯特们会稍带不屑地说，“不早告诉你了”。 １９３０年，重磅炸弹横空出世。哥德尔进一步证明，如果将算术运算公理引入 一阶谓词系统，则由此而成的算术运算系统是不完备的，即存在这样的命题，它 们的真伪是不可证明的。这个结论的一个前提是，算术运算系统是一致的。由此 自然得到，一致性的证明不可能从系统内部完成，即算术运算系统的一致性不能 由其自身证明！ 　　颠覆是彻底而毁灭性的。希尔伯特和罗素赖以建立数学大厦的根基居然自己 就是建立在沙滩上。据说，希尔伯特听到这个结论后“相当愤怒”。罗素则彻底 丧失了对数理逻辑的兴趣，不知是写作《数学原理》耗尽了他的心血，还是哥德 尔定理击碎了他的信心。用他自己的话说，“从此我发现我对抽象问题的处理能 力肯定是大大降低了”。他改而倾心哲学和文学，关注社会事务。当他在１９５ ０年获得诺贝尔文学奖时，人们早已忘记他曾经是个数学家。另一个当时业已蜚 声数学界，以公理系统将量子力学形式化的哥廷根大学逻辑学家冯?诺依曼(John von Neumann, 1903-1957)，从此放弃了纯粹数学的研究，而１０多年后却因对 现代计算机的奠基和发展的贡献而青史留名。 　　然而，希尔伯特应该还存有希望。哥德尔的结果并未解决“可判定性”问题。 哥德尔只是证明了，逻辑系统中存在不可能判定真伪的命题。然而，一个系统是 不完备的，并不等于不存在一般的判定过程，使得可以判定其中任意一个命题是 否可证。在哥德尔不完备定理出世以后，如果还能证明存在这样的一般过程，退 而求次，看起来还是可说很圆满了。 　　最后的“致命”一击，来自美国数学家丘奇(Alonzo Church, 1905-1995)和 英国数学家图灵。１９３６年，两人几乎同时，却是独立地循着完全不同的途径， 证明了“判定问题”的不可解性。即不存在一般的过程，可以判定任意一个命题 在一阶谓词逻辑系统是否可证。丘奇的方法是“兰姆达演算”，它现在只存在于 数理逻辑及其相关的若干狭窄研究领域中，虽然其对现代计算即程序语言如ALGOL, LISP和APL等等的发展也曾有重要影响。图灵的工具，则是大名鼎鼎的“图灵 机”。图灵机对后世产生了深远的影响，特别是对２０世纪以来的计算机发展起 到并且继续发挥着革命性作用。 　　简单地说，图灵在其划时代论文《论可计算数及其对判定问题的应用》中作 出了以下开创性贡献： 　　一． 定义了一种抽象的计算机器 　　二． 证明了能够模拟任意计算机器的通用计算机器的存在性 　　三． 证明了存在任何计算机器都不能解决的问题 　　那么，图灵机到底是怎样一个神通广大的机器？让我们跟随图灵的论文，进 入图灵机的王国。 　　对于图灵而言，他的计算机器是一种思维模型，是只存在于纸上或头脑里， 模拟人们演算活动而简化到了最基本操作的抽象思维工具。这种抽象完全摈弃现 实世界时间和空间的限制，从而得以揭示事物的本质。 　　图灵试图将人的计算过程还原为最基本的若干机械操作。人在演算数学问题 时，面前有张写着算式的纸，脑子里记着演算规则。演算过程的任一时刻，人只 关注于算式的某一部分和某一特定规则，并据此写下新的数字，或擦除已有数字， 然后将关注转向算式的另一部分和另一规则，直到演算完毕。图灵论证说，这些 规则一定是有限的，否则就会由于状态无限接近而不可区分。 　　这是天才的抽象。图灵正是据此来构造他的计算机器。 　　图灵机由有限的状态（图灵原文中称为“m-配置”）组成。可把状态看作是 计算规则的模拟。机器被送进一条分成连续“格子”的“带子”，这些格子上可 以写有数字或符号。显然，带子是模拟写着式子的纸。任何时刻机器只能“看到” 当前一个格子。每个状态“告诉”机器，根据当前看到的符号，采取何种操作， 以及下一个状态是什么。图灵机的操作非常“原始”，只包括左移一格，右移一 格，擦去当前格子的符号，或者在当前格子写下新的符号。状态和当前符号构成 图灵机的一个“配置”。“配置”完全决定了图灵机的行为。计算机器“写出” 的０和１的序列就是机器计算出来的结果。 　　就是这些。没有复杂的“指令”，没有五花八门的输入输出，没有多少ＧＢ 的存储器，没有强大的“ＣＰＵ”或控制器。甚至连后来出现在许多介绍图灵机 的文章中的“读写头”，在图灵原文中也是隐含的。在用惯了现代计算机的人们 看来，图灵机可以说是“土得掉渣”。 　　那么，这样“简陋”的机器到底如何工作呢？ 　　图灵在论文中给出了两个具体计算机器的例子，一个计算二进制０.０１０ １０１。。。（十进制的１／３），另一个计算超越数０.０１０１１０１１１ ０１１１１.。。。我们来看计算1/3的例子。我们只需一条空白带子和四个状态 来构造这个图灵机： 配置 行为 状态　 当前符号 操作 下个状态 ―――――――――――――――――――――――― ｂ 空白 写0，右移 ｃ ―――――――――――――――――――――――― ｃ 空白 右移 e ―――――――――――――――――――――――― e 空白 写1，右移 f ———————————————————————— f 空白 右移 b 　　初始状态ｂ下，机器在当前格子上写1，然后右移一格，“转到”状态ｃ。 ｃ看到当前格子是空白，于是右移，然后转到状态e。e看到的仍是空白，于是写 1，右移，并转回状态b。如此永远“循环”下去，永不停歇。机器“写”出的结 果是010101.．．。按图灵的约定，结果应按前面加上小数点理解，于是我们得 到 0.010101．．．，也就是十进制的１／3。注意，根据图灵的定义，只有永远 不停“写出”0或1序列的机器才是正常的，“好”的机器。 　　细心的读者也许会发现，这个图灵机实际上是隔一格打印一个数字。这正是 图灵的匠心所在。图灵将带子上的格子分为F-格（数字格）和E-格（可擦除符号 格）两类，一个F-格跟着一个E-格。计算结果由F-格表示，E-格则用于“打标 记”，写特殊符号，起到“临时存储”的作用。对上面这个简单图灵机而言，还 用不到E-格。 　　图灵机的操作是如此原始，以至于连进行简单加减运算都需要许多繁复步骤 才能完成。如果要计算更复杂的问题，岂非要算到“地老天荒“？但图灵对这些 具体运算根本毫无兴趣。他所关心的不是要花多少时间，需要多长的带子才能完 成某个计算，而是可不可能完成它。 　　图灵定义抽象计算机器的方法亦有很大弹性，改变一些细节并不影响可计算 的范围。下面的例子是一个对原始图灵机定义略加改造的图灵机，它的“输入” 是一条所有格子都是空白的带子，它的功能是依次打出所有正整数（也就是完成 加1操作）： 配置 行为 状态　 当前符号 操作 下个状态 ―――――――――――――――――――――――― b 空白 P0 i i 0 P1 r 1 P0,L i 空白 P1 r r 空白 L i 其他符号 R r 　　其中操作Pn（Print）意为在当前格子打印n，P0即打印0。L（Left）和 R(Right)分别意为左移或右移一格。状态b可视为起始操作，打印数字0，然后转 到状态i（increment，加1）。根据当前符号，i可以有三种动作。如果当前符号 是0，则将其改为1，这同时也就完成了加1操作。如果当前符号是1，则将其改为 0，然后左移一格（进位），重复i操作。如果当前符号是空白，说明进位到了新 的最高位，于是打印1。然后转到状态r（rewind，回到最后一位有效数字）。这 个图灵机依次打印0，1，10（十进制2），11（十进制3），100（十进制4） 等 等。读者可以看到，这个“加法器”对原始图灵机有多处修改，例如，它每次新 打印的数字都覆盖了前一个数字；它不使用E-格，也不隔格打印；它的结果向左 方而不是向右方“延伸”，等等。 　　图灵在论文的随后几页为我们构造了完成诸如搜索，复制，擦除，“跑”到 带子最左端，跑到带子右端最后一个格子，比较，打标记等等更为复杂动作的状 态。特别的，他引入了“公共任务”的概念，用可以带参数的m-函数表示。以此 简化图灵机的说明。他很快就在论文中把这些函数称为“指令”。我们也可以看 出这些函数和现代计算机程序语言中的子程序，函数，循环，递归调用等构造的 类似。 　　事实上，图灵在真正的自动计算机出现前１０多年就开始“编程”了。图灵 将使用这些函数构造他的“通用计算机器”。 　　我们再来看一个图灵论文中稍为复杂的m-函数的例子。“擦除从起始符号起 的第一个α”的函数e是这样定义的： e(C,B,α) f(e1(C,B,α),B,α) e1(C,B,α) E C 　　这里的E表示“擦除当前符号α”。m-函数e擦除第一个α，然后转到C。如 果不存在α，则转到B。函数e的定义“引用”了一个已经定义过的“搜索函数” f，f完成搜索从起始符号э开始的第一个α的功能。如果找到这样的α，机器转 到状态C，否则转到状态B。在函数e的定义中，C实际上e1（C, B，α）。 　　图灵接着定义了函数e的另一个版本： e(B, α) e(e(B, α),B, α) 　　这个只有两个参数的e“神通广大”。它首先“调用”三参数的e擦除带子最 左边的第一个α,然后转到三参数的e的第一个参数表示的状态，而这个状态正好 又是两参数的e。于是又去“调用”三参数的e，擦除当前的第一个α（也就是原 来的第二个α），等等，直到所有的α都被擦除，机器转到状态B。了解计算机 编程的读者已经看出，这里包含了计算机程序设计中的递归调用，以及许多老一 代程序语言都不支持的函数“overloading”。图灵的思想确实大大超前于时代。 　　图灵机也可以视为“算法（algorithm）”的体现。算法以有限的符号，有 限的步骤，精确地描述一类计算过程。实际上，图灵机后来被广泛地用于算法研 究。 　　图灵机的计算结果是一个可计算序列。显然，对一个可计算序列，可以构造 不同的图灵机，它们的计算结果相同。为了用一种标准方式表达图灵机的结构， 他将图灵机的配置“规范化”一个五元组 　　（当前状态，当前符号，要写的新符号，移动方向，下一状态） 　　如果将所有m-函数展开，任何图灵机都可由这样一组有限的五元组表示。为 了规范化，图灵规定，擦除操作相当于打印空白符号，保持当前符号不变相当于 打印当前符号。然后将所有的配置，符号和动作都分别排上序号，比如，对某个 特定的有20个状态，使用15个符号的图灵机，状态用带下标的q表示，即ｑ从q１ 到q２０，符号用带下标的Ｓ表示，即从S１到S１５（其中S0是空白，Ｓ１是数 字０，Ｓ２是数字１）。再以字母A代替q的下标：状态ｑ１表示为ＤＡ，ｑ２表 示为ＤＡＡ，qi表示为D后跟随i个A; 用字母C替代符号S的下标：Ｓ１表示为Ｄ Ｃ，Ｓ２表示为ＤＣＣ， Sj表示为D后跟随j个C等等。动作用L或R表示右移和或 左移，用N表示不移动。这样，计算１／３的图灵机可以写成下列标准表达式 （S.D, Standard Description，其中分号分开各个五元组）： ＤＡＤＤＣＲＤＡＡ；ＤＡＡＤＤＲＤＡＡＡ；ＤＡＡＡＤＤＣＣＤＡＡＡＡ；ＤＡＡＡＡＤＤＲＤＡ； 　　图灵实际上是用有限的符号为他的计算机器编码。进一步，如果用数字表示 每个不同字母，比如１表示Ａ，２表示Ｃ，３表示Ｄ，４表示Ｌ，５表示Ｒ，6 表示N,７表示分号；则数字 ３１３３２５３１１７３１１３３５３１１１７３１１１３３２２５３１１１１７３１１１１３３５３１７ 　　就是该图灵机的标准表达数（D.N）。D.N（亦即S.D）唯一地确定一个图灵 机的结构，也就是唯一一个可计算序列。反过来，对每个可计算序列，至少存在 一个标准表达数。不难想象，绝大部分任意正整数都不是一个合格的图灵机的标 准表达数。事实上，最小的可作为图灵机标准表达数的正整数是３１３３４３１ ７（只打印空格！因此，这个图灵机按图灵的定义是一个不好的机器）。最小的 完全符合图灵定义的“好”图灵机标准表达数是313325317（计算0.1111.。。）。 　　图灵还定义了“完全配置”的概念。在图灵机工作的任一阶段，被查看的格 子的序号，带子上的全部符号，以及当前的状态，构成此阶段的图灵机的一个 “完全配置”。形象地说，这就是图灵机的一个“快照”。 　　绕了这么大一个圈子，图灵到底要干什么？别急。好戏才刚开场。 　　图灵下面要做的，是一个绝对天才的创造：他要构造一个“通用计算机器”， 只要给这台机器提供写有某个图灵机的标准表达的带子，就可以模拟这个图灵机 的计算，得出相同的可计算序列。图灵论文的第６和第７节详细给出了通用图灵 机的构造和所有状态，用到了我们上面提到的那些m-函数。图灵证明，如此构造 的这个通用图灵机的计算结果正好就是提供给它的标准表达所代表的那个图灵机 的结果。 　　对通用图灵机构造的详细描述超出本文的篇幅。粗略地说，其“输入”是写 有任一欲被模拟的特定图灵机的标准表达式（由D,A,C,L,R,N和；编码而成）的 带子，“输出”是被模拟的图灵机的一个个相续的完全配置，以及每个完全配置 所对应的当前打印数字。这个相续的数字序列正是被模拟图灵机的计算结果。如 此，则通用图灵机可以“惟妙惟肖”地模拟任一特定图灵机的工作。 　　到目前为止一切似乎进展顺利。我们已经有了神通广大可以模拟任何图灵机 的通用图灵机。图灵还将给我们带来何种惊喜？ 　　不幸的是，图灵很快就给我们的热切期待浇上一盆凉水：图灵机并非万能。 利用通用图灵机，他巧妙地证明了，不可能构造这样一个图灵机，当给它提供任 意一个图灵机的标准表达后，能判定该机器是否是“好”的（即是否能够无休止 地打印数字），甚至不能判定任意一个图灵机是否最终会打印一个0。 　　尽管通用图灵机“仿谁象谁”，但它并无“三岁看小，七岁看老”的未卜先 知的本事。 　　图灵论文的最终目的是证明希尔伯特“判定问题”无解。为此，图灵将图灵 机的标准表达和数理逻辑的一阶谓词演算联系起来。 　　一阶谓词是这样的一类逻辑表达式，例如 （ｘ）（ｙ）（Ｇ（ｘ，ｙ）－＞　Ｇ（ｙ，ｘ）） 　　式子的意义可以不同，但表示某种交换律，对偶关系。比如一个解释是， （ｘ），（ｙ）表示对所有的人ｘ和ｙ，Ｇ（ａ，ｂ）表示“ａ是ｂ的亲戚”。 －＞表示“可推出”，“隐含”。在上述解释下，式子的意思是，如果ｘ是ｙ的 亲戚，那么ｙ也是ｘ的亲戚。 　　图灵用若干逻辑式来表达图灵机配置的五元组，这样，一个图灵机就可以用 逻辑式的“逻辑积”来表达。然后，通过将希尔伯特的“判定问题”表达为一个 更为复杂的逻辑公式，成功地将问题转化为“如果判定问题有解（即存在一般判 定过程），则存在一个图灵机，它能判定被它模拟的图灵机最终是否打印０”。 我们已经知道，这样的图灵机不存在，因此，一般的“判定过程”不存在。 　　至此，图灵圆满地解决了希尔伯特的判定问题。 　　以图灵机作为工具，图灵继而证明了一大类数字(包括π和е)和函数是可被 图灵机计算的。不仅如此，图灵机还能证明希尔伯特一阶谓词系统中所有可证公 式。现在人们一般接受，任何直觉上可计算的数和函数，都可以被图灵机计算。 而无法用图灵机计算的，本质上也是不可计算的。因此，图灵机的计算能力与直 觉上人作为计算者的能力本质上相同。这是对人类智慧及其局限的深刻洞察。 　　在1936年，我们有了三种关于可计算性的定义：图灵的通用图灵机，哥德尔 的递归函数，和丘奇的兰姆达函数。图灵证明了图灵机与兰姆达函数的等价。后 来，丘奇的学生科雷尼(Stephen Kleene, 1909-1994)证明了递归函数与兰姆达 函数的等价。于是这三个表面上似乎不相关的定义被统一起来，揭示了可计算性 的本质。 　　正如一部关于可计算性理论的著名专著中所评价的，“图灵关于通用图灵机 存在的定理是上个世纪的智力里程碑之一”。 　　通用图灵机可以说是现代“存储程序通用计算机”的雏形。图灵的思维是革 命性的。他的构造中已经有了“软件”的思想：标准表达就是一个计算程序。程 序和数据被同样“输入”和“存储”，计算机是通用的，其工作由程序控制。这 些几乎１０年后才由被后人称为“计算机之父”的冯?诺依曼总结提炼而成为现 代计算机体系结构核心的思想，至少部分归功于图灵。冯?诺依曼对从图灵那里 所获得的启发从不讳言。１９３６到１９３８年，图灵在美国普林斯顿大学师从 丘奇攻读博士学位，冯?诺依曼当时正在那里任教，两人过从甚密。图灵获得学 位后，冯?诺依曼曾表示希望雇用图灵在普林斯顿工作。图灵谢绝了，回到英国， 不久即进入皇家密码学校，即战时的英国密码破译中心，开始了帮助英国和盟军 击败德国的密码破译工作。 　　现代通用计算机（也就是现在遍布于世的大小电脑）的计算能力本质上不超 过通用图灵机。也就是说，图灵在现代计算机诞生10年以前就不但证明了它可以 做什么，而且也证明了它不能做什么！ 　　图灵机的意义早已超越了对证明“判定问题”的应用。由于图灵机深刻体现 了人类机械思维的本质，它成为一个通用工具。许多数学家和数理逻辑学家使用 它（通常是改造后的变体）来证明一些复杂的数学定理。图灵机至今仍是研究算 法复杂性和可计算性的重要手段，亦是研究形式语言与自动机的基本工具。图灵 机也被用于研究人脑，神经网络和思维的机制。甚至有人以图灵机作为研究宇宙 的模型。 　　当图灵和丘奇的否定性结果发表时，希尔伯特刚刚退休。他的哥廷根大学数 学系作为世界数学中心的地位，由于德国疯狂的反犹浪潮，也已经岌岌可危。大 批优秀的犹太血统数学家不得不背井离乡，远走高飞。据说，一次宴会上，希尔 伯特碰巧坐在德国教育部长身旁，部长关心地问道，现在哥廷根的数学研究情况 如何？希尔伯特不无悲伤地说，“数学？哥廷根现在哪还有什么数学！”。希尔 伯特在其生命的最后１２年从未对哥德尔和图灵的证明公开发表评论。他死后， 墓碑上刻着“我们必须知道，我们能够知道！”。 　　知道我们能做什么固然很好，知道我们不能做什么也很重要。比如，有了热 力学第二定律，我们就知道任何形式的“永动机”是不可能的。有人向你兜售永 动机，你就知道他必然是骗子。有了“判定过程”的不存在性，我们也就不会再 费神劳力企图发明一种万能验证程序，可以查出任意程序的“虫子”，或者判定 任意程序的最终结果。等等。 　　图灵发明了抽象的图灵机，制造过破译密码的电动解码机，也设计过当时体 系结构领先的真正的可编程序带存储器的电子计算机ACE。他的设计思想和编程 理念被应用到了曼彻斯特大学“马克Ｉ”计算机上，并深刻影响了后世。他的 “机器指令集”类似于３０年后才开始流行的“简约指令体系结构”（RISC）思 想。这是图灵思想远超时代的另一证明。 　　图灵一生都在思考人的心智如何“运算”，能否用机器模拟的问题。１９５ ０年，他在另一篇影响深远的论文《计算机器与智能》中提出了“机器能否思考” 的问题，并给出了机器智能的判定标准，即后来被称为“图灵测试”。他提出， 如果一个测试人对处于黑室中的一台机器和一个人提出问题，经过一段充分时间 “较量”，他不能从答案中分出哪个是人，哪个是机器，就可以认为机器拥有了 智能。这篇文章被认为是人工智能的开山之作。 　　图灵曾乐观地预言，到２０世纪末，机器智能将能够达到以７０％的成功率 通过图灵测试。或者由于图灵英年早逝，后继乏人，或者由于我们对智能的本质 还远未了解，我们现在离这个标准还差的太远。现在世界上每年都举行机器智能 大赛，但参赛者都心知肚明，不敢妄称试图通过图灵测试，而只是期望击败自己 的机器人对手。近两年的大赛获胜者是一个叫做Ａｌｉｃｅ的机器，“她”现在 有一个网站 　　 http://alicebot.blogspot.com/ 　　谁愿意都可以和她聊天。偶尔她也会说出很“聪明”的话。不过很容易判断， 她的“智能”十分有限。 　　图灵为我们留下了永久的遗产。他的智慧结晶，图灵机，现在仍然是人们探 索人类自身能力和局限的有力工具。图灵孤独而默默地离开了我们，留下了许多 奥秘和疑团。就像人类面临的其他许多奥秘一样，我们有可能最终找到其中一些 的答案。还有很多，我们甚至将永远无法知道，它们是不是有答案。 ◇◇新语丝(www.xys.org)(xys4.dxiong.com)(www.xysforum.org)(xys2.dropin.org)◇◇