用电子计算机证明数学定理

用电子计算机证明数学定理

计算机对于数学研究的帮助中最明显的是与算盘一样简单。这也是人们最初发明计算机的动因。高速计算机可以出色地完成大量的重复运算，这使得原先那些由于太复杂而难以处理的问题现在都可以由计算机直接给出其数值答案。计算机的这一用途帮助所有的应用数学取得了引人注目的成就。现在，人们认为一个应用数学的问题得到了满意的解答，是指你能找到一种算法，输入计算机后将给出你所要求的所有数值解。

然而并不是所有的数学与数有关，而且与其他自然科学的情形一样，数学中的发现也要经几个阶段才能实现，而形式证明只是其中的最后一步。那么计算机除了能够快速运算之外，还能够进行逻辑判断吗?回答是肯定的。电子计算机逻辑判断这一特征的最引人注目的是在解决“四色问题”中所起的作用。

“四色问题”的起因

四色问题的第一次书面记录出现在1852年10月23日伦敦大学数学教授德·摩根给数学家哈密尔顿的信中。在信中，德·摩根讲述了他的学生弗雷德里克格里斯给他提出的一个问题:“一位学生今天让我说明一个事实的道理，我不知道它是否可以作为一个事实。他说任意划分一个图形并对其每个部分染色，使得任何具有公共边线的部分具有不同的颜色，而且只能用4种颜色，不能再多。下面就是需要用4种颜色染色的情况。

图5－1　A、B、C、D代表4种颜色

没有必要提出使用五种或更多颜色的要求。此刻就我所看，如果4个基本部分中的每一个都和其他部分有一段公共边界，则其中3个包围了第四个使任何第5个部分不能与它相邻。若这是对的，4种颜色就可以对任何地图着色使得除了点之外，相同颜色不相遇。

图5－2

现在看来，画出两两具有公共边界ABC的3个部分，除了包围其中的一个这种方式以外，不可能使得第四个成分跟这3个部分中的每一个都有公共边界。但这是有技巧的工作，我不能确定它的难度。你以为如何?如果这个问题成立，它能引起人们的关注吗?我的学生说从英国地图的染色中可猜测到这一点，我越想越觉得它似乎是显然的。……”

这一问题可以用简单的语言说清楚:每幅地图可以用而且只用4种颜色着色，使得有共同边界的国家着上不同的颜色。

这个看上去非常简单的问题德·莫根和哈密尔顿都没有能够证明。

利用计算机证明“四色问题”

自从四色问题提出100多年来，许多数学家都想证明它，但后来发现他们的证明有漏洞或者完全错了。越来越多的数学家对此绞尽脑汁但都没有彻底解决。于是“四色问题”成为数学史上的一个著名猜想。

1976年，美国伊利诺斯大学的哈肯和阿佩尔郑重宣布，他们证明了著名的四色问题。他们使用的工具就是计算机。通过设计的十分巧妙的程序，用计算机进行复杂的证明，他们在伊利诺斯大学的ZBM360机对所设计的1000多种情况花费了1200多小时机器时间，证明了四色定理。

这个证明本身没有多大的创新，但在它之前人们只知道电子计算机能够计算，至于证明定理则整个的理论还十分幼稚。然而这次却对四色问题这种超级难题进行了证明，进一步说明电子计算机越来越深入地介入数学本身的各个领域。

尽管四色问题用计算机所给出的证明仍然面临着挑战，持怀疑或保留态度的人也大有人在，但计算机用于纯粹数学领域是一股还会增大的潮流。