不可解问题

这两天看到一篇算法方面的文章，提到了不可解问题。于是我自己也想了一下。我能想到的不可解问题只有一类（不知道是否还有其它类型的不可解问题？）：是由无限引起的不可解。

比如这个问题“打印出所有的整数”就是一个不可解问题，因为整数是无限的，无论哪种算法都无法将其全部列出。图灵提出的The Halting Problem也是这样一种情况，由于它是一段可能被无限次递归调用的代码，因此无法判断其运行结果。

有一类问题是暂时不可解的，不可解是因为它没有被现有公理所覆盖到。这类问题一旦被发现，人们就会补全公理体系，问题就解决了。比如说哥德巴赫猜想就有可能是这样一个问题。哥德巴赫猜想还没有被证明，所以现在不能确定它是否可解，不过也许有一天人们会发现从现有所有的数学公理都无法证明这个题目，它本身可能就会变成一条公理，被加入到数学体系里去了。