六角形蜂房的优点：在所有二维图形中，给予一定的周长后，圆形含有最大的面积。但是它不适合于蜜蜂的巢室，因为在各个圆形之间，将有许多空隙浪费掉。六角形的另一种优点则来自它们的共用邻边。6个外围的六角形可以产生一个“免费”的内六角形，因为内六角形的每边都是共用的，然而 6个外围圆形却不能产生一个“免费”的内圆形，因为这些圆形没有共用的圆周，所以内圆形必须另行绘出。由6个外围六角形的共用邻边所形成的“节约”，则更为微妙。6个外围六角形仅由5个六角形的周边长度构成。7个圆形是的的确确的7个圆形，而5个六角形实际上可以形成7个六角形。三种规则面砖的贴砖如果放宽要求，那么可以在贴砖中使用一种以上的正多边形面砖，但所有的顶点都应该一致（即在顺序方面，贴在任何一个顶点周围的正多边形面砖都要与任何其他顶点一样），因而还可能有另外的8种贴砖方式。无论你是喜欢用数学的分析方法，或是喜欢从经验上的判断，既可以通过纸上谈兵式的分析，也可以通过对浴室地板花样的综合调查，你会相信，不可能还有其他的贴砖方式。到现在为止，我们所论述的贴砖方式全都是规律性的，它们都像壁纸那样，是重复的。每一种贴砖方式都含有一块“籽砖”，即贴砖中的最小单元，从总体上看，贴砖都是它的多次复制。如果你有一块籽砖的橡皮图章，那么你可以重复地使用它，只要上下或左右地移动，不需要转动它，就能做出整个贴面。在只由一种正多边形面砖（正三角形、正方形和正六角形）组成的3种贴砖方式中，籽砖显然是正多边形本身；蜂巢式的贴砖是由一个正六角形产生的。方形的贴砖是由一个正方形产生的，而三角形的贴砖则是由一个等边三角形产生的。荷兰艺术家 M.C.埃歇尔就是以他的规律性贴砖方式而著名，他的贴砖通常都不是正多边形，而是这类或那类的动物。贴砖的要求至于非规律性的贴砖方式，则不复杂。画出一张方形贴砖图。设想把每块方形面砖沿其对角线分为两个直角三角形。可以由你决定沿哪条对角线把每块方形面砖分开，但是所有方形面砖的分开方法则应使其直角三角形的整体贴砖方式形成非规律性的。这种非规律性的贴砖方式不能再简单了：它只由一种面砖——直角三角形面砖组成，而且，即使它不具有籽砖，从某种意义上讲，也仍然可以断定，三角形组成方形。使用一种以上正多边形面砖的贴砖方法无须费力，就能把这种非规律性贴砖方式中的直角三角形重新排列成为周期性贴砖。要做到这一点，一种简单的方法，就是在每两块面砖组成的方形贴砖中，把对角线从左上角到右下角的那些方形移动90度。这样就可使所有的对角线方向一致，而籽砖就成了组成任何方形贴砖的两块直角三角形面砖了。非规律性贴砖方法非规律性的贴砖方式也可以由任何数量的不同种类面砖贴成。这种数量上的不受限制，使得非规律性贴砖方式可供那些在几何图形上喜欢附庸风雅，希望浴室地板花样独特的人选用。要用两种面砖贴成非规律性贴砖，我们还得从方形面砖开始，然而，我们不是把它们沿对角线分开，而是在每块方形面砖的西北角或东南角刻出一条三角形刻痕。像前面一例的，我们选择的是没有图案的两角，而所有的刻痕则是同样尺寸的。其结果是非规律性贴砖方式都由直角三角形与不规则的五角形组成。而且，这些面砖也可重新排列成为规律性式样，比方说，把每一块东南角有三角形刻痕的面砖取出，并把它们转动180度。规律性贴砖方法两种面砖的非规律性贴砖方法面砖的规律性贴砖方法早在60年代初期，数学家们就认为，在至少以两种不同形状面砖为基础的任何非规律性贴砖方式中，必定存在一种用相同形状的面砖（或这两种不同形状面砖的子集）排列而成的规律性贴砖方式，然而他们还不能对此加以证明。1964年，哈佛大学的一名研究生岁伯特。伯杰论证了这种看法是错误的。10年以后，正当雷施研究复活节彩蛋时，牛津大学的理论物理学家、富有充分想象力的罗杰。彭罗斯提出了两种新面砖，它们称为风筝和飞镖，达到需要的目的。如图中所示，风筝和飞镖必须角与角连接在一起，但有些边则不能与其他面砖的边相接触。在面砖上做出凸起和凹口来限制它们，以免排列成不需要的形式。风筝和飞镖风筝和飞镖上的突起和凹口令人惊奇的是，风筝与飞镖能够以无限多的方式在平面上贴砖，其中没有一种是规律性的，但其图案可具有高度的对称性，它们本身总是没有重复就终止了。最值得注意的是，在这些贴砖方式中，任何一种贴砖方式中的有限范围往往是无穷尽地出现在该种特殊贴砖方式中的其他地方，也往往是无穷尽地以每隔一个贴砖的形式出现。马丁。加德纳在《科学美国人》的封面故事人物一文（1977年1月）——彭罗斯面砖爱好者必读——中写道：“要知道这种情况是多么的奇妙，设想一下你生活在一个无限的平面上，它由彭罗斯的无穷无尽的贴砖方式中的一种来镶嵌成花纹状。你可以在不断扩大的面积内，一块一块地检验你所贴好的图案。不管你检查了多少块，总是不能确定你究竟是在哪一块贴砖上。不管你走得多远，或分区划片地检验也无济于事，因为所有这些范围都属于一个大的有限范围，里面所有拼图也都是准确地多次重复。当然，这对任何规律性的棋盘结构来说都是正确的，也是无关紧要的。然而彭罗斯的世界却不是规律性的，在无穷无尽的各种方式中，它们彼此各不相同，而且也只有在不能达到的界限处，才能把一个与另一个区别开来。”彭罗斯的贴砖方法如果这还不足以使你兴奋的话，接着加德纳又解释了另一个值得注意的特性，该特性由剑桥大学的数学家约翰。霍顿。康韦发现。假设你生活在某一城镇中，它是一个任意大小的圆形区域，该城镇是彭罗斯世界中的某处。你必须走多远才能发现一个完全相同的城镇？康韦证明了，远于你所在城镇的直径两倍处，你都不必去尝试！而且，如果你突然要迁往彭罗斯世界的无穷无尽的任何其他处，那么你也总是要迁往远离这座城至多直径两倍之处，那里就有与原住地相匹配的地方，而且很可能就在至多直径一倍之处。彭罗斯的宇宙论的含义也是令人大吃一惊。只要用两种简单的基本组合，或者说原子，就能创造出数量无限的世界。所有的原子世界在任何可想象的有限范围内都显示出惊人的规律性，然而在宇宙范围内则显出独特的不规则性。尽管雷施的设计工程近于幻想——一大群复活节女郎都搬不动如此巨大的复活节彩蛋，但是他所关心的事则很实际。他知道，在贴砖模式方面的大量数学与建筑学文献，仅仅适用于平面，而不适用于蛋形的曲面，面对前景莫测的挑战，他绘制了一幅卵形图，图上画有纬度线。换句话说，他想象复活节彩蛋是由许多条形构成的，一条带叠在另一条带上，在每条带上分别贴砖。然而，对这种自然概念的计算机模拟表明，即使每条带都很细，而且面砖的数量又很多，人们的目光仍然会放在各条带上，而忽视整体的形状。雷施放弃了带状结构，转向另一种最简单的图形结构，等边三角形结构。经过了6个月的思考和模拟之后，雷施认为，用2，208块同样大小的等边三角形面砖和524块三点星形面砖（等边但不是规则的六角形）就可贴成复活节彩蛋，三点星形面砖的宽度略有不同，它根据贴在彩蛋上的位置而定。面砖连接的角度都有变化，彩蛋中部隆起处小于1度，到末端处仅为7度。由于角度这么小，即使由平的面砖组成，彩蛋也呈平滑弯曲状，三角形面砖是用经过阳极化处理的铝片制成的，重量2，000磅，厚度为八分之一英寸；星形面砖的厚度则为其一半。用于固定的内部结构重3，000磅。彩蛋的长度 25.7英尺，宽度18.3英寸。雷施说道：“从未用这么大量的同样面砖贴成像彩蛋这样的三维表面。例如，航天飞机上的隔热砖都是形状各异的。如果航天飞机的设计师已经了解我的有关工作，或者我知道他们的问题，那么航天飞机就可以像贴彩蛋那样贴上隔热砖。这样，他们还可以携带备用的隔热砖进入太空。”可实际上由于航天飞机上的每块隔热砖都不同，所以它也无法携带备用隔热砖。航天飞机在高速通过大气层时，隔热砖往往会脱落，这时要贴上一块新砖就必须进行加工。雷施还说道：“当韦格勒维尔镇雇用我时，协议是由我设计复活节彩蛋，由他们负责建造和油漆。然而，我很清楚，若不约请一家航天公司加工彩蛋面砖，韦格勒维尔镇将无法建造彩蛋。他们肯定担负不了这项工作。所以我告诉他们，还是由我来建造并油漆它。”面砖的油漆，要在它们组装起来之前进行，此事牵扯到一些让步。该镇希望复活节彩蛋要用色彩鲜艳的红、蓝、绿、橘黄颜色粉饰，而且期望油漆的鲜亮色彩能够保持100年。雷施告诉他们，彩蛋使用这几种颜色油漆，每隔3－5年就要重新油漆一次。最终选用了3种颜色——金色、银色和青铜色，这几种颜色可以保持其光泽半个世纪。在雷施开始建造彩蛋之前（要把这些面砖在内部连接在一起，而且不能看见其连接头，为此用了6， 978只螺母和螺栓以及 177根连接到中心轴上的支杆），镇的管理条例要求有一位土木工程师或建筑师证明该设计在结构上肯定安全可靠。必须注意到，韦格勒维尔镇经常遭受每小时 100英里风速的飓风袭击，当地的工程师或建筑师没有一位愿意证实，如此巨大的新奇形状在结构上具有完整性。“人们害怕，大风可能把它刮跑，”雷施回忆说，“我也承认有些担心。在建造彩蛋时，我成为指责的目标并受到了指责。”那时候，该工程已获得了势头，而且镇上也完全放弃了需要证明的规定，韦格勒维尔镇的许多居民都在打赌，所赌的不是彩蛋是否可能倒塌，而是如何倒塌（翻倒还是刮跑）以及何对倒塌（建造时还是建造后）。雷施带领一队志愿人员组装复活节彩蛋，历时6星期。他们曾经历过一次侥幸脱险。当彩蛋的上端部分组装完毕并安装在中心轴的顶端上时，它看来很像一把巨伞。这时空中狂风暴雨肆虐，龙卷风席卷而下。雷施及其伙伴花费整夜时间，把这个伞形结构转向顺风，使它不会被风刮走。这座复活节彩蛋不仅要顶住自然力量，而且还要面对人们的愤怒。建造彩蛋劳累了一天以后，雷施会累得躺倒在当地一家旅馆中，他听到人们窃窃私语，计划要炸掉彩蛋。他也曾几次接到警告：中学的孩子们声称要炸毁彩蛋。雷施终于弄明白了，在他到达韦格勒维尔镇之前的一段时间内，报纸曾经传播谎言，说镇里把用于建造中学游泳池的经费挪去建造复活节彩蛋。“我只好四处游说，”雷施说道，“竭力向每个人解释彩蛋款项的实际来源，而且学校会有自己的游泳池的。没有人再想要炸掉彩蛋了，可是彩蛋确实遭受过几次来福枪射击。”在复活节彩蛋完工后很长一段时间里，雷施使用计算机分析其结构的牢固性，并得出结论，它比所需的强10倍。雷施说道：“就是全体居民被大风吹倒，复活节彩蛋也不会。”自从雷施离开韦格勒维尔镇，10年过去了。当然，该镇依然存在，而这座独具匠心的纪念碑使韦格勒维尔镇出现在地图上（还被收载入女王伊丽莎白的加拿大旅游指南中）。该镇惟一的委屈是这个复活节彩蛋尚未被收入《吉尼斯世界纪录大全》之中。看来这是不公平的，加拿大艾伯塔省的另一个城镇卡尔加里镇就曾因用20，117个鸡蛋烹调出世界上最大的煎蛋饼而载入《吉尼斯世界纪录大全》。第六章 麦比乌斯分子数学家们吐露，麦比乌斯带只有单面，如果你要将它分成两半，你将会感到十分可笑，因为分开后还是一条带。——无名氏数学不仅可以在最宏大的规模上帮助进行形状设计，如3层半楼层高的复活节彩蛋，而且还可以在微小的范围内帮助设计。本章将叙述美国博尔德市科罗拉多大学的戴维。沃尔巴及其同事们如何在奇特的麦比乌斯带中合成分子的故事。神秘的麦比乌斯带是数学家们的宠物。你可以用一条窄纸条制作麦比乌斯带，例如取一条加法器用纸带，半扭转，再把纸带两端连接，形成一闭合环，就成为麦比乌斯带。麦比乌斯带只有单边，也只有单面。如果你用一把漆刷沿着纸带方向刷漆，那么你将发现，当漆刷回到起点时，它已漆满整个纸带的表面。如果你沿着纸带的一面做一种魔术记号，那么你也会立即相信，纸带只有一个边。如果你沿着纸带方向把麦比乌斯带剪成两半，果然，就像五打行油诗所说的，它仍然还是一条带子。1858年，法国巴黎的一家科学协会为数学方面的一篇最优秀论文颁了奖。在这次竞赛提交的论文中，德国莱比锡市的数学家奥古斯特。费迪南德。麦比乌斯“发现了”这种曲面，就是现在以他的名字命名的曲面。麦比乌斯仅用纯数学观点论述了他的发现，例如，没有讨论自然界中存在着麦比乌斯带分子的可能性。的确麦比乌斯不会想到诸如麦比乌斯带分子存在的可能性，这是因为当时的有机化学科学还处于萌芽阶段，人们即使对最简单的分子形状也一无所知，更不用说对数学有意义的复杂分子了。在麦比乌斯发现的同时，德国波恩大学的奥古斯特。凯库勒宣布他的发现：碳原子可以连接形成长链，它将成为有机化学的基础。4年前，凯库勒在伦敦的公共马车上，首次在幻想中思考了碳链的问题。他回忆说：“那是一个晴朗的夏夜，我乘坐末班公共马车回家，和往常一样坐在‘车顶的’座位上，通过大城市中没有行人的街道，在平时，那是个充满活力的城市。我陷入幻想，并且好像看见许多原子在我眼前欢跳……我常常看到两个较小的原子如何联合形成偶原子，1个较大的原子如何环抱着两个较小的原子；还有更大的原子如何抓住3个甚至4个较小的原子不放，同时，它们整体如何跳着眼晕的舞蹈快速旋转着。我也看到较大的原子如何形成链子……无论如何，我也要花些夜里的时间，把这些幻想中形成的形态轮廓写进论文中。”11年以后，1865年，凯库勒认识到碳链子可以环绕着旋转，形成环。而梦幻又一次给他以灵感。“我坐着编写教科书，然而工作毫无进展，我的思维开了小差。我把椅子转向取暖壁炉，并打起盹来。原子再次在我眼前欢跳。这时较小的原子谨慎地呆在基底上。我的心灵眼睛通过这种重复景象而更加敏锐，现在可以辨别出多种形体中较大的结构，长长地排列成行，有时还更紧密地拼接在一起；整行迂回曲折像蛇一样运动。瞧！那是什么？有一条蛇咬住了它自己的尾巴，嘲弄般地在我眼前快速旋转，仿佛一道闪电，把我惊醒了……当天晚上，我就推断出假设的结论。”首先，凯库勒推导出苯的结构，它由6个碳原子和6个氢原子组成。凯库勒断定，6个碳原子形成六角形，各带有一个氢原子与每个碳原子相连。自从凯库勒辨明苯的形状以来，120年内有机化学家们当然发现了更为复杂的分子的形状，诸如双螺旋的脱氧核糖核酸分子。但只是在近些年，化学家们才观察到形状呈麦比乌斯带的分子。麦比乌斯分子不是在自然界中发现的，而是由戴维。沃尔巴及其同事们在实验室里合成的。开始时，他用形状像一架3级梯子的分子合成。（梯子的每级实际上是一个碳-碳的双键，这里可以忽略掉。）然后使梯子环绕着弯曲，再把两端连接，使其实际上形成一个环状物。环形物中一半仅仅是一条环形带，而在另一半，当它两端连接时，将半截扭转，从而形成一条麦比乌斯带。麦比乌斯带分子与麦比乌斯纸带一样，都具有许多神秘的性能。如果3个碳双健全部断开，那么分子仍然还是单个分子。碳双键的断开，相当于沿着纸带的中线环绕着把麦比乌斯带分成两半。对于分子和纸带两者来说，结果都是单带，只是其周长为原来的两倍。化学家们很早就已知道，两种化合物可以有同样的分子式（即由同样化学成分严格地按同样比例组成的化合物），但却以性质不同的化学实体存在。如果同样的化学成分以不同的方式或以不同的角度相互键合时，这种现象就可能发生。然而，两种具有同样分子式的化合物，甚至具有同样的化学键，其在化学性质上也可能不同。怎么会有这种可能呢？一门叫做拓扑学的数学分支学科可以解释这种现象。它是研究物体在不断发生变形时其性质仍然保持不变的数学学科。设想某物体是由柔性橡胶制成。拓扑学家想要知道，当物体受到推拉但不戳破或撕裂时，什么性质仍然保持不变。可用麦比乌斯带这个实例形象地说明这种抽象概念。假设你有一条橡胶的麦比乌斯带，你可以用一切可能的方法使它伸缩。不管你用多少种方法也都不能使它变形，最后得到的形状总是只有单面。因此，只有单面的性质就是拓扑学家们所关心的事。当一种形状能够连续变形成为另一种形状时，从拓扑学上看，两种形状被认为是等价的，所以，不管把麦比乌斯带伸缩成什么形状，从拓扑学的定义来说，它们也都是等价的。现在考虑两条麦比乌斯带，一条用橡胶带朝某一方向扭转而成，另一条也用橡胶带但朝相反方向扭转制成。从拓扑学上看，这两条麦比乌斯带是否等价？它们不等价。两者都不可能变形成为另一种形状。如果你从镜子里看这两条带子中的一条，那么你会看到，其映像很像另一条带；两条带互成镜像。这里我必须停下来发表一项否认声明，以避免数学家们来信恶意攻击。数学家们都是一群怪人，拓扑学家们都不把自己局限在三维空间之中。而在四维空间中，他们却能证明，镜子里的麦比乌斯带可以互相转变。然而我仍将坚持把我们的讨论限于三维之内，因为我们探究的主要对象分子的形状总是在三维中观察到的。因此，我要重申，在三维中，镜像的麦比乌斯带从拓扑学来看是截然不同的。成分一样而且化学键相同的两种化学化合物为什么会有性质截然不同的实体，关键在于从拓扑学上看，可能存在着截然不同的镜像。因为右手和左手都是众所周知的镜像，所以人们习惯地把与其镜像相反的物体称为左手的或右手的。在一对镜像物中，究竟哪一个叫做像，是一个习惯问题。这正如街道的右侧不存在绝对位置一样，它取决于你行走的方向。两种麦比乌斯带已被人们称为右旋和左旋的麦比乌斯带，但是不必担心何者右旋，何者左旋。分子也存在右旋和左旋形式，人们称它们为手性，它是从希腊词“手（Cheir）”借用来的。右旋和左旋麦比乌斯带都是镜像形状的实例，从拓扑学来看，它们在性质上是截然不同的，但有着等价的镜像形状。现以一简单图形为例，一个圆形是它本身的镜像，显然，从拓扑学上看，圆形与它本身是等价的。另一个例子是字母R及其镜像Я。若用软橡胶制成图形R，那么可以用拓扑学的变形方法把它变换成为它的镜像。可是，分子不是软橡胶制成的，物理的约束力防止它们以任何方式发生变形。尽管如此，R形分子还是能够转变成为它的镜像，无须弯曲变形——的确根本不需要弯曲。这次，如果把用硬塑料制成的字母图形R及其镜像Я放在桌子上，那么，只要把它拿起来翻转，就能使其中一个变成另一个。这种变换由于物体始终保持其刚性，所以叫做刚性变换。许多有机分子都是刚性的手性分子：它与它的镜像在刚性上是截然不同的。人体明显偏爱某种手征的手性分子。例如，大多数的蛋白质都是由左旋氨基酸和右旋糖组成的。当手性分子在人体内合成时，只能产生具有所需手征的手性分子。但是，当诸如药物等手性分子在实验室内用非生物方法合成时，结果都是右旋与左旋形式分子的对半混合。当病人服药时，由于难于除掉不是所需形式的分子，所以服用的是混合物。一般说来，非所需形式的分子在生物学上是惰性的，而且只是经过身体，无任何作用。有时还是有害的。60年代初期，就曾发生给妊娠妇女服用擦里多米德药物事件。药物中的右旋分子具有所需的镇静药性，而左旋分子却能造成新生儿畸形。英国伦敦皇家学院化学教授斯蒂芬。梅森在英国周刊《新科学家》发表的文章中，注意到收入标准药物手册中的486种合成生产的手性药物，只有88种是由所需的手征分子组成的。其余的398种全都是对半的混合物。梅森得出了结论：“它们都是在特定环境（人体）中使用，某种手征会得到特别的偏爱。可是，效果又会怎样呢？”当一位有机化学家分析一种新分子时，首先要做的事是试图确定分子是否刚性的手性分子，即在刚性上与其镜像是否截然不同。这里可借助于拓扑学。从拓扑学上看，如果分子与其镜像性质不同，那么它们在刚性上也是不同的，因为刚性变换只能是许多通过拓扑学完成的变换中的一种。还以上面讨论过的R及其镜像Я作为例子。在从一个变形成为另一个时，可以得到一种中间的形状Я，它具有对称性，其左半是其右半的镜像。拓扑学家们知道，如果一种形状能够变形成为某种具有反射对称性的形状，那么该形状本身就能够变形成为其镜像。这就意味着，如果化学家能够让分子获得具有反射对称性的形状，那么，他就能消除分子的手性。这种见解往往证明是有用的。沃尔巴已经从三级梯形分子中合成出分子的麦比乌斯带，他请我去直接观察从两级梯形分子中合成的类似方法。所得到的形状是手性吗？如下图所示，由于它能变换成为具有反射对称性的形状，所以不是手性的。可惜，这种解释对于三级麦比乌斯分子似乎不起作用。经过许多思考实验之后，沃尔巴推测，好像它不可能变形成为具有反射对称性的形状。如果变形后已经显示出反射对称性，那么他就会断定，三级麦比乌斯形状可以变形成为它的镜像。可是，这样的逆叙正确吗？任何变形未能显示出反射对称性，是否意味着分子本身就不能变形成为其镜像？毛病就出在答案太容易上。沃尔巴请我考虑两只橡胶手套，一只为右手的，另一只则是左手的。手套显然都是镜像的，可是从拓扑学来看，它们等价吗？当然，手套在刚性上是不等价的，因为如果我们像翻转字母R那样翻转两只手套中的一只来获得镜像，那是行不通的。然而，如果我们把任何一只手套从里往外翻转，那么就能使手套成为等价。（拓扑学家因而发现它自己处在一个奇特的位置上，既不能认为手套是右手的，也不能认为是左手的。）在把手套从里往外翻转的过程中，手套在任何步骤都不具有反射对称性。我们也许能够得出结论，手套是一个反例：某种形状在拓扑学上与其镜像等价，但在其变形过程中却不具备反射对称性。这种结论可能是错误的。只是我们没有让手套充分变形。如果我们使劲拽开手套，那么至少在理论上能够把手套变形成为一个圆盘的形状，这时手套就具有反射对称性（沿任何直径方向都有反射对称性）。以上讨论的要点是，沃尔巴在化学方面的一些研究已向拓扑学家提出一个重要问题：如果某种形状在变形过程中不可能具备反射对称性，那么是否可以得出结论，从拓扑学上看，形状本身与其镜像不等价呢？这是一个基本问题，但在数学文献上，好像还没有人提出来过。这个问题整个都牵扯到一个重要的哲学问题：物理科学上的新概念是否常常会启迪出数学上的新概念？或者反之？换句话说，何者在先，是物理科学，还是数学？许多哲学家遇到过这个问题，这与众所周知的关于鸡和蛋何者在先的问题一样，答案看来是不会令人满意的。在这两种情况下，人们所得出的结论，似乎不是一个不可置否的证据，而是一个目的性的试验。一些步柏拉图后尘的专横数学家断言，他们的学科是与物理学实际相脱离的。他们认为，即使没有可供计数的物体，数字也会存在。不大固执的数学家们则承认，科学与数学是紧密相连的，但他们坚持数学在先。他们提出群论作为证据，群论是数学的一门分支学科，在19世纪30年代诞生，它完全没有物理学上的用途，只是最近才被粒子物理学家应用，以便用于研究过去20年内发现的亚原子粒子集。但是，物理学家们则相信他们的学科在先，而且认为历史是站在他们一边。例如伊萨克。牛顿创造了数学中著名的分支学科微积分，就是因为他当时需要一种数学工具，用来分析极小的空间与时间间隔。而我认为，数学与科学都相得益彰，才是惟一公正的结论，尽管这种判断既不鼓舞人心，也不增进知识。麦比乌斯带的故事就是数学与物理科学之间错综复杂相互促进关系的一个很好的实例。1858年的论文竞赛中提出的麦比乌斯带仅仅创立了纯数学，现在它在化学中发展起来，而且已被化学家们熟练地运用，又为纯理论的数学家提出许多问题。你可以感到欣慰的是，麦比乌斯带不仅可以服务于化学家，而且也可以服务于工业家。B.F.古德里奇公司已经获得麦比乌斯输送带的专利权。在普通输送带中，带的一侧会有较多的磨损与撕裂。而在麦比乌斯输送带中，应力可分布到“两侧”，从而可以延长其使用期一倍。第七章 遗漏了的带一把手的三孔空心球形问题在40年代和50年代期间，许多在数学上思维敏捷的人曾经热情地工作，研制出第一部电子计算机。当然，他们成功了，而且在过去30年内，数学家们在电子方面的脑力成果已使许多科学领域发生了巨大的变革，然而，可笑的是，数学本身却没有进展。美国斯坦福大学的数学家约瑟夫。凯勒说道：“看看我们这个系，我们拥有的计算机比学校其他系，包括法国文学系在内，都要少。”“这是很可笑的事，”罗伯特。奥泽曼这样说，他是凯勒的同事，已在斯坦福大学工作了30年。“我们缺乏计算机显然是有几种原因，一是由于一些数学家的保守性——他们不愿意花时间去真正学习如何有效使用计算机——另外，他们认为使用计算机要花很多时间，这正是他们自己不愿努力思考的托词。”然而这些日子，由于前斯坦福大学学生、现在美国阿默斯特市马萨诸塞州立大学工作的戴维。霍夫曼有了一项引人注意的新发现，使凯勒和霍夫曼对计算机在数学中应用的未来更有信心了，借助于改革了的计算机绘图系统，霍夫曼及其同行、美国赖斯大学几何学家威廉。米克斯第三发现了无穷无尽的优美曲面，这些曲面遵循某些严格的标准。而目前已知的只有3种曲面符合这些标准。这些奇异的曲面已使麦比乌斯带似乎显得世俗而又平凡。无疑，他们填补了数学上的一项空白，而且还证明了这些曲面像麦比乌斯带一样可以用于数学之外的一些学科，诸如胚胎学与牙科学等多种学科。计算机对基础数学做出的最著名的贡献是一项“10岁”的成果，它打乱了老规律。1976年，美国伊利诺斯大学肯尼思。阿佩尔和沃尔夫冈。哈肯证明了著名的四色地图定理，该定理阐明了用这种方法至多只需4种颜色，就能把许多想象到的国家绘制在一张彩色平面地图内，而其中的任何两个邻国颜色不同。当时，我还是美国哈佛大学的一名大学生，当该证明的消息传到坎布里奇市时，我的微分方程老师中断了讲课，打开香槟酒瓶，热烈庆贺。124年来，四色地图定理（以简单的辞藻形容，就是多么的诱人）曾经搞乱了著名数学家与献身数学的业余爱好者的步伐，他们都曾徒劳地探索这项证明（或许可以预料地得到了反证）。我和穿着漂亮服装的同学都跟随着我们的老师，高举酒杯，为阿佩尔与哈肯已经攀登上数学的珠穆朗玛峰而干杯。几天以后，我们知道了阿佩尔与哈肯使用的未曾有过的高速计算机取得的这项证明：1，200小时的工作量仅用3小时就记录完。这项证明若用手工检验，简直是太长了。（好奇的读者可消磨10年的时间去研究《伊利诺斯数学杂志》第二十一卷中460多页的检验表。）我还能回忆起当时我们的心绪是多么的烦恼。这项证明不符合那时保罗。厄尔多斯所赞同的数学观点，他是一位到处走动的古稀老人，世界上最多产的数学家之一。厄尔多斯认为，上帝有一本很薄的小册子，书中含有所有重要数学定理的简明的第一流的证明。毫无疑问，四色地图定理包含在该书内，而阿佩尔与哈肯的证明肯定不在其列。我们的老师和我们都感到沮丧，有些人担心计算机会出差错，因而造成微妙的误差。另一些人承认计算机有助于定理的证明，但还希望众所周知的聪明的中学生有朝一日会不用计算机就能做出简明漂亮的证明，一项像厄尔多斯心目中上帝所赋予的证明。还有一些人则想知道，那冗长乏味的证明是否就是论题的最后定论；不过，他们都曾猜想过，四色地图定理是整个令人感兴趣的定理中的代表，简单的证明不会存在，也不可能存在。今天，10多年过去了，对阿佩尔与哈肯的工作还是没有定论，当然也没有宣告计算机证明的时代的到来。计算机固然已经发现了新素数，而且解出了阿基米德的关于牛的问题，但这不是证明一个定理。事实上，自从四色地图定理以来，还没有一个著名的定理要由机器来证明，霍夫曼和米克斯曾用另一方式使用计算机，它可能是未来的出路。他们曾利用计算机的数字捣弄能力获得洞察力，使他们无须计算机的帮助就能不断取得进展，并证明了一项基本结果。150年来，许多数学家都曾研究肥皂膜的形状，而且霍夫曼和米克斯发现的许多曲面都是与这些形状有关的。如果把一铁丝圆环浸没在肥皂液中，然后取出，那么横跨在铁环上的肥皂膜形状是平圆盘状的。这种形状被认为是极小的曲面，因为在可能横跨铁环的所有曲面中，平圆盘形具有最小的面积。如果再用两个相距很短的铁丝圆环，一个放在另一个上方，再浸入肥皂液后取出，那么跨过两个铁环的肥皂膜形状叫做悬索曲面，它类似核电厂冷却塔的形状。这种形状也是一种极小曲面；因为连接两个铁环的所有曲面中，没有其他曲面具有更小的面积。自然界总是偏爱极小曲面，是因为它们在物理上稳定：最小的面积意味着贮存的能量最小。可以把极小曲面的概念从肥皂膜的厨房物理学世界扩展到无限的超自然领域，我们把这个工作留给数学家们去做。无限小的曲面的说法似乎像是矛盾的，因为任何曲面要在一个方向或多个方向无限向外扩展，必须有一个无界的面积。如果一位数学家说一个无限的曲面是极小的，也就是说用制作肥皂膜的方法把该曲面充分缩小到有限范围内的最小面积，换句话说，如果你在该无限曲面上任何处做一魔术标记，并画一条非常小的闭合曲线，那么，在该曲线作为边界的前提下，曲线内的曲面将有最小的可能面积。平面就是无限小曲面的最简单例子；平圆盘状肥皂膜正是一个平面。如果悬索曲面的两端永远扩展，结果也成为另一个无限极小曲面。平面和无限扩展的悬索曲面都是本身不会相交的曲面。它们也都不会自身形成双重曲面，也不会无限接近。诸如平面和无界的悬索曲面等曲面都可变形，成为一个简单的有限物体：一个具有一些微孔和一些空心把手的空心球形。（不妨在皮箱上画出一个空心把手，它就可以使皮箱中的空气流过空心把手，再回到皮箱。从数学角度来说，每种空心把手都可以用来增加曲面的“连通度”，因为剪断空心把手将不会把曲面分成几块。）数学家们以他们丰富的想象力认为曲面都是由超柔性的橡胶制成。如果用拉长、压缩、扭转或其他手段，但不包括撕开、穿孔或填孔等方法使这些曲面之一变形成为另一种曲面，那么这两种曲面被认为具有同样的拓扑学结构。例如空心球形就可以拉伸成为卵形曲面，因此这两种曲面具有同样的拓扑结构。从拓扑学角度来看，平面与穿有单一微孔的球形相同，因为在这种奇特世界里，微孔可以无限地扯开，形成平面，这将使查尔斯。古德伊尔感到悲哀。悬索曲面与带有两个微孔的空心球形具有同样的拓扑结构；每个微孔都能拓宽并拉伸到无限大。（总的说来，多孔空心球形的每一个微孔都可以扩展成为无限大。）当霍夫曼和米克斯开始研究时，数学家们都知道，除了平面和无界的悬索曲面外，仅有另外一种无限极小曲面，它本身不会相交，在有孔的空心球形（带或不带把手）上，能用橡胶片的变形来模拟。这种曲面就是无界的螺旋面，它类似于扩展成无限大的螺旋。和平面一样，螺旋面与单孔空心球形具有同样的拓扑结构。人们知晓的这3种极小曲面几乎存在200年了，而且过去10年的一系列成果也都说明，似乎不太可能有第四种存在。例如，1981年，美国圣地亚哥市加利福尼亚大学的里克。舍恩就曾证明，带有两孔的空心球形仅能作为悬索曲面的模型，而不能作为无自身相交的其他无限小曲面的模型。同一年，巴西数学家卢奎西奥。豪尔赫则证明了，带有3孔、4孔或5孔和不带把手的空心球形都不能成为适宜的模型。霍夫曼说道：“由于在所有特殊情况下都已排除了新极小曲面的存在的可能性，许多人认为，而且试图证明没有新的例子能够存在。他们未能获得成功，但是大家却有一种共同的感觉，认为他们未能成功不是因为他们在无效地试图证明实际上是错误的东西，而是由于他们没有足够先进的数学工具。”1983年11月，霍夫曼获悉，一位名叫塞尔索。科斯塔的巴西研究生，在其博士论文中讨论了提及的曲面的疑难方程问题。科斯塔已能证明无限的、极小的曲面在拓扑学上可与带一把手的3孔空心球形相同。但是，科斯塔和其他任何人都不知道提及的曲面看起来像是什么，因为定义曲面的方程似乎都是相当复杂。况且，也没有人知道曲面是否本身相交。如果该曲面要加入平面、无界悬索曲面和无界螺旋面的极小曲面的神圣行列，那么它是不容许本身相交的。自身相交的问题不是一个简单的问题。霍夫曼解释说：“当你有一组曲面方程时，你不能计算出某些量，说‘是，它自身相交’或‘不，它自身不相交’。而从本质上说，你只能证明曲面的某一块不能与另一块相交。”然而，对于一个无限曲面，这是远远不够的，因为你还必须与无数块曲面相比较。霍夫曼计划使用计算机去计算曲面核心部分的坐标，然后绘制出曲面核心图。但是，常规的计算机制图学软件爱莫能助，因为它们所包括的主要是工程师们使用的立方形、球形和其他现有的形状，而不包括自身相交或扩展成无限大等奥秘的数学曲面。碰巧，他又获悉，美国马萨诸塞大学研究生詹姆斯。霍夫曼开发了一种计算机图形学的新软件。戴维。霍夫曼说道：“我们的对策计划是使用计算机观察面。如果我们看到了它们自身相交，那么我们打算发表一篇有关这个实例的简短论文，排除该曲面可能是无限小曲面的看法。也许我们必须在一本低等的杂志上发表，因为在数学杂志上很难发表这类问题的否定结果。要是我们看不到它们自身相交，那么我们也不知道我们要做什么，只能说证明曲面本身不相交的工作实在太难了。”然而，计算机生成的图形使他们的预料落空。它不仅显示出自身不相交，而且还显示出具有高度的对称性。它含有两条成直角相交的直线。霍夫曼在从不同角度“观看”曲面核心并经过长期艰苦的思考后，终于认识到曲面可以分解成为相同的8块。在物理学中，眼见为实；而在数学中，就不够了。霍夫曼和米克斯看到了对称图形之后，把图形搁置一边，仅根据方程就证明了曲面本身不相交。出乎他们意料，竟然发现了第四种无限小曲面，这种曲面由两个悬索曲面和一个平面构成，整体像从“瑞士硬干酪心”中发出来似的。3个月后，他们证实了存在着无限多的这种曲面，每一个曲面在拓扑学上都与带几个把手的3孔空心球形等价。在霍夫曼和米克斯发表第一个新曲面核心的图片之后，英国剑桥大学的一位生物学家就和他们联系，他认为，发育中的胚胎可能呈现这种形状。最小面积曲面往往会自然地存在于有机与无机材料之间的界面中，因为这样的曲面可使表面张力降到最低程度。美国纽约市的一位牙外科医师打电话给霍夫曼，并且说明该图形看来正好像他们用于移植在假牙上固定假牙的骨质物，霍夫曼说，他认为“极小曲面的破坏性较小，因为它与骨质物的接触面较小。而且，还有许多‘把手’为骨质物履行使命”。即使极小曲面在现实世界中未得到应用，而霍夫曼与米克斯的发现仍然是不朽的。不过它却暴露出有关无限小曲面的最新知识是多么的贫乏，而且它也证实了可以在纯数学研究中利用计算机。但对于将近200年来搞不清楚的问题，很难对其在计算机帮助下所取得的惊人进展提出异议。第三篇 计算机在发现巨大素数、解阿基米德牛群问题、破译密码、证明四色地图定理以及发现新图形等问题上，计算机证明对数学家是有用的。然而在计算机能做些什么问题上，却还有难以捉摸的限制。自20世纪30年代起，数学就面临着一场革命，如同物理学的两次革命——广义相对论与量子力学——一样重要，这两次革命动摇了物理学的基础，并且推翻了关于空间、时间与因果律的经典理论。数学的前景展望也由于美国纽约大学的莫里斯。克林提出了“必然的损失”的说法而完全改观。一种崭新的工作已不再注重于数学计算的能力，而是注重于计算的限制。有意义的计算问题被规定为原理上不能解的，或在原理上能解而实际上无法解的问题。一个从原理上不能解的有意义的典型问题就是“停机问题”，它是艾伦。马西森。图灵于1936年提出的。图灵想到了计算机程序是否迟早会提供结果和停机的问题。停机问题已不仅是纸上谈兵的理论家所关心的问题，而且是很容易在实践中出现的问题。美国麻省理工学院计算机科学理论学家迈克尔。锡普塞说道：“你可以想象，当你把程序编入卡片，然后提交给计算机中心时，尤其是在这几天里，你是多么想知道答案。他们总是整夜地进行运算，第二天就送回给你。比方说，你有一笔100美元的钱存在机内。有时，计算机程序会有一个无限的循环，而且会耗掉许多钱。由于它会陷入无限的循环，因此你从程序上得不到任何东西。不论是你帐上的钱都已耗费完，还是计算机以何种方式注意到机器运行了很长时间，计算机自己停了机。“那么，你一定会想，为什么事先不检验程序，如果其中有无限循环，就不应该用它运算”。然而令人惊奇的是，这种自然的概念不能够实现，因为图灵证明了，没有一种检验方法能够适用于所有程序。除了图灵所证明的停机问题是不可解的之外，1936年数学家向绝对数学知识的虚幻目标发动了另一次进攻。逻辑学家阿朗索。丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的。至于你所给的每一种可能想到的算术语句，计算机也是不能确定其真值的。的确如此，要求找出算术的真值是没有诀窍的。近几年来，数学界的注意力已从理论上不能解的问题转向理论上能够解而实际上不能解的问题上。在这些问题中，最著名的就是美国国际商业机器公司（IBM）的拉里。斯托克迈耶称之为“内在困难”的问题，即委婉法问题，如果这也算是一个问题的话。他请你构想一部想象中的最大功率的计算机。这部想象的计算机，可以大到充满整个宇宙（直径也许为1，000亿光年）。它将由质子大小（直径为10-13厘米）的硬件构成，信号将以光速（每秒3×1010厘米）在硬件中疾驰通过。它可以就某个问题工作200亿年，它超过了宇宙的估计年龄。这个难题具有一个令人不知所措的特点，即它在原则上能够解决，但即使用可想象出的最大功率的计算机，按宇宙年龄再工作上千百万年也无法解决。这类问题之一是下棋问题，它在棋盘不是普通的8×8，而是n×n（这里n表示任意大的数目），而且还有不限数量的棋子（但每方只能有一个王棋）。我们想有一种计算机程序，不论棋下到哪一步，不管我们是哪一方，比如说白子，它都可以用来确定是否能够赢。某种程序只在理论上可行而在实际中行不通，它需要考虑所有白方可能走的棋步，随后考虑所有黑方可能回应的棋步，还要考虑所有白方可能反回应的棋步，以此类推，考虑所有可能继续的棋步，直到结束时为止。这种穷举搜索程序的缺点是速度太慢：有那么多可能继续的棋步，甚至理想的计算机也不可能在200亿年的时间内把所有棋步都考虑进去。1981年，美国耶鲁大学的戴维。利希滕斯坦和以色列的数学家艾维兹里。弗伦克尔证明了对于足够大的棋盘也没有更快的程序。换句话说，耗时的穷举搜索程序没有简捷的方法。这种下棋问题，即使我们知道已有解法，也总是会使计算机的分析落空。下面4章，我们将从理论和实践两个方面考虑计算机的能力与局限性。第八章 图灵的通用计算机艾伦。马西森。图灵是一位非凡的数学家、计算机科学的先驱者、破译纳粹的著名密码谜的关键人物。 1952年 2月，他以“粗野的下流言行，触犯了1885年刑事法修正条例第八条”的罪行，在英国曼彻斯特市被捕。在此之前不久，图灵的家被盗，盗窃犯是他的朋友阿诺德。默里，一位19岁的无业青年，图灵与他曾有过性关系。当图灵向警察报告盗窃案时，曾把他与默里的关系告诉了警察，他天真地认为，皇家委员会即将使同性恋合法化。两个月后，他因6次进行性骚扰受到审讯，并因总共 6次的性骚扰被判有罪，将送往监狱。他接受定期服用两性化女性激素药物的方案，进行“有机疗法治疗”，因此给他一年缓刑。1954年6月7日，41岁的图灵吃了半个浸在氰化物溶液中的苹果自杀。①在人工智能领域，图灵取得了基本概念方面的两项不朽成就：图灵检验法和图灵计算机。图灵检验法是他确定计算机能否思考的方法。检验要求把计算机和任意选出的人与提问者分开，提问者要通过中间物向他们提出数量不限的问题。图灵认为，如果提问者未能区别两者之间是计算机还是人，那么就意味着计算机正在思考。换句话说，如果计算机被认为是有智能的，那么它就是智能型计算机。要对图灵通用计算机的概念进行解释，需要一些基础概念。当图灵在英国剑桥大学时，1935年他就是在那里成为英国皇家学院的一名研究员，他受到了物理学革命性发展的影响，该发展推翻了因果律和决定论的传统概念。按照牛顿的世界观，如果在自然体系方面掌握了足够的知识，那么整个未来都将是可以预测的。1795年，法国数学家、同时又是牛顿迷的皮埃尔-西蒙。拉普拉斯是这样论述智能的：“假如某一时刻有一种智能，这种智能可以包含所有的力量，并由此使自然界生气勃勃，而且使组成自然界的各种生命都有各自的位置——智能的强大足以使许许多多数据服从于分析——它可以使最大物体的运动与最轻原子的运动都包含在同一公式之内；对于智能来说，没有不能断定的事物，而且未来也和过去一样，都将出现在其眼前。”然而，本世纪初，量子力学的提出，使未来完全根据现在和过去来决定的说法宣告结束。在30年代，由于量子力学，特别是由于观察者总是影响着观察结果的原理，使哲学界发生了大混乱，而英国剑桥大学正处在这种混乱的中心。图灵发现这种概念是不稳固的，而且他也被引向数学，因为看来它所涉及的是绝对的实体，与观察者无关。正如剑桥大学数论学家G.H.哈迪所说的，317是一个素数，不是因为我们想它是个素数，或者说我们的想法是以某种方式而不是另一种方式形成的，而是因为它就是一个素数，因为数学的实体性就是那样建立的。图灵致力于解答某个疑难问题的工作，该问题切中了数学实体性的本质核心：是否有一机械方式确定数学中任何已知语句是正确的还是错误的？为了回答这个问题，他终于提出了“通用计算机”，即图灵计算机的概念，这种概念可以例行地回答数学的问题。图灵引入了能够运算数学的计算机概念，目的在于强化数学作为与人类事物无关的学科的地位。然而可笑的是，图灵发现，数学的某些问题是不能由计算机或人用机械的方法来解题的，例如，涉及非重复小数的数产生问题。图灵计算机是一个非凡的概念。不过从其一系列性能的观点来看，它却是非常有限的。即使你对计算机的程序设计一无所知（或许整个主题会使你吃惊），但图灵计算机的如此有限性能，也会使你很快地理解它的“内部”工作情况，从而高兴地为它编写程序。然而，从计算的观点看，它是能够进行任何运算的，换句话说，数学家能够进行的任何运算，想象的最大功率计算机也能够进行运算。如果说，这种说法不是相当惊人的话，那么让我再隐晦地补充一句：图灵计算机，不管它叫什么名字，不一定是一部计算机。它可以是一个人或一组人。那么，这种图灵计算机的基本原件是什么？首先，它有一条长带，设想它是一条窄窄的纸带，纸带上划有许多竖线，把它分成许多方形单元。如果已知某单元不是空白的，那么它就含有有限字母符号中的某一种符号。图灵计算机，能够一次扫描纸带的一个单元，通常都是从含有符号的最左边单元开始。如果所扫描的单元是空白的，那么计算机就会让单元的空白留下，或者在单元中打印一个符号。如果所扫描的单元含有符号，那么计算机就可以让单元的符号留下不变，擦掉该符号并在该符号的位置上打印另一个符号，或者擦掉该符号并让单元留下空白。然后计算机停机，或者立即扫描到左边或右边的单元。计算机对所扫描的单元要做些什么，下一个要扫描的是两个相邻单元的哪一个，这取决于计算机的状态或内部构形，状态数与符号数一样，必须是有限的。计算机的状态像一种思维状态，即计算机在“思维”些什么。要了解图灵计算机的运算，用不着对其状态的本质进行精确的、形而上的思考（或更抽象定义）。计算机的“程序表”规定了计算机对于符号与状态的每一种可能组合将要做出的反应。举两数相加一例，将会非常清楚地阐明这些抽象概念。假定我们以“一元”的记号写出一些数字，其中整数 n用一串 n个*号来表示，在n个相连的单元内每单元一个*号。据此，**号表示2，*****表示5.一元记号的优点是只有一种符号*号，不需要10个不同的数字来表示任何已知的正整数。若要2加5，只要把**号和*****号打印在纸带上，它们之间有一个空白单元，这样两串*号就可以区别开。带有图解的程序表说明了计算机如何进行两数相加的运算。但在讨论程序表的特点之前，先要概括地描述加法的过程。聪明的计算机先找到两个数之间的空白单元，在空白单元打印一个* 号（那么在纸带上留有一串的8个* 号），而后继续下去，找到一串* 号的结束单元，并擦除掉最后一个* 号。这样，在纸带上就留有*******号，按一元记号，它就是7，即2加5的和。现在让我们再来看程序表。计算机的状态通常列在最左边的一栏内。在这个程序表内，共有3个状态，编号分别为0、1和2.符号（和表示空白单元的词“空白”）通常横列在程序表的上方。在这个表内只有一个符号*号。计算机在0状态中开始，按照惯例，扫描纸带上最左边的符号（换句话说，扫描**号中的第一个*号）。程序表描述了计算机如何运算状态0与符号*号的组合。计算机让符号留下不变，扫描到右边的下一个单元，并停留在状态0中，那么，计算机如何运算这个单元？由于计算机仍然处在状态0中，而且单元中的符号还是一个*号，计算机仍按前面所述进行运算：只让符号*号留下，扫描到右边的下一个单元，并停留在状态0中。现在换到空白单元。程序表中状态0与空白符号的组合说明了计算机是如何进行运算的。它打印了一个*号，再扫描到右边的下一个单元，即进入状态1.这时，这个单元中还是一个*号，而状态1和符号*号的组合就描述出计算机的行为：扫描到右边的下一个单元，并停留在状态1中。这个步骤要重复4次，因为每次都是一个*号继续出现。当计算机扫描到一串5个*号结束处的空白单元时，它会回到左边的一个单元，并进入状态2.这个单元中有一个*号，计算机会擦掉它。然后计算机停机，处于一种完成状态。这种方法的作用是：相同的程序表都可以生成任何两数的和，无论数的大小如何，只要以一元的记号写出，两数间有一个空白单元，就能算出。在状态0，计算机只是扫描第一个数的每个单元，一直扫描到空白单元，再在其上打印一个*号。在状态1，它则是扫描第二个数的每个单元，直到空白单元，再回扫，并停留在最后一个*号的单元上。在状态2，它只是擦掉这个*号。于是，纸带上就立即有了答案。这种加法是众所周知的有限数法，因为程序表包括数量有限的状态和数量有限的符号。然而这种有限数法却可以生成范围无限的数。图灵计算机要运算可以想象的任何数之和，纸带的长度就必须是无限的，也就是说，如果纸带仅有1，000个单元长，而它就不能运算大于1，000的数。在图灵计算机用这种方法完成两数相加的运算时，纸带将只有答案，而没有原来的两个数。如果有人试图编写一个带有原来两数的程序表，那么他一开始就应该想到，图灵计算机需要“计算”在两串*号中的8个*号。然而令人感到意外，图灵计算机不能进行这种计算。设想它扫描第一个*号时，就会跳入状态1.每当它扫描另一个*号时，就会跳入下一个状态。这样下去，在它扫描第五个*号后，计算机就已处在状态5中，扫描第二十三个*号之后，就处在状态23中。看来用这种方法，图灵计算机似乎能够计算任何*号的数；即当它扫描完所有*号时，它的状态数就相应于它的*号数。但是，这种方法是行不通的。你知道这是为什么吗？问题就在于这个方法不是有限数法。这种方法需要数目无限的状态。比方说，如果计算机仅有5个状态，那么它就不能计算多于5个的*号，因此它将被限制在和为5或小于5的数之内。如果它有50，000个状态，它也不能计算多于50，000个的*号。换句话说，对于有限数状态n，它不能计算多于n的*号。这种方法行不通，是因为我们所要寻找的是在任何情况下都可用于任何加法的方法。如果允许数字状态是无限的（或者符号数是无限的），那么程序表就编写不出来。而要求编写出有限数字的程序表，按照惯例，需要用机械的方式。现在需要探讨一个令人感兴趣的说法，即图灵计算机不必是一部机器，而是程序表（如果你愿意的话，可以叫它软件），那就是图灵计算机的定义。任何一个实体，它可以是一部计算机、一个人、一条美人鱼、一个游魂、或是克里姆林宫，只要它能够按照程序表进行运算，就是一部图灵计算机。如果你能够按照加法图表中的程序表在纸带上进行两数的加法运算，那么你就是一部图灵计算机。在一篇卓越的论文中，图灵在理论上和实践中已经能够证明；图灵计算机无法做到的，数学家和计算机都无法做到。一部超级计算机能够非常迅速地解出的问题，动作迟缓的图灵计算机也同样能够做出解答。掌握图灵计算机的实质和具备有限数法的解题能力，最佳的方法是自己编写程序表。我想提出一个建议，请你编写一种程序表，使它可以用于图灵计算机的一元记号的减法运算。但要提醒你，在编写程序表时，应让计算机以某种方式知道它已完成计算，并把该方式写入程序表中。否则，由于纸带的长度可以任意长，常常可能使计算机一直连续扫描许多空白单元。下图显示出了减法用的程序表。当然，其他程序表也可以进行运算。第二个问题是为计算机编写一种程序表，可用于检验编写在纸带上的符号P和Q顺序是否是回文式的，即正读与反读的顺序都一样。一种方法就是使计算机能够对第一个符号与最后一个符号进行比较，第二个符号与倒数第二个符号进行比较，以此类推。但要记住，这种方法必须是有限数字。如果顺序是回文式的，可以让计算机打印一个Y，如果不是，则打印一个N.这种方法是安德鲁。霍奇斯在为英国《新科学家》周刊撰写的一篇文章中采用的。这种方法如图所示。霍奇斯方法的缺点是，尽管程序表只有6个状态，但计算机要浪费许多时间沿一串符号来回移位。如果计算机在拿第一个符号与最后一个符号进行比较之后，拿倒数第二个符号与第二个符号进行比较（而不是拿第二个符号与倒数第二个符号进行比较），然后拿第三个符号与倒数第三个符号进行比较，再拿倒数第四个符号与第四个符号进行比较，以此类推，那么它就可以节省时间。这种方法的程序表如下图所示，它需要 10个状态。要缩短计算时间，必须以较长的程序作为代价。最后一个建议是为图灵计算机编写一种程序表，可供计算机用于检验由空白单元分开的两串P和Q符号是否变移位置式的。而且，Y符号同样代表“是”，N符号代表“否”。这里需要提示一下，在计算机解题时，计算机会打印出一个假符号字母R.有一种可能的答案似乎是正确的。_______① 关于图灵最后几年的悲剧性详情，在安德鲁。霍金斯著的同情性传记文学曾做报道，《艾伦。图灵：谜》（西蒙-舒斯特出版社，纽约， 1983）。第九章 威利。洛曼无辜地死去了吗？从某种基本意义上讲，计算机和数学家只是不容易识别的图灵计算机，知道这一点也许令人泄气。但在另一方面，从表面上看过于简单的图灵计算机，由于证明能够解各种各样的计算问题，从而又可被认为是鼓舞人心的。数学家与计算机之间理论上的相似性不仅适用于他们能解出的各种问题，而且也适用于他们不能解出的各种问题。工业上每天都出现许多计算问题，若用任何已知的方法去解，则太费时间，现在都例行地由计算机去着手解决。然而工业需要的是对这些问题的解法，而计算机常常牵扯到程序设计人员的水平，他们往往不能编出最佳程序。其中有许多是众所周知的使旅行推销员感到为难的问题；已知一个城市与公路网络，要找一条推销员在往返旅程中到每个城市去一次的最短路线。仅有一种已知的算法用来解这种旅行推销员问题，就是可靠的逐步试探法，这种方法费力，缺乏预见性，只是对每一种可能性都进行尝试。看来，数学并未减轻威利。洛曼的烦恼。过去15年内，数学家们都感到迷惘，他们寻求巧妙的、较快的算法都告失败，这是由于他们无知呢，还是这种问题本身存在内在的困难？按照当前的知识水平，暂时还没有较快的算法，甚至在理论上也没有。目前还没有人能够证明这一点。对证明的研究已是理论计算机科学中最为热门的课题，而且在这个领域中工作的数学家已被公认为是复合型理论学家。当数学家们谈到保证解题方法时，他们的意思就是指算法。不要由于“算法”（algorithm）这个英语单词的发音令人生畏而摈弃它，它是9世纪波斯数学家阿布。贾法尔。穆罕默德。伊本穆萨。阿尔霍瓦里米的姓氏音译转讹而来的，他的语义遗产还包含有单词代数（algebra）在内。算法的音难读但不难懂。你早已了解什么是算法的直观概念。你可曾记得，在你读小学时，你的英语老师让你制定出一整套令人厌烦的规定，去做诸如系鞋带一类枯燥无味的琐事，然后老师叫约翰尼。怀斯盖严格按照你的规定去系他的鞋带（与此同时，这个讨厌的老师还会让你大声念你的那一套规定）。当然，他会立即出错——而且是个大错——因为你没有考虑一些看来好像是理所当然不成问题的基本步骤，就像系鞋带时理所当然要握住鞋带的塑料包头，而不是握住它的中部一样。如果你详详细细地写出，那么你就会得到一个有关系鞋带的规则系统，而这个规则系统不过是一个循序渐进的程序，在这个程序中，每一步都说得很明确，你可以按部就班地解决每个问题。每个步骤都要规定得清清楚楚，其间不允许留下任何靠可能、直觉、经验、解释或想象等方法来处理的细节。当然，数学家们对于计算问题的算法要比系鞋带更感兴趣。两个整数相加的算法，根据小学老师教给我们的方法，是用纸和铅笔按照如下的明确步骤进行：把整数写成一行，一个数写在另一个数的上方，两数右端对齐，在它们下方划一横线，从右到左地进行计算，有时还“进位”1，而且照此步骤计算许多其他数的相加，也是不成问题的。这种算法应该包括如下法则，像“如果一个数2在另一个数4的上方，可在其下写一个数6”和“如果一个数3在另一个数6的上方，可在其下写一个数9”等法则。算法的功能之一是其能用于一个问题的所有实例。例如加法算法可以算出任何两个整数的和。你虽然花费时间去详尽写出一种算法的全部细节，但你却得到了一种能够保证工作的方法。计算机的程序或是单一的算法或是系列的算法。如果没有指令告诉该算法的每一步骤应该做些什么，那么计算机就同不能模拟系好鞋带一样，也不能进行两数相加的计算。程序设计员的作用在于编好完整的指令，换句话说，要编好完整的算法。当程序设计员责怪其程序中的错误时，他的意思是指在编写详尽算法或把算法译成计算机语言时，他犯了一个错误。必须强调的是，算法的用户不管是一部机器还是一个人，不需要对算法做出判断。例如，加法算法的使用，不需要“什么是数字”这一概念。要应用算法时，你可以盲目地按照法则进行。比方说，你不必知道，5是跟在4之后，7是大于3等等，甚至你也不必知道你是在使用十进制的数制。哲学文献中已有许多篇幅谈论过，就计算机的思考能力而言，缺乏判断会意味着什么。但是，探讨这样一个引人兴趣的说法则使我们离题太远了。数学家们都不大关心旅行推销员这一专题。对于一系列较小的城市与公路网络，由于没有多少可能的路线需要审查，因而找到解法是很容易的。甚至对于大的城市与公路网络，那也可能幸运地或者偶然地找到最佳的路程。当数学家们宣称某问题实际上是不可解时，他们的意思是，仅仅知道保证解法的许多方法，就像穷举搜索所有可能性的方法一样低效，即使对于最高级的超级计算机来说，这种穷举搜索法也是太慢的。数学的行家对于快速（与可用）的算法和慢速（与不可用）的算法都有严格的确定方法。假设数字n是某问题大小的量度（对于旅行推销员问题，n是城市与公路数目的量度）。对于快速的算法，随着计算问题规模的增大，完成算法所需的时间的增长不会大于n（表示计算规模）的某个多项式。多项式是一种数学函数，诸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。而对于慢速的算法，例如用于解旅行推销员问题的穷举搜索法，则其执行时间将按问题规模增加的指数增加，即2n、6n或12n等。当n的值小时（也就是说，对于简单的问题），已知的多项式函数可以等于甚至超过已知的指数函数，但是当n的值大时，任何指数函数都将迅速地超过任何多项式函数。例如，当n等于2时，多项式函数n2等于4，它等于指数函数2n.但当n等于10时，n2只等于100，而2n却会像火箭上天那样猛增到1，024.毫无疑问，指数函数的增加会大大超过多项式函数的增加，这曾使托马斯。马尔萨斯感到忧虑，因为他发现人类的人口是以指数函数增长的，而与之相比，食物的供应则只以多项式函数增长。解旅行推销员问题，仅有已知的一种方法是按指数减慢的方法，即审查所有可能旅程的方法，这一事实意味着，在当今这个年代里，我们已不能对看来如此简单的问题有真正的了解。综合性理论学家总想试图证明这个迷惑人的猜想：不管我们如何努力尝试，我们对它都不会有任何了解，因为它就是不能理解的。看来与旅行推销员问题似乎有点相似的许多问题，数学家们对它们已经有所了解。例如，请考虑，一位公路检查员，他负责检查某段公路网，旅行推销员可能就在这段公路网上驱车。这位检查员渴望回家去看妻子和孩子，他想知道，是否有一条来回的路程，只须经过每条马路一次，只经过一次。但他并不关心城市，他只是想自己能走过公路的每个路段，而且还不重复。而从另一方面来说，旅行推销员却不关心公路，他只想去每个城市，每个城市只去一次，这样可把其汽车里程减到最短。伦哈德。欧拉1736年的研究工作，轻而易举地回答了公路检查员的问题。欧拉是一位29岁的普鲁士数学奇才。原普鲁士城市柯尼斯堡（现为苏联城市加里宁格勒）位于普雷盖尔河的两岸，并且包括克尼霍夫岛以及河流岔口中部的一块狭长陆地。城市的4个区域由7座桥梁的网络连接起来。据说，伊曼纽尔。坎特习惯于环绕城市进行长路程的保健散步运动，而且居民们也都想知道，是否可能有一条进行散步的来回路线，可以穿过所有7座桥梁，而每座桥梁只能穿过一次。由于桥梁的数目很小，这个问题可以用列举所有可能路线的方法（否定的方法）去求解，也就是说采用类似于旅行推销员这个小问题的、没有预见性的穷举法。这个问题由多产数学家欧拉去解，欧拉是一位有13个孩子的父亲，同时还著有80本书的数学研究成果。传说，许多研究报告都是在第一次与第二次叫他去吃饭之间的30分钟时间内写出来的，他预见性地证明这种路程问题无解。数学的灵魂大力提倡分析最普通的例子。因此，欧拉不仅想为柯尼斯堡的居民，也想为各地喜欢桥梁散步的人们解决问题，他试图解答一个普遍性的问题：“有若干河流及其分支穿过某一地区，并在其上架设任意数量的桥梁，已知河流与桥梁的布局，求是否有可能在每座桥梁只穿过一次的情况下，穿过所有的桥梁。”如果你把陆地区域看成城市，把桥梁看成公路，那么你就可以认为，这个一般性问题与公路检查员所面临的问题相同。为了解柯尼斯堡桥梁问题，欧拉用几何线表示每座桥梁，用几何点表示每块陆地。在这幅图中，欧拉已把问题简化成基本线条，去掉了所有无关紧要的内容。比方说，线与点的表示无法区别桥梁是宽还是窄，是特定的桥梁还是连接同一陆地区域的其他桥梁，是大块陆地还是小块陆地，乃至是岛屿还是河岸等。这些区别也许在其他方面非常重要，但与穷举的非重复性散步方法无关。这是一种漂亮的数学表示法：它仅需要在手边保留那些有关的情况，从而使数学家免受枝节问题的干扰，更能集中注意力于问题本身。欧拉已能证明，只有当点（陆地区域）为0或2，形成的线（桥梁）为奇数时，才可以进行穿过所有桥梁的非重复散步。你只要稍加思考就可支持这一结论。如果你穿过一座桥梁到另一处陆地去，必须还有一座桥梁让你离去，否则你将被困在那里。大片陆地需带有偶数桥梁才能确保那里有一条进去的路，另有一条离去的路。要是大片陆地只带有奇数的桥梁，那只有在旅程的终点（在那里你不需要一座桥梁离去）和旅程的起点（在那里你不需要一座桥梁进去）才有可能进行非重复的旅行。由于只有一个起点和一个终点，因此只有两处陆地才能有奇数的桥梁。在柯尼斯堡，4处陆地区域的每一处都连接了奇数的桥梁，即使没有比较严格的来回旅程条件，那么完全的非重复散步显然是不可能的。欧拉关于任意数桥梁与任意数陆地区域的结论要比归纳成普通的常识重要得多，认识到这一点很重要。我们的推论只是简要地说明，如果欧拉所断定的条件不能够满足，则非重复的旅行将是不可能的。欧拉的结论是很强有力的，直观上却不是很明显的：他证明了，如果这一简单条件得到满足，也就是说，当陆地区域数为0或2，而且连接它们的桥梁数为奇数时，非重复的行程总是可能的。要把欧拉的分析应用于一般情况，需要数出每处陆地区域的桥梁数。由于每座桥梁都要连接两处陆地区域，因此桥梁要两倍计数。如果桥梁数为n，那么欧拉的分析需要2n个步骤。桥梁的计数可以作为一种算法列出公式，而且它将成为一种非常有效的算法，因为虽然问题变得越来越复杂，演算所花费的时间却仅多了一倍。而从另一方面看，所有可能旅程的穷举搜索法则将成指数地迅速增长为2n.在旅行推销员问题中，对效率很低的穷举搜索法仍无简捷的方法。比方说，你仍不能计数出连接于每条公路的城市数，并根据这些数是奇数还是偶数来做出某种结论，或者就此而言，也不能根据这些数的其他性质得出结论。而且，这还不仅是我们不知道寻求那些性质的问题。还有可能是这些性质本来就不存在。这正是综合性理论学家都在努力证明的问题。旅行推销员问题不仅仅是惟一的计算问题，许多数学家都不理解其快速算法。还有一整套叫做NP-完全的问题，对于这类问题，人们仅知道其计算所需时间以指数方式激增。①在NP-完全的问题中，另有一个众所周知的例子称为人群问题：已知有一大群人，比方说，共100人，他们之间是否有许多人，比方说，有50个人，全都彼此认识吗？“你可以解这种问题，”美国麻省理工学院综合性理论学家迈克尔。赛普泽说道，“先投出 100个点，每点表示一个人，然后在相应的彼此认识的两人的点之间划一直线。”于是你将希望这组的50个点全都有连线。赛普泽接着又说：“看起来它很像一个有关计算机方面的重大问题，然而它不是。我们知道，如何去解这种问题，仅有的一种方法实质上是查看50人小组的所有连线，它们的数量非常多，就像10的29次方。要解出这个问题，即使应用快速的计算机，也要好几百年。”旅行推销员的问题、人群问题、以及所有其他NP-完全的问题，都有难以理解的共同特点：如果有人声称，他对于这类问题中的任何一个特殊事例已经有了解法，那么要检验这个解法则是很容易的事。对于旅行推销员问题，只要检查所提出的旅程，并查明是否包括了每个城市一次。对于人群的问题，则要双向检查已被辨认全都互相认识而成群体的50个人。美国伯克利市加利福尼亚大学计算机科学教授理查德。卡普把 NP-完全的问题比作拼图玩具：“它们可能难于组合，但是当有人向你展示一幅完全的拼图时，你就能一下子知道问题已有正确解。”NP-完全的问题还有一个醒目的特点，如果这类问题中的任何一个问题能够用快速算法求解，那么其他问题也都能用此法解出。而且，对于某类NP-完全问题采用快速算法毫不费力，而且稍加改进，就可用于解任何其他NP-完全问题。例如，如果人们发现了一种用于解旅行推销员问题的快速算法，那么数学家们就会自如地运用快速方法去解人群问题和所有其他的NP-完全问题。因此，旅行推销员问题是否有快速解法与NP-完全问题是否真的像看上去那样难这一较大问题有关。美国电话电报公司的戴维。约翰逊说道：“我认为，现在每位数学家实际上都认为NP-完全问题有内在的困难。”约翰逊是这一领域的权威人士，著有《计算机和难处理性：NP-完全理论指南》一书。他还说：“真正的问题是证明它。”这种论点动摇了一些数学家的想法，他们认为他们也许能够证明旅行推销员问题及同类的其他问题都不会有快速解法——从来就没有过——即使未来让爱因斯坦一类大师来绞脑汁也不会有。他们怎么会提出要证明这样的问题？目前的工作都集中在逻辑门上，它已被认为是计算机硬件中最基本的单元。在电子计算机内，逻辑门是一种组件，由任意数目的输入引线与一根输出引线组成。逻辑门也是一种二进制器件：每根引线中的信号都被认为或是1、或是0.（在电子学术语中，高电平对应于1，低电平对应于0.）每一个逻辑门都能完成3种基本运算中的1种：“非”、“与”或“或”。这3种运算的名称都是根据布尔代数中已经使用的词“非”、“与”和“或”而得来的。布尔代数是19世纪40年代由乔治。布尔研究出来的一种开拓性的形式逻辑体系。布尔是一个贫穷补鞋匠的儿子，他自学数学，研究出符号逻辑体系，其中1表示真的，0表示假的。尽管布尔的研究工作使他获得了爱尔兰科克大学的数学教授职位，但直到100多年后第一部电子计算机问世之后，他的逻辑体系才得到数学界的完全赏识。在形式逻辑中（和日常的英语中），词“非”加在前面可把真语句变成假语句，而且反过来也一样。把它换成布尔代数的术语，则是“非”可把1转换为0，0转换为1.因此，“非”逻辑门有一根输入引线，并把输入信号转变为其相反信号，即如果输入是1，则输为0，而如果输入为0，则输出就为1.当然，词“与”用于连接单个语句成为复合语句，即如果每个组元都是真的，那么复合组元也是真的。现举一简单例子，“朱尔斯吃豆腐与吉姆吃多夫条形面包”，只有当朱尔斯和吉姆两个人都在吃上述的食物时，它才是一个真实语句。由于同样的理由，“与”门可接受两个或多个信号输入，如果所有的输入都是1时，那么输出也是1，否则，则输出为0.词“或”也是用于连接语句成为复合语句，但只要一个或几个组元都是真的，则其复合组元也是真的。如果朱尔斯或者吉姆（或者他们两人）在吃他们各自的食物，那么“朱尔斯吃豆腐或吉姆吃多夫条形面包”才是真语句。同样地，“或”门可以接受两个或几个信号输入，但只要至少输入之一是1时，则其输出也是1.布尔代数的绝妙之处在于，1和0不仅表示真的和假的，而且还可以表示任何两种不同的状态。例如在旅行推销员问题中，0和1可以表示城市之间的相应关系：如果两个城市由一条公路连接，则以1表示，如果它们没有公路连接，则以0表示。在人群的问题中，1可以表示两个人成为朋友的状态（或者在该问题的图解表示法中，表示由一条线连接的两点），0表示他们不是朋友的状态（表示没有线连接的两点）。在计算机中，任何数目的“与”门、“或”门和“非”门都可以连接在一起，形成一种电路。例如下图示出4个“与”门和1个“或”门组成的一种小型电路，它可以用来求解人群问题的普通实例：在4个人的一组中，有3个人是朋友吗？然而，随着人群问题的人数增加，用于已知解法的电路大小（也是逻辑门的数目）将按指数方式激增。如果数学家们能够证明，对于任何可能已知或未知解法，电路必按指数方式增大，那么他们就能证明人群问题没有快速算法。数学家们还不知道如何开始这样的证明，已经转而考虑另一特殊的问题，这就是通常都有快速算法的奇偶函数，而且他们还试图以某些基本方式来限制电路，使得快速算法不再产生作用。（奇偶函数可在一串的0与1中确定是否产生偶数或奇数。）这种方法看来也许有些怪，其实它并不怪。数学家们对于如何证明电路必须是大型的了解甚少，因此为此目的而做的任何证明，甚至是某种人为的情况，也都将会有所进展，而且可以提供证明真正论点所需的数学工具。赛普泽说道：“这是数学中的普通方法。如果问题很大，可试图把它限制到某些范围，并求解其中一部分，希望这种分部解法使人们对原来的问题会有更深的了解。”在这一领域内，早期的工作限制了电路的研究工作的深度，这里的深度是指逻辑门的层次数目。1981年取得了第一批成果，当时美国卡内基-梅隆大学的赛普泽及其两位同事证明了，如果他们限制用于奇偶函数的电路深度，那么电路宽度的扩展快于任何多项式。1985年，美国斯坦福大学的安德鲁。姚在这方面取得了更惊人的研究成果，他证明了电路的宽度不仅以超多项式的方式扩展，而且还以指数的方式扩展，这表明这种问题虽然受到人为的限制，但也有内在的困难。姚的成果很快地传遍了数学界。赛普泽这样说道：“每个人都认为这个结果很满意，但也是非常复杂的。”姚的方法为他人铺平了道路，好几个研究人员很快地对他的结果做了改进。美国电话电报公司贝尔实验室数学科学部主任罗纳德。格雷厄姆说：“这很像开车的头4分钟路程，一旦有人学会它，那么人人都可以学会它。”1985年8月，美国麻省理工学院计算机学科研究生约翰。哈斯特德采用了姚的基本理论，但是简化了他的论据。哈斯特德说道：“在工作过程中，我获得了比较有力的结果。（在这种有限制的问题中）我们所知道如何设计的最小电路并不比我在理论上曾经证明它们应有的规模大出很多。”后来的证明都表明：数学家们实际上知道如何设计出并不比他们在理论上所推断的最佳电路差很多的电路。对于这些有限制的问题来说，不是数学上的无知，而是问题的本身排除了快速的解法。苏联莫斯科大学的两位数学家阿。拉兹波洛夫和阿。安德烈耶夫在不限制电路深度但却限制所进行的运算方面取得了很大的成功。拉兹波洛夫又证明了如果不允许用“非”门的话，则用于人群问题的电路规模的增长将快于任何多项式的增长。而且，数学家们还在这里对这一结果做了改进，它表明电路必须是按指数方式增大。安德烈耶夫通过禁止用“非”门还能够证明另一类问题也需要大规模电路。这些成就使这一领域乐观起来，虽然还没有人知道怎样才能减少对电路的限制并证明在无限制的情况下，旅行推销员的问题的确很难。“还有很长的路程要走，”赛普泽这样说道，“6年以前，我曾与人打过赌，我希望他还记住，将在2000年得出证明。我仍然信心十足，还有12年多的时间。”格雷厄姆还抱有更大的希望：“在以后3年内得到证明也不会让我吃惊。”尽管人们普遍乐观，但在综合性理论方面（数学的一个分支学科，它表述了问题的难度）的研究人员，以他们的直觉已经知道他们会失败的。1985年冬天，美国麻省理工学院的数学研究生戴维。巴林顿曾证明，计算机能够运算的某些原始表示法会比该领域中任何人所能设想的更有功效。这种原始表示法不包含“与”门、“或”门和“非”门，但却包含一个分支门，它也有两根输出引线。当分支门受到触发时，如果输入信号具有一定的指定值，则分支门就会沿两根引线之一送出一个信号；对于所有其他输入信号，分支门沿另一根引线送出一个信号。换句话说，分支门能够处理计算机程序中的语句，诸如“如果x=5，转向步骤4；对于所有其他x，转向步骤7”。巴林顿又证明了，全部由门层次不超过5层的分支门构成的电路，可以解所谓的多数问题：在一串的0和1中，1是不是多数？综合性理论学家普遍地（并且错误地）认为分支门限制于任何固定高度，不可能求解多数问题，更不用说严苛的五层限制了。巴林顿说道：“我的证明很简单，但它令人惊奇，因为他们总是认为我所试图证明的都是假的。”巴林顿的结果也许没有多少实际用途——他又说：“除了它可以让我在一所好大学获得一个教师职位之外。”而且它还可以说服数学家们不要在复杂的综合性理论领域中如此自信。________① 如果你一定要知道的话，NP表示非决定性的多项式，而complete一词则意味着这些问题是该类问题中最难的。第十章 计算机——未来的象棋之王到此为止，我们所注意的大部分是计算机科学中的理论问题，计算机和人在原则上能进行哪些类型的计算。我们已经讨论的限制都是无条件的。如果综合性理论学家能够证明他们的推测是真实的，那么旅行推销员问题就不可能找到有效的解法。这既不是因为数学家的问题，也不是计算机缺少适当的运算工具；而是根本没有这种工具，将来也决不会有。大多数的数学家和计算机科学家都不会遇到理论上难以超越的限制。他们所面临的障碍都是自我设置的，而且都是可以超越的，至少在原理上是可以超越的。一个主要的障碍——在数学之外的许多工作中也很突出——就是这样一种倾向：稳妥的做法是照搬被普遍接受的他人的解题方法，即使这些方法不是那么圆满。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂来，否则就会招来他人的嘲笑。本章内，让我们看看汉斯。伯利纳的开拓性工作，他制造了一台能够下好国际象棋的计算机。下一章，我们则将探讨W.丹尼尔。希利斯的工作，他试图用他自己的改革性设计取代曾很好地为电子计算机服务了40年的基本体系结构。汉斯。伯利纳是美国匹兹堡市卡内基-梅隆大学计算机学科的研究人员，他本人态度文雅，还很想跻身于世界佼佼者行列。他曾经有过这样的荣誉，现在也想为他的计算机成果赢得同样的荣誉。1968年，他曾以42步一盘棋的卓越成绩击败了苏联足智多谋的国际象棋策略家J.埃斯特林，成为国际象棋通信比赛的世界冠军，为此他曾扑在棋盘上琢磨战术整整500小时。1979年，他又设计了称为BKG（15子棋）9.8的计算机程序，并在蒙特卡洛城举行的大做广告的15子棋①比赛中，以7－1的压倒比分击败了世界15子棋冠军意大利的卢吉。维拉。伯利纳也和他自豪的父亲一样，他很高兴，BKG9.8程序已成为第一台能在任何棋盘上或纸牌游戏比赛中击败人类世界冠军的机器。现在，BKG9.8程序已被搁置起来，世界15子棋联合会已禁止在正式比赛中应用计算机，但是，由伯利纳和他的研究生卡尔。埃贝林设计的一种称为Hitech（高科技）的新计算机程序却在另一种棋盘竞赛场所中保持了计算机的荣誉。1985年10月，Hitech程序赢得了北美计算机国标象棋的冠军称号。这项成功与其他一连串击败人类天才的胜利一起，完全证明了Hitech程序在下国际象棋方面优于任何其他计算机，也优于参加美国国际象棋协会认可的各种比赛的30，000名高明棋手（“思维”人）的99％。现在，伯利纳已注视着弗雷德金奖金，这项10万美元的奖金将给能击败人类世界冠军的第一台计算机的设计师。Hitech程序目前要击败人类世界冠军力量尚不足。但就伯利纳的顽强性格、教育情况与比赛纪录来看，其程序的前途是不可低估的。若按年月顺序来看，伯利纳早先热爱国际象棋，而后才爱他的计算机。他1929年出生于德国， 8岁时随父母迁居美国，定居在首都华盛顿。他发现那里的学校的要求比德国松得多，因此他寻求课堂外的挑战。在1942年的夏令营时，他看到了一些年轻人在下国际象棋，就向他们请教比赛规则。伯利纳回忆说：“甚至就在第一天，已有些棋手成为我的手下败将，情况就是这样。我从此着了迷。”两年以后，他是他所在地区国际象棋俱乐部的冠军，并且保住华盛顿地区最佳国际象棋俱乐部冠军的称号。伯利纳说道：“我父母从不鼓励我。他们警告我说，如果我把时间都花在下棋上，我将没有什么前途。如果没有人告诉我，谁知道我将成为什么样的人？”不过在短期内，伯利纳未控制自己的棋瘾。到了1949年，他终于赢得了人人盼望的华盛顿市国际象棋冠军称号，那时他刚刚20岁，这是个破纪录的年龄。同年，美国数学家克劳德。香农发表了一篇颇有影响的论文，他在论文中概括地论述了如何编制计算机下国际象棋的程序。当时电子计算机刚刚问世，但是，下国际象棋已被作为在新生的人工智能领域中的一个重要的目标。它与其他智力游戏不同，国际象棋引起人们的兴趣是因为在控制的条件下，通过让计算机与人类选手对阵就可以精确判断出计算机在国际象棋上的能力。参加比赛的棋手都有数字的等级，这是根据他们与其他等级对手比赛时的成绩如何而定的。计算机也要取得等级，以反映它与人的等级棋手比赛所获得的成绩。当计算机科学的先驱们努力把香农的想法付诸实践时，年轻的伯利纳正集中精力于下国际象棋。1954年，他是这个国家中最佳的12名棋手之一，并保持了12年。50年代初期，他阅读有关计算机下棋的第一批研究成果。他回忆说：“他们的把戏在我看来是相当可笑的。”英国数学界杰出人物艾伦。马西森。图灵也是计算机的开拓者之一，他是人工智能方面有创造性的思想家（已在第八章中论述过），而且，惮精竭虑地穷究数学领域的奥秘。他还是一名国际象棋手，和爱因斯坦一样，即使算不上精通，也至少乐此不疲；也许由于他认为国际象棋是少数几种他未掌握的智力活动之一，因此他毕生热爱这项活动。不管情况如何，他至少撰写了6页有关以机械方式下国际象棋的配方性棋步，这实际上是一种计算机程序。虽然他还没有花费精力把下国际象棋的方法译成编码输入计算机，但他曾用这些配方棋步于1952年与阿利克。格伦尼对弈。阿利克。格伦尼是英国曼彻斯特大学的一名学生，他也是很有才能的计算机程序设计者，但却是一名不大高明的木材推销员。图灵的纸上下棋机（所以这么叫它是因为它还只是在纸张上存在）在那次对弈中失败了，但毕竟是首次用任意一种理想化的或者可以实现的计算机下棋。图灵的配方是给每个棋子以数量价值，像国际象棋教科书所定级的那样，以便大体上反映各棋子的相对实力：王1，000，后10，车5，象3.5、马3和兵1.在选择棋步时，都是接着走所有后续棋步，包括捉子在内，一直走到两方既不能吃子也不能给予将死的静止棋势时为止。对于每种静止棋势，两方的相对实力是把棋子的数值加在一起进行计算的，并把计算机的棋子数值看成正数，把对方的棋子数值看成负数。选择导致静止状况的棋步，在这种状态中，机器能使其相对实力增加到最大限度。图灵的估值方案是能够找到求胜的棋步的，但是在静态情况下则无法使用。例如，它不能判别白方的头一步如何走，因为在比赛开始时，在其20个可能的棋步（16个进兵步和4个上马步）中，没有一步棋捉子或者可能捉子，因此这20个静止棋势都是同样0值的相对实力，显然，要用该方案判断是很荒谬的。图灵还用加权的方法来克服这个问题，在静态棋位中考虑诸如机动性与王的安全性等因素。例如对兵来说，走兵越过自己的布阵之后，每横线增加0.2，如果受到别的子而不是本方兵的保卫，则另加0.3，如果不受到保卫，则要另减0.3.对于车、象、马和后来说，如果走它们能走的法定棋步，则每走一步棋都增加其数值的平方根，如果这些棋步中至少有一步棋可以捉子，则另加1点。而且，要是车、象、或马（不包括后）受到保卫，得到保卫一次另外奖给1点，两次或两次似上另外奖给2点。如果王得到车的保卫，则加0.3，如果与车保持均势，则加0.2，要是以车保王未来仍能出现，则加0.1.图灵也考虑王的安全性。在他的估值方案中，王所要损失的点数取决于它易于受到攻击的程度。图灵设想王是另一个后，并计算这个后的机动性，用此来量度其受到攻击的程度。此外，图灵还给攻对方王棋的棋步增加0.5，给立即能将对方王棋的威胁性棋步增加1.在静态情况下，纸上下棋机将按照其求值函数、最大的机动性、本方王的安全性以及对方王的易受攻击性来决定棋步。在1952年与格伦厄博弈时，纸上下棋机以P－K4开局，即走王前兵两步，在20个可能棋步中，P－K4棋步具有最大的数值，这个棋步不仅可以进兵到第四横线，而且还可以提高后、王前象和王前马的机动性。早在第三步棋时，纸上下棋机走了一步软着的兵出击，但格伦尼并没有乘机利用它。在第二十九步棋时，由于纸上下棋机的求值函数示出格伦尼没有立即有效的捉子应步，因此它贪婪地用后吃掉一兵。纸上下棋机的程序忽视一个简单然而可以压车的棋步，该棋步可以用下棋机的后看住对方的王，使得后可以强行捉子。最后，图灵这个安乐死控制论的倡导者，代表纸上下棋机主动认负。纸上下棋机尽管非常原始，仍然有一些独到之处。例如，它认为，只有在没有任何捉子的可能时，实力的研究才有重要性。在棋盘上的某一棋位中，你可能缺少后，这种情况通常是很糟的，但只要是该你走子，你仍有机会，你可能捉住对方的后。你大概不需要一个估值的过程，它只不过统计出棋子的相对实力，却没有把可能的捉子考虑进去。当图灵把诸如机动性与王的安全性等国际象棋知识的一些方面包括在求值函数之内时，他的思路是正确的。在与格伦尼博弈时，纸上下棋机的棋输掉了是由于这些知识还不够充分。它不能辨别在特定的棋局中的内在的危险性：王与后在同一纵列上。伯利纳和其他国际象棋大师，甚至许多很不熟练的棋手都把这种棋局和不计其数的其他棋局牢记在他们脑子里。研究证明，人类国际象棋大师对棋局和棋位都有非凡的记忆力，而且这种优异的记忆力不一定会转移到与国际象棋无关的事物上。站在人的水准上，伯利纳觉得，他在棋盘上所享受到的成功的喜悦没有延续到教室中，至少在最初时没有。伯利纳回忆说：“一些人往往刚上大学不久，就会遇到麻烦，我就是其中之一。本来，我曾是一名物理学的优等生，但是不知怎么一来，我走上了岔道。我一边打工，一边上学，终于攒够了钱来付学费，可以不再打工。这是一个关键性的错误，忽然间我有了很多时间，因此除了下国际象棋之外，我还打桥牌。很快地，我就成为华盛顿市15名最佳桥牌手之一。一切都砸了锅。”伯利纳服完兵役后，想返回学校。他接着回忆说：“我未能完成物理学学业，因为我的平均学分太低，因此我转修心理学。看来这是个广阔的研究领域，因为全是些有兴趣的事。”伯利纳是从物理学转来的，他期望能把事实归纳成理论，但是他失望地发现，情况恰好不是那样。1954年，伯利纳结婚了，在家庭生活与新工作之余，几乎没有时间打桥牌，不过他还是想方设法继续下国际象棋。他接着说道：“我在美国海军研究实验室从事称为人类工程的工作。那是非常严肃的工作，牵涉到心理学与物理学，与设备的设计有关。那是在1955年，当时计算机刚刚问世，实验室里也造出一部。我曾修过一门程序设计课程，大概编写过20行有关加数的程序，但是除此之外，我没有接触过计算机。”“因为没有时间旅行去参加国际象棋比赛，我决定参加通信国际象棋活动。这又是另一项重大错误。它无休止地在棋盘上花去我更多的时间。随后的13年内，我参加了许多国际象棋的通信比赛，并且赢得了所有比赛。在世界通信锦标赛中，我必须下16盘棋。我估计，要思考每一步棋，平均需要花去4个小时的时间，一盘棋大约需要走35步，这就意味着，要赢得该比赛冠军，我要投入2，200多小时的时间。接着，我实际上还是放弃了该项比赛。”他考虑为了保持该项冠军还得再花2，200多小时的时间，是很不值的。1961年，伯利纳进了美国马里兰州贝塞斯达的国际商业机器公司（IBM），成为一名系统分析家，并且主要工作是面向军界。虽然他在那里工作了8年，而且奋力进取，升任了经理，但他仍觉得这项工作得不偿失：“如果你很认真地工作，这是一种可怕的生活。作为一名经理，你必须对上下都要负责任。你有一批人为你工作，但他们的确对工作毫不关心。还有一个家伙来自军界，他其实什么都不懂，还对你指手画脚，或提出一些无理要求。后来又有一个人接替了这个家伙的工作，他根本不知道第一个人想要什么，于是命令改变一切。我开始觉得，我所要做的工作应该是，在我回首往事时，能使我感到骄傲的工作。我希望从事研究工作。”伯利纳继续进行用计算机远距离下棋的探索，但他看到进展很慢，感到失望。在50年代期间，学者们曾做过乐观的预测，但它与实验室内的成功不相吻合；例如，1957年，美国卡内基-梅隆大学现代诺贝尔荣誉获得者罗伯特。西蒙就曾声称数字计算机将在10年内成为世界的国际象棋冠军。计算机程序设计的重要性还没有完全得到认识。按照公众的看法，国际象棋大师就像一种人类的计算机：当他选择一步棋时，他在心目中还要探索几百步后续棋，如果我上了王前兵，那么他将同时攻我两车，而后我将捉他的后……都以惊人准确的闪电速度下棋。计算本来是计算机的主要功能，因此它们在国际象棋上似乎应该是天生的冠军。问题在于公众的这种看法是错误的，对于国标象棋大师来说，计算不是惟一的甚至不是成功的主要的秘诀。他们的成功更多地取决于对棋局的判断，而不是研究那些令人头痛的棋步。荷兰的心理学家安德里安。德格鲁特发现，在典型的棋法中约有38步可能的法定棋步，而国际象棋大师平均只考虑其中的1.76棋步。换句话说，一位象棋大师通常根据自己曾经下过或看到别人曾经下过的成千上万步棋，在他所能判断的两个候选棋步中进行选择，这种选择对实现该棋步的眼下和长远目标有利。美国的一位国际象棋特级大师威廉。隆巴迪老人曾经写道：“在实现目的之后，即取胜的布局转变成为数学上的强力取胜的时刻，计算最为常见。”只要花一两秒钟，就能一眼认出所熟悉的布局，这是象棋大师们在棋赛中具有惊人优势的根本原因。在动态的棋局中，简直没有时间进行预测。许多早期的计算机程序都只局限于考虑选择候选棋步的数量（尽管它根本就不会是1.76这么小的数）。应用选择搜索方法的问题在于没有人知道如何用计算机语言，更不用说是用英语，来表示用于选择候选棋步的一般失效保险原理。 1966年，由美国麻省理工学院的理查德。格林布拉特研究的早期选择搜索程序MacHack最为成功，它已成为在比赛中击败人类棋手（即使是最弱的一名棋手）的第一部国际象棋计算机。MacHack程序还有幸驳倒了休伯特。德赖弗斯的看法，德赖弗斯是《计算机不能做些什么》一书的作者，他曾靠贬低计算机的能力而出了名。然而MacHack的功能一般说来还有严重的缺陷。虽然它在下棋时能够胜任持续时间很长的棋局，但它还是易于突然犯下某种可笑的错误，而这种错误多少是由编入该计算机程序的象棋原理造成的。此外，它有时也会对某些巧妙但却显然违背了象棋原理的棋步视而不见。但是它已在比赛中击败了人类棋手，因而是计算机国际象棋的里程碑。伯利纳回忆说：“我的上帝！当我听到有关MacHack程序取得胜利的消息时，我认为，尽管计算机国际象棋受到如此冷遇，尽管人们做了种种努力却收效甚微，但还是有希望的。我去拜访格林布拉特先生，虽然我还不完全理解计算机真的会按他所希望的去做，但我还是留下了深刻的印象。由于我离了婚，还没有再婚，我又一次有了许多时间，因而我自学计算机程序设计，并花去许多晚上和周末时间编写计算机国际象棋程序。我向美国国际商业机器公司申请让我到该公司在纽约的约克顿海特斯研究机构中从事计算机国际象棋的工作。他们答复说：”我们不资助这类项目。而且，你还没有博士学位，因此，如果你能做些对公司有益的其他事的话，我们顶多让你稍微做一点这方面的工作。‘““我认为，要达到我的目的，惟一的途径是获得博士学位，以便进入该公司。我对自己的基本情况很自负。我向几个学校提出了申请，但只有卡内基-梅隆大学接受我。”他在1968年获得世界通信国际象棋比赛冠军的胜利显然有助于他进入该校。“因此，我是在1969年秋季40岁时成为一名学生的。这对我是多么大的震惊。我觉得我需要学习的东西实在太多了，像自动化理论、各种不同的程序设计语言、多种多样的硬件配置、以及人工智能本身等等。”伯利纳早年在高等学校中不喜欢的许多课程，现在反而都要修读它们。