张正育张正齐

在1976年以后，从美国伊利诺斯州厄班纳寄出的邮件，除了盖有通常的邮戳外，还加盖了一个特殊的邮戳，那是一句颇带炫耀口吻的话——“四色是足够的!”

厄班纳人如此炫耀是可以理解的，因为那个特殊的邮戳所纪念的，的确是数学史上的一个重大事件——让数学家们困惑了100多年的“四色定理”，终于由厄班纳的两位居民证明了。

四色问题是在1852年由一位21岁的大学生最先提出来的，他猜想，任何地图都可以只用4种颜色着色，使得任何两个相邻的区域都着上不同的颜色。

这个问题看上去是那么简单，就是一个小学生也不难理解；结论的正确性看上去也是无可置疑的，谁要是不相信，请他随便画幅地图试一试好了。但是，数学的严谨性要求，任何一个数学命题只有获得了严格的证明，才能被承认为数学定理，而正是这样一个基本的要求，却难倒了100多年来许多优秀的数学家，使四色问题也像“哥德巴赫猜想”这一貌似简单的问题一样，成了一道著名的数学难题。

1976年6月，伊利诺斯州立大学的两位数学家哈肯和阿佩尔宣布，他们证明了“四色是足够的”，从而使这道长期悬而未决的难题变成了一条真正的数学定理。

在数学史上，一道难题获得解决的意义，往往并不在于又增加了一条新的定理，而在于在解题过程中，数学家们发展了数学思想，创造了新的数学方法。那么，这一次哈肯和阿佩尔作出了什么新的贡献呢？

最令全世界瞩目的是，他俩对四色定理的证明，是在电子计算机上完成的!

人们一向把证明数学定理看作是对人的智力的严格考试。现在，数学家们没有解决的问题却在计算机上解决了，难道它比数学家的智力还更高超一些吗？

对这个问题，不能简单地用“是”或“不是”来回答。让我们还是先看看电子计算机是怎样完成四色定理的证明的吧！

哈肯和阿佩尔在1972年就开始研究四色问题。他们注意到，英国数学家肯普曾经在1879年发表了一个巧妙的“证明”，基本思路是考虑地图上相邻区域的数目不同时各种可能的情况，证明每一种情况下都不必要用5种颜色着色。这实际上是运用的穷举归纳法。后来，人们发现肯普的“证明”中出了错，原因在于，按照肯普的穷举归纳的思路，必须把情况分得足够细，并逐一判断每种情况是否可以“归约”（即是否不必要用五色着色），而这一工作的复杂程度，是运用已有的数学技巧由人力所不能完成的。于是，哈肯和阿佩尔考虑让计算机来完成这项工作。他们一方面从理论上继续简化问题，一方面用计算机试算。到了1976年1月，他们认为可以上机操作了，便将他们编出的一种很复杂的程序输入IBM360计算机，让计算机去寻找各种可能的情况（称为“构型”）并逐一判断它们是否可以归约。

事实表明，这项工作对于计算机来说也并不轻松。计算机工作了1200多小时机器时间，进行了上百亿次逻辑判断，对1482种构型逐一验证了它们都是可归约的，这才修补了100年前“肯普证明”中的错误，完成了四色定理的证明。

四色定理的机器证明是一项重大的数学成就，其真正的意义，在于它以胜过雄辩的事实，有力地回答了，电子计算机究竟能做些什么？它同时还重新挑起了一个长期争论不休的话题：电脑能胜过人脑吗？

计算机能做些什么？这个问题实际上早在电子计算机问世之前就已经有了答案。

英国的图林是一位对电子计算机的理论和技术发展都作出过突出贡献的数学家。1936年，他通过把人的计算活动分解成几个基本的机械动作，提出了一种抽象的计算机模型，即所谓的“图林机”。图林机的结构很简单，动作也很简单。我们不妨把珠算盘看作图林机的一种物理原型。图林机有一条打上方格的纸带，每一格都可以写一个数码——珠算盘的每一档就相当于图林机纸带上的方格；图林机有一个读写头，它在纸带上向左或向右一格一格地移动，同时相应地执行操作指令——我们的眼睛和拨算盘珠的手指就可以起读写头的作用，也是向左或向右一档一档地扫描和拨珠；图林机有一个控制装置，它对读写头发操作指令，并根据读写头所扫描的纸带方格中的数据决定下一个操作步骤——在做珠算时，我们的大脑就起着这样的作用。手指拨算盘的动作很简单，无非是：(1)在某一档上拨珠或不拨珠（相应地便改变或不改变这一档上原来的数据）；（2）向右或向左（当需要进位时）移动一档；（3）停止。图林机读写头的动作则是：（1）在纸带的某一格中写或不写数据；（2）向右或向左移动一格；（3）停止。我们知道，从理论上讲，人能够执行的算法，珠算盘都能够执行。图林则证明了，人或其他机器能够执行的算法，图林机也都能够执行。这样，他就对计算机在理论上能做或不能做什么提供了精确的回答。