计算机科学导论：跨学科方法

5.5　难解性

在前面的章节中，我们根据是否能被计算机解决来对问题进行了分类。在本节中，我们将重点放在我们可以解决的问题上，特别是如何确定解决这些问题所需要的计算资源。

在本书中我们研究了很多算法，这些算法普遍用于解决实际问题，而且它们消耗的计算资源的数量是合理的。大多数算法带来的实际效益是显而易见的，对于许多问题，我们都有很多高效的算法可以选择。不幸的是，许多在实践中出现的其他问题不能使用这些有效的解决方案。更糟糕的是，对于一大类这样的问题，我们甚至无法判断是否存在有效的解决方案。对于程序员和算法设计人员来说，这种情况是十分令人沮丧的，因为对于很大一部分的实际问题他们找不到适用的有效算法；理论家们也同样沮丧，因为他们也无法找到有效的方法来证明这些问题确实是很难解决的。

人们在这个领域已经做了大量的工作，这导致一个新的机制的发展。这个机制是将新出现的这些问题在特定的技术意义上归类为“难以解决”的问题。虽然这些工作的大部分都超出了本书的范围，但是中心思想是相通的。我们在这里介绍这些工作是因为对于每个程序员来说，当他们面临一个新问题时，他们应该知道这个问题有可能是那些没人知道任何有效算法的问题，自然也无法保证能找到一个有效的解决方案。

在前面两节中，我们研究了下面两个观点，这两个观点源于20世纪30年代艾伦·图灵的开创性工作：

·普遍性。一个图灵机能够执行任何可以用物理存在的计算设备描述的计算（判定语言或者计算函数）。这个想法被称为邱奇-图灵理论。把这个理论推广到自然世界时是不能被证明的（但它有可能是错的）。支持这个理论的证据是，数学家和计算机科学家已经研究出大量的计算模型，但是它们全部被证明与图灵机一致。

·可计算性。无法通过图灵机来解决（根据普遍性，也可以说是通过任何物理存在的计算设备都无法解决）的问题是存在的。这是一个著名的数学事实。著名的停机问题（没有程序可以保证能够确定一个给定的程序是否会停机）就是这样的一个问题。 ...