互动科普

被遗忘的阿兰·图灵计算机科学思想

B. Jack Copeland，Diane Proudfoot

这位以图灵机、图灵检验和图灵命题等概念而著称于世的英国科学天才也曾预见到神经网络计算机和“超级计算”。

阿兰·马塞松·图灵在1935年构想出了现代计算机，今天所有数字计算机实质上全是“图灵机”。这位英国数学家也开创了人工智能(AI)这一领域，提出了引起广泛争论的著名图灵检验来作为判定一台经过适当编程的计算机能否思维的一种方法。在第二次世界大战期间，图灵对于破译德国Enigma代码起了决定性的作用，该工作是英国一项绝密行动计划的一部分，历史学家称这一行动计划把欧洲的战争缩短了两年。图灵去世时年仅41岁，当时他正在对今天可能会被称为人造生命的问题进行最早期的研究，模拟生物生长发育的化学过程。

在其不平凡的整个研究生涯中，图灵从未对宣传他的设想有过很大兴趣。因此，多年来他的研究工作的若干重要方面一直被人们忽视甚或遗忘。特别是没有几个人——哪怕是精通计算机科学的人——熟悉图灵对“联网化”(connectionism，即类神经元计算)所作的令人极感兴趣的预见。同样，他在“超级计算”(hypercomputation)这一激动人心的领域中的一些开创性理论见解也被忽视了。某些专家认为，超级计算机有朝一日可能解决迄今被认为无法对付的问题。

图灵连接

数字计算机是处理数字的高手，如果要它们预测一枚火箭的轨道或者计算一家大型跨国公司的财务资料，它们可在几秒钟内就得出答案。但是，要想把人们常做的一些看来非常简单的事情，例如识别一张面孔或者辨读手写的字，编成计算机程序却是非常棘手的事情。或许构成大脑的神经元网络天然就具有标准计算机所缺乏的执行这类任务的能力，因此，科学家们一直在研究更精确地模拟人脑的计算机。

联网化是一门用人工神经元网络进行计算的新兴科学。目前研究人员一般是在通常的数字计算机上模拟神经元及其互连(正如工程师们在计算机上创造虚拟的机翼和高楼模型一样)。在计算机上运行的一个训练算法调节神经元之间的连接，使该网络逐步生成一台具有某种特定功能(例如预测国际货币市场)的专用机器。

当代的联网学者认为Frank Rosenblatt是这一方法的开创人，他在1957年发表了关于此问题的许多论文中的第一篇。然而，几乎没有人意识到，图灵早在1948年就在一篇鲜为人知的论文(题为“智能机器”)中研究过联网网络。

这篇论文的手稿是图灵在伦敦国家物理实验室工作期间写成的，它没有获得图灵的老板的首肯这家实验室的主任是其举止有点像私立学校校长的Charles Darwin爵士(英国著名博物学家达尔文之孙)，他对该论文不屑一顾，称其为“小学生的习作”。但是，实际上这篇有远见的论文是人工智能领域的第一份宣言。在谈论文中——它直到图灵逝世后年的1968年才发表——图灵不仅提出了联网化的基本原则，而且还以非凡的才能描述了后来成为人工智能的核心的许多概念（有些是在被其它学者重新发现后成为人工智能核心的）。

在该论文中，图灵发明了一类他称之为“B型无组织机”(B-Type unorganized machine)的神经网络，该网络由人工神经元以及对人工神经元之间的连接进行调整的装置构成B型机可有任意多个以任意方式连接起来的神经元，但有一条限制始终存在，那就是每一个神经元之间的连接都必须经过一个起调节作用的装置。

所有的连接调节器都有两条训练纤维对其中一条纤维施加一个脉冲，可将该调节器置于“通过状态”，在此状态下输入——可以是0或1——将通过调节器而不发生变化，并成调节器的输出对另一根纤维施加一个脉冲就把调节器于“中断状态”，在此状态下无论输入是什么，输出都恒为1。

图灵对联网化的预见

