直到最近,数学家才能检验证明的正确性,可一旦求助于计算机解决一些长期遗留的问题,就只有计算机能检验答案。

1976年,依利诺斯大学的两位数学家肯 · 埃普(Kenneth Appel)和沃 · 哈肯(Wolfgang Haken)解决了四色问题。四色问题是1852年由伦敦大学的学生佛 · 欣斯里(Francis Guthrie)提出的,他当时观察到:如果近邻区域着以不同颜色,那么用四种颜色足够给任何画在面上的地图着色。他由此提出疑问:是否能够从数学上对此加以证明。一个多世纪以来,虽然有人试图解决它,但都失败了,只有埃普和哈肯成功地获得了证明:四色足以给地图着色。欣斯里在提出他的著名问题时根本不知道怎样给以证明。此证明的大部分工作是由计算机完成的,并且证明正确性的检验也离不开计算机。

史无前例的使用计算机来进行数学证明引起数学家的争论并带来实际的和哲学上的问题:我们怎么知道程序设计者和机器都没有出错?这类证明的主要方法不同于传统的由纸笔完成的证明吗?数学其理并非先验的而是经验的吗?

自那时起,另外一些计算机辅助的证明也实现了。关于证明的有效性还存在争论,1988在纽约时报上一篇文章以这样的标题问道:“没人能检验的证明算是数学证明吗?”其中提到了十阶投影面不存在的证明,这个两世纪前提出的几何问题,稍微籍助计算机的帮助就得到了解决。什么是通过计算机完成的数学证明?什么是常规的数学证明?

1928年英国著名数学家乔 · 哈代(George Hardy)用富有诗意的话对数学证明的特征和目的作出了解释。他将数学家比作一个注视远处山峰的观察者,认为证明的最根本目的是使人确信。

典型的数学证明是从已知的真理经逻辑演绎而得到新的真理,已知的真理可以是显而易见的也可以是已被证明过的e大多数证明书写出来要几行乃至几页,有的也许更长。瓦 · 费特f Walter Feit)等关于所有奇数阶群可解结论的证明需要251页,而著名的Ramanujan猜想需要两千多页。

从传统的观点看,一个证明应该能够被有足够耐心和能力的数学家所检验,这要求与实验科学上的“可重复性”是等价的。当然,即使证明已被检验也可能是错的,出现这种情况的有伦敦数学协会成员兼法律顾问阿 · 肯普(Alfred Kempel)对四色问题的证明。

19世纪20年代德国数学家希尔伯特和他的学派发展了一种关于数学证明的形式化理论体系,在这种体系中先将数学命题用形式化语言来表达,这些表述本身是无意义的,它们无所谓对与错,根据一定的演绎规则可以从一些表述得到另一些表述,这些“证明”实际上是用纯粹形式化方式得到的表述的继续,只与表述的形式有关。更进一步,给定一个“证明”,原则上可以从数学上检验其正确性,比如说可用机器来完成。

希尔伯特的目的主要不在于进行数学工作以便确立一种内部自洽的数学,他并没有成功。几年前奥地利逻辑家哥德尔认为:任何证明数学是内洽的企图都是白费。但形式化工具抓住了数学的一些根本特征,而今的大多数证明还具有形式化体系演绎的轮廓。

并非所有人都赞同数学证明有效性的标准。“直觉主义”学派数学家一直对“街头数学家”认为理所当然的逻辑原理持怀疑态度,比如说“排除中项原理”,给定任意命题P,要么P是真要么非P是真。这种直觉主义工具排斥那些常用在主流数学中的许多证明形式。

计算机从什么地方着手呢?计算机以多种方式帮助数学家:计算、解题和模拟,还可以画图作曲线,还帮助进行数学真理的证明,通过“计算机辅助证明”,我们知道用于传统证明检验的手工方法不能对由计算机获得证据的证明进行检验,比如说希 · 威尔夫(Herbert Wilf)为证明组合恒等式所编的程序。但是在我们头脑中认为这类证明并非计算机辅助的,因为我们能将计算机的结果转换为常规的纸笔的证明,简而言之,如果我们除了相信计算机外别无选择,那么这个证明就是计算机辅助的。

