在发现巨大素数、解阿基米德牛群问题、破译密码、证明四色地图定理以及发现新图形等问题上，计算机证明对数学家是有用的。然而在计算机能做些什么问题上，却还有难以捉摸的限制。

自20世纪30年代起，数学就面临着一场革命，如同物理学的两次革命——广义相对论与量子力学——一样重要，这两次革命动摇了物理学的基础，并且推翻了关于空间、时间与因果律的经典理论。数学的前景展望也由于美国纽约大学的莫里斯·克林提出了“必然的损失”的说法而完全改观。一种崭新的工作已不再注重于数学计算的能力，而是注重于计算的限制。有意义的计算问题被规定为原理上不能解的，或在原理上能解而实际上无法解的问题。

一个从原理上不能解的有意义的典型问题就是“停机问题”，它是艾伦·马西森·图灵于1936年提出的。图灵想到了计算机程序是否迟早会提供结果和停机的问题。停机问题已不仅是纸上谈兵的理论家所关心的问题，而且是很容易在实践中出现的问题。

美国麻省理工学院计算机科学理论学家迈克尔·锡普塞说道：“你可以想象，当你把程序编入卡片，然后提交给计算机中心时，尤其是在这几天里，你是多么想知道答案。他们总是整夜地进行运算，第二天就送回给你。比方说，你有一笔100美元的钱存在机内。有时，计算机程序会有一个无限的循环，而且会耗掉许多钱。由于它会陷入无限的循环，因此你从程序上得不到任何东西。不论是你帐上的钱都已耗费完，还是计算机以何种方式注意到机器运行了很长时间，计算机自己停了机。

“那么，你一定会想，为什么事先不检验程序，如果其中有无限循环，就不应该用它运算”。然而令人惊奇的是，这种自然的概念不能够实现，因为图灵证明了，没有一种检验方法能够适用于所有程序。

除了图灵所证明的停机问题是不可解的之外，1936年数学家向绝对数学知识的虚幻目标发动了另一次进攻。逻辑学家阿朗索·丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的。至于你所给的每一种可能想到的算术语句，计算机也是不能确定其真值的。的确如此，要求找出算术的真值是没有诀窍的。

近几年来，数学界的注意力已从理论上不能解的问题转向理论上能够解而实际上不能解的问题上。在这些问题中，最著名的就是美国国际商业机器公司（IBM）的拉里·斯托克迈耶称之为“内在困难”的问题，即委婉法问题，如果这也算是一个问题的话。他请你构想一部想象中的最大功率的计算机。这部想象的计算机，可以大到充满整个宇宙（直径也许为1，000亿光年）。它将由质子大小（直径为10-13厘米）的硬件构成，信号将以光速（每秒3×1010厘米）在硬件中疾驰通过。它可以就某个问题工作200亿年，它超过了宇宙的估计年龄。这个难题具有一个令人不知所措的特点，即它在原则上能够解决，但即使用可想象出的最大功率的计算机，按宇宙年龄再工作上千百万年也无法解决。

这类问题之一是下棋问题，它在棋盘不是普通的8×8，而是n×n（这里n表示任意大的数目），而且还有不限数量的棋子（但每方只能有一个王棋）。我们想有一种计算机程序，不论棋下到哪一步，不管我们是哪一方，比如说白子，它都可以用来确定是否能够赢。某种程序只在理论上可行而在实际中行不通，它需要考虑所有白方可能走的棋步，随后考虑所有黑方可能回应的棋步，还要考虑所有白方可能反回应的棋步，以此类推，考虑所有可能继续的棋步，直到结束时为止。

这种穷举搜索程序的缺点是速度太慢：有那么多可能继续的棋步，甚至理想的计算机也不可能在200亿年的时间内把所有棋步都考虑进去。1981年，美国耶鲁大学的戴维·利希滕斯坦和以色列的数学家艾维兹里·弗伦克尔证明了对于足够大的棋盘也没有更快的程序。换句话说，耗时的穷举搜索程序没有简捷的方法。这种下棋问题，即使我们知道已有解法，也总是会使计算机的分析落空。

下面4章，我们将从理论和实践两个方面考虑计算机的能力与局限性。