在一篇直到他逝世后14年才发表的论文中，阿兰·图灵介绍了一种随机方式连接起来的人工神经元网络。这种名为“B型无组织机”网络中的每一个连接都经过一个节器，此调节器可以设定在两种状态之一，一种状态允许数据通过而不发生变化(绿色纤维)，另一种状态则破坏被传送的信息(红色纤维)把节器从一种状态转换到另一种状态，就使网络能够得到训练。注意，每个神经元都有两个输入，并执行简单的“与非”逻辑运算(NAND)：如果两个输入均为1，则输出为0，否则输出就为1。

在图灵的网络中，神经元自由地相互连接。而现代的网络则使信息的流动限于从一层神经元流向另一层神经元。联网专家们的目标是模拟大脑中的神经元网络。这一状态使调节器把所有企图通过该调节器所在的连接的信息全都破坏掉。

一旦状态被设定之后，某个调节器就将保持它的功能(通过“或者“中断”)，除非它收到另一根训练纤维上的脉冲，有了这些独出心裁的连接调节器，人们就可通过图灵所谓的“适当的干预、模仿教育”来训练一台B型无组织机。实际上，图灵总结说，“幼儿的大脑皮层就是一台无组织机，它可通过适当的干预训练组织起来。”

每一个图灵模型神经元都有两根输入纤维，而一个神经元的输出是其两个输入的简单的逻辑函数。网络中的每一个神经元都执行相同的逻辑运算，即“与非”(NAND)：如果两个输入中有任一个为零，则输出为1，如果两个输入均为1，则输出为零。

图灵之所以选择NAND这种逻辑运算，是因为其它每一种逻辑运算(或布尔运算)都可通过一组NAND神经元来完成。此外他还证明了即使是连接调节器本身也可用NAND神经元来作出。因而图灵规定一个网络仅由NAND神经元及它们的连接纤维构成——这差不多可算得上是最简单的大脑皮层模型了。

1958年，Rosenblatt用一句简明扼要的话奠定了联网化的理论基础：信息的存储通过建立新的连接——即神经系统中的传输通道——而实现(或者通过创造与新的连接具有等价功能的条件而实现)：“由于破坏现有的连接与建立新的连接在功能上可以是等价的，因此，为了建立一个能够完成某一特定任务的网络，研究人员可取一个具有过剩连接的网络，然后有选择地破坏其中部分连按在图灵B型机的训练中，这两种操作(即破坏与建立)都用上了。

开始时B型机中已经有一些随机的神经元间连接，它们的调节器被任意地设定于通过状态或中断状态。在训练期间，对于不需要的连接，可以把它们的调节器转换到中断状态，这样就把它们破坏掉了。反之，把一个调节器从中断状态改变为通过状态，实际上就是建立了一个连接。这种有选择地断开和建立连接的做法就把开始时处于随机状态的网络训练成一个为完成某一给定工作而组织起来的网络。

图灵希望研究其它类型的无组织机，而且他希望一台普通的数字计算机来模拟一个神经元网络和它的训练方法。图灵说，他希望“让整个系统运行相当一段时间，然后自己以‘学监’的身份去看看它的学习取得了什么样的进展。”但是他自己关于神经元网络的研究工作是在第一台通用电子计算机问世不久进行的。(直到1954年，即图灵逝世那一年，Belmont G. Farley利Wesley A. Clark才在麻省理工学院对一个小的神经元网络进行了首次计算机模拟)。

不过，用纸和笔进行的计算就足以让图灵证明，一个足够大的B型神经元网络，在经过适当配置后(通过它的连接调节器)可以成为一台通用计算机。这一发现揭示了与人类认知有关的最根本的问题之一。

从“自上而下”的观点来看，认知包括了复杂的中行处理过程，常常涉及到语言或其它形式的符号表示(正如在数学计算中那样)。但是从自下而上的观点来看，认知只不过是神经元的简单激发而已。认知科学家们面临的问题是如何协调这些完全不同的观点。

