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

5.4　可计算性

现在我们已经对算法是什么有了一个清楚的认识——算法就是图灵机。我们可以通过对图灵机的证明来探究计算的本质。邱奇-图灵论题告诉我们，当我们有任意一种可用的计算设备，且在这个设备上能够有一个有限的、确定的且有效的方法能够解决某个问题，我们就期望能够构建一个图灵机来解决这个问题。该论点反其道而行之更为成立：如果我们能够证明判定一种语言或者计算函数的图灵机不存在，那么我们便认为这个任务在物理上是不可执行的。图灵论文的中心焦点是如何在图灵机可以解决的问题和图灵机不能解决的问题中划分出一条清晰的界限。在本节中，我们将介绍图灵机模型中一个非常重要的结论：这个结论可以用来证明不可判定的语言和不可计算的函数是存在的——在这种情况下，不存在能完成这些工作的图灵机。我们将这些问题称为不可解问题，因为我们认为无论是现在还是将来都不存在可以完成这些工作的图灵机，即没有解决这些问题的算法。

不可解性是问题的一个重要特性。它表明的不是对于这个问题的算法科学家们尚未找到解决方案，而是不可能找到。了解问题的不可解性是很重要的，因为这能让你知道你试图解决的是一个无法解决的问题，这样你就可以避免浪费时间和精力来解决它，转而解决更容易解决的问题。在过去的一个世纪里，很多人都为解决某些问题努力工作，但这些问题在后来都被证明是不可解的。那些不了解图灵理论的人就像在黑暗中工作，他们有可能会浪费大量的精力来完成不可能完成的任务。

背景：希尔伯特计划　20世纪初期，当时杰出的数学家大卫·希尔伯特提出了一个雄心勃勃的计划，这个计划的目的是为了解决逻辑和数学中的一些最基本的问题。他和他的同事挑战了一个难题，对下列三个陈述进行严格证明：

·数学是一致的：不可能同时证明一个陈述和它的反论，就像你不能证明1=2。

·数学是完备的：如果一个数学陈述是真的，那么就可以证明它是真的。 ...