信任计算机

四色猜想与十阶投影面不存在的证明是利用计算机解决问题的两代表。这两个问题折腾数学家很长一段时间,这表明传统证明方法是不能胜任的,即使完成了证明,但要检验的事例数量之大已超出纸笔计算的范围。

计算机能以很快的速度执行程序指令,它能按照数学家的思维运行,让我们考察计算机在解决投影面问题中所起的作用。

投影面是由一定数量点和线构成的抽象几何体。最简单的是由三条线联结三个点所构成的三角形,这个面的阶数为1,不同的投影面具有不同的几何特征。每个面可用由0和1组成的关联矩阵来表征,每个矩阵满足一定的可被检验的条件。对十阶投影面,矩阵应有111行和111列,每行有11个1和100个0——这个关键,如果不存在满足这些条件的矩阵,则说明不存在十阶投影面。

这样可将寻找投影面简化为寻找其关联矩阵。对所有的由0与1组成的111阶矩阵进行系统的检查,即使是超级计算机也不能胜任。

蒙特利尔的康可地亚大学的拉姆(Clement Lam)等通过理论手段设法将可能出现的情况数减少到计算机能处理的水平。他们用了一种称作“回溯寻找”的算法语言来为寻找编程,开始设定一空矩阵,计算机根据关联矩阵所满足的条件a行填充,如果至少有一种情形符合条件,说明存在十阶投影面,但是Cray-IA计算机最终没能找到这样的关联矩阵,由此得出结论:不存在十阶投影面。

我们可将不存在十阶投影面的证明归结如下:如果存在一个,那么计算机应能找到它。面对这样的“证明”,我们或许会问:怎么知道软件或硬件没有出错?回答是:不能。

如果计算机出错怎么办?

计算机辅助证明存在许多出错的可能:错误的输入、程序错误、编码器中未被发现的错误和硬件错误,无论如何可以肯定是某些错误确会发生。拉姆也承认这点,他写道/这是实验结果,总存在出错的概率,但存在未被发现的十阶投影面的几率是很小的。”

很显然验证证明的正确性是不可能的。我们可以检查所有计算机程序指令(还有编码器和操作系统),但不能保证不存在内部硬件错误和运行过程中的随机错误。

如果不能消除出错可能,就应该间接地确定结论的有效性。比如说,用不同的程序、不同的机器进行独立的验证,另外还要考虑时间因素。存在一个简明而根本的逻辑原理:从错误的前提可以得出任何结论,如果四色猜想是错的,由它证明其它理论,总有一个会与已知事实相矛盾,若根本不存在矛盾情形,这使得计算机结果更加可信。

计算机用于证明给数学家带来了不确定性问题,这对实验工作者已司空见惯,这也许是利用如此优越的工美所付出的小小的代价。正如拉姆所说的:“像物理学家离不开不确定性(测不准)一样,数学家也应学会与不确定性证明共处。”

中心论题是证明的长度问题,某些数学命题最短的证明对人来说也太长了,大家公认的不知道是否存在一个重要而有趣的涉及如此问题的理论。还有,即使命题P的证明只能是很长的,也可以存在如陈述句“存在命题P的证明”这样短的证明,使某些命题也可能没有常规形式的证明。埃普也持这个看法,他写道:“我们关于四色问题的证明充分表明了数学中只通过理论手段完成某些问题受到限制。”

如果将哈代的类比更进一步,计算机辅助证明就像通过空间探测器发送到遥远星球上的山峰的图像。作为观察者可能拒绝承认这种电子图像,认为是不可靠的第二手证据,即使如此他会认识到:即使没有看见它,山峰也可能存在。

根据马林(Manin)的观点,在证明概念中还含有时间因素。他说:“‘证明’被理解为‘用当时的手段实现的证明’。比如说,如果引入一个新的集合论公理并被广泛接受,那么证明的概念可被拓宽。”

计算机的应用也许迟早会变成一种可被接受的手段,更有甚者,如美国数学家约 · 米诺Milnor)以调侃的语气所说的:“在未来的两代里,某些东西只有经计算机检验才能算是被证明了的。”

[New Scientist,1991年2月23日]