图灵的发现提供了一条可能的出路：大脑皮层由于是一个起着通用计算机功能的神经元网络，因此它能够执行在自上而下地进行观察时所辨识出的串行且面向符号的处理过程。在1948年这一假说远远地超前于它的时代，直到如今它仍然是关于认知科学中最困难问题之一的最杰出的猜想之一。

计算不能计算的东西

1935年，图灵构想出了一个抽象装置，此后该装置得到了“通用图灵机”这一名称。图灵机由一个无限的存储器和一个扫描装置构成。存储器用于存储数据和程序，而扫描器则穿过存储器来回移动，一次一个符号地读出存储器上的信息并写入其它符号。图灵机的每项基本操作都是非常简单的，例如“识别扫描的符号”，“写入(1)”以及“向左移动1个位置”等等。但是，把大量的这些基本操作组合在一起，就可以实现复杂问题的操作。尽管看起来非常简单，但通用图灵机却能够执行功能最强大的现代计算机所能执行的任何一项任务，事实上，所有的现代数字计算机究其实质都是通用图灵机。(参看本刊198t年9月号John E. Hoprroft所著“图灵机”一文。)

图灵在1935年的目的是设计一种尽可能简单的机器，它能够进行按照某种算术方法作计算的数学家能够进行的任何一种计算，拟定他有无限的时间、精力、纸笔并且完全聚精会神地工作的话。把一台机器称为“通用”机只是表明它能够进行所有这类计算。正如图灵自己所写的那样：“电子计算机的作用是执行任何一种明确的经验过程，这些过程也可以由人类操作者通过一种严格的但非智能的方式来执行。”

尽管有这样功能强大的计算装置但仍然存在一个令人感兴趣的问题：能否设计出可以完成更多任务的机器呢？这个问题的答案是，此种“超级机器”可以在理论上进行描述，但至今没有人知道它是否能建造出来。超级计算这一研究领域现在正在吸引着越来越多的科学家。某些人猜测，人的大脑本身——已知的最复杂的信息处理器——实际上就是一种天然生成的超级计算机的实例。

在新近出现研究超级计算的热潮之前，人们把那些难度非常大，因而通用图灵机无法处理的信息处理任务一概称之为“不可计算”的。从这个意义上说，超级计算机就是计算那些不可计算的东西。

甚至在最简单的数学分支中也能够找到这类困难任务的例子。例如，给定一些随机选出的算术陈述，通用图灵机可能并非总是能够判定哪些是定理(如“7+5=12”)，哪些不是定理(如“每个数都是两个偶数之和”)。另一类可计算的问题来自几何学一组铺砖——即大小不等，且各边颜色也不相的若干正方形——如果能够覆盖整个欧几里德平面，既不留一下空隙，铺砖相互间也不重迭，而且相邻的各边颜色总是相同，那么我们就说这组铺砖能够“铺砌平面”。夏威夷大学的逻辑学家William Hanf和Dale Myers发现了这样一组铺砖，它们只能以非常复杂的方式铺砌平面，以致用通图灵机并不总是能预测某一给定程序是将终止还是将永远继续运行下去。有时候这一事实用另外一种说法表述：任何通用程序设计语言(Pascal、BASIC、Prolog、C等等)都不可能有一种可靠的停机查错程序，即一种能检测出所有可能导致停机的故障的工具(包括那些可能产生出无限的处理循环的错误)。

图灵本人第一个研究了超级计算机的设想，这类机器能够完成那些难度太大以致通用图灵机无法执行的任务。1938年，图灵在普林斯顿大学撰写的博士论文介绍了”一种新的机器”，即“O型机”。

O型机是用一个黑盒子(或“神盒”)对通用图灵机进行扩充所得的结果，而神盒就是执行不可计算任务的机器。在其它方面，O型机与普通的计算机井无什么差别：一个数字编码的程序输入O型机，该机通过一步一步地反复运用计算机的基本操作而从输入中得出数字输出（一项基本操作就是把数据传送给神盒并记下它的响应)。

