所罗门诺夫归纳法的不可计算性

因此，在这种狂热面前，你可能会提出一个疑问：那所罗门诺夫归纳法岂不终结了对知识哲学的探求？在我看来，大体来说的确如此。但所罗门诺夫归纳法有一个巨大的缺陷，促使我不得不写出本书剩余的内容。实际上，所罗门诺夫归纳法太复杂，难以实际应用。这不仅是我们自身或者我们认知能力有限的问题——你可能还记得，即使是埃尔德什，他也奋斗了一番才理解了贝叶斯公式的一个简单情况——对于计算机也是如此。

所罗门诺夫归纳法是不可计算的。这是什么意思？这就是说，不存在任何图灵机可以严格地执行这种计算。这个事实有个非常简单的原因，但那无关紧要，而另一个原因却更微妙、更无可挽回。

简单的原因是，要严格执行所罗门诺夫的计算，就必须同时考虑无限个预测性理论，这是出于算法有无穷个这一单纯的原因。然而，没有任何计算机或者计算机网络能进行这种无限长的计算。

话虽如此，我们可以这样回应：根据先验概率的构造，过于复杂的理论对应的概率无论如何都会呈指数递减，因此可以被忽略。如果我们忽略这些理论的话，因为我们知道它们对所罗门诺夫归纳法的预测结果影响有限，那么不就可以做出所罗门诺夫归纳法的一个非常好的近似了吗？不幸的是，这也不行。

所罗门诺夫归纳法真正的难点并不是需要考虑的理论的数目，而是这些理论所需的计算。今天，在计算机上运行的算法一般很快、很流畅，这是因为软件工程师在算法上面花了心思！但一般来说，我们其实很难得知某个算法会不会很快结束，而想要知道它的计算会终止，还是会越来越复杂，永不休止，这也同样困难。

这种算法最惊人的例子之一就是锡拉丘兹猜想，它也叫作科拉茨猜想、乌拉姆猜想、捷克猜想或 猜想。我们向这个算法输入一个正整数。如果这个整数是 1，那么算法就停止；如果它是偶数，那么算法就将它除以 2；如果它是奇数，那么算法就将它乘以 3 再加 1。然后，算法会在得到的结果上重复同一套运算。锡拉丘兹猜想的问题是：无论输入什么正整数，这个算法是否最终都会停止 ^[9] ？

看起来无比奇怪的是，我们还不知道这个叙述非常简单的问题的答案，连怎么尝试解决这个问题，甚至连解法是否存在都不知道。大数学家埃尔德什·帕尔这样说：“数学还没有准备好回答这样的问题。”

这可能就是图灵发现的不可计算性的一个例子。在利用图灵机定义计算的概念之后，图灵立即提出了这样的问题：我们能不能在运行某项计算之前就预计到它是否会停止？换句话说，我们能不能构造一台图灵机，它能够在有限的时间内预测出其他图灵机是否会在有限的时间内停止？

你可能觉得图灵的这个问题有点像咬着自己尾巴的蛇，这并不是偶然。在康托尔的对角线法、罗素悖论以及哥德尔不完备性定理的启发下，图灵通过自指论证证明了这些问题的答案都是否定的。我们无法在所有情况下预计计算是否会停止，因此我们说停机问题是不可计算（或者不可判定）的 ^[10]。

而这对于所罗门诺夫归纳法来说是个大问题。这是因为，要进行所罗门诺夫归纳法，就必须计算不同理论 的预测结果 。在理想情况下，我们应该考虑所有对应的计算会终止的结果。然而，如果我们相信丘奇–图灵论题的话，我们就不可能在物理上断定这些计算是否会终止。所以，这个论证的一个惊人结论就是，经过有限的计算时间之后，不可能排除某些预测性理论的计算仍未终止但终将停止的可能性。

更糟糕的是，我们同样不可能预计这些理论之后可能得出的预测是否会大大改变此前的结果，所以，一般来说我们在有限的计算时间内无法衡量当前结果的有效性。所罗门诺夫归纳法不仅不可计算，而且它的所有近似都不可计算！