对于神盒是如何运行的，图灵没有作任何说明，(他在较早期的研究中，对于通用图灵机的基本操作——例如“辨认扫描器中的符号”——是如何进行的也没有作任何解释。)但是不难想象出对O型机里盒子的具体情况作规定的一般概念上的原则。原则上，甚至一个适当的B型网络也能执行不可计算的任务，只要神经元的活动去同步的话。(当一个中央时钟使各神经元的活动彼此保持同步时，神经元网络的运作就可以用通用图灵机精确地模拟。)

根据超级计算这一新奇的数学理论，诸如区别算术中的定理与非定理这样一类任务不再是不可计算的了。从理论上说，甚至连查错程序——它可以判定比如说用C语言编写的任何一个程序是否会进入无限循环——都是可能实现的。

如果能够建造出超级计算机——这是一个很大的“如果”——那么解决迄今为止被为是无法对付的逻辑和数学问题的潜力是非常巨大的。事实上，计算机科学可能正在接近自从研究人员几十年前通过电子方式实现了一台通用图灵机以来它所取得的最重大进展之一。然而另一方面，研制超级计算机的工作也可能因为找不到实现神盒的方法而告吹。

寻找适当的物理、化学或生物现象的工作现在正在进行，或许答案在于某些复杂的分子或其它结构。它们互相连接成一些有如Hanf和Myers所发现的那样复杂结构。也可能正如麻省理工学院的John Doyle提出的那样，存在着一些天然发生的具有分立的平衡系统，它们被视为原则上在执行不可计算的任务，在接受了输入之后产生出适当输出(例如1或0)。

在数理逻辑这一领域的范围以外，图灵的O型机基本上已被遗忘了，取而代之的却是一个神话。根据这一不足凭信的说法，图灵在三十年代中期已经证明了超级机器是不可能实现的。人们认为他和逻辑学家Alonzo Church(图灵在普林斯顿大学的博士导师)已经阐明了这样一条原理：通过图灵机可以精确模拟其它任何一种信息处理机器的行为。但这种说法其实是错误的。上述命题被广泛称为Church-图灵命题(这也是不正确的)，它意味着任何一种机器都不能执行通用图灵机所无法胜任的信息处理任务。事实上，Church和图灵只是说，通用图灵机的功能同任何按照算法规则用纸和笔进行计算的数学家的行为是等价的——这是一个保守得多的陈述，它肯定没有排除超级机器的可能性。

即使对那些正在努力遍求建造超级计算机这一目标的人来说，图灵的开创性理论贡献也被忽视了。专家们常常谈到关于“超越图灵极限”的信息处理工作，并常常说他们自己是在努力“突破图灵障碍”。《新科学家》杂志最近发表的一篇关于这一新兴领域的评论声称，新的机器“超出了图灵的观念”，是“图灵从来没有想到过的一类计算机”，仿佛是这位英国的天才学者在半个多世纪以前没有设想过这些装置一样。遗憾的是，关于图灵在联网化方面的思想，已经出现过的情况现在似乎又开始四处重新出现。

图灵的最后几年

五十年代初，在他的生命的最后几年中，图灵开创了人工生命这一领域。他试图模拟使受精卵的基因得以确定该受精卵将要长成的动物或植物的解剖结构的化学机制。他说这一研究同他对神经元网络的研究“并非完全不相干”，因为“大脑结构必然是通过遗传胚胎机制来实现，而我现在正在研究的这个理论可能会更清楚地揭示这实际上将意味着什么样的限制。”在这段时间中，图灵因第一个进行计算机辅助线性动态系统研究而声名卓著，他的理论使用非线性微分方程来表示生长的化学过程。

但是，在这一开创性研究正在进行的中途，图灵不幸死于氰化物中毒，有可能是他自己所致。1954年6月8日，就在他即将过42岁生日之前不久，人们发现图灵死于他自己的卧室。他留下了许多手写的笔记和一些计算机程序。数十年后，这些引人入胜的资料仍未被充分认识。

【刘光明/译；冉隆华/校】