所罗门诺夫复杂度

1963 年，数学家安德烈·柯尔莫哥洛夫做出了肯定的回答。柯尔莫哥洛夫依靠哥德尔、丘奇和图灵关于计算的概念，定义了一种方法，用于衡量类似 1, 2, 4, 8, 16, 32 和 1, 2, 4, 8, 16, 31 这种数列的复杂度。这种复杂度今天又被称为柯尔莫哥洛夫复杂度，它已成为可计算性理论中的基础概念。

但柯尔莫哥洛夫并不是第一个想到这个复杂度概念的人。所罗门诺夫对此知道得更早，在 1960 年就发表了相关研究的初步报告。所以，把这个概念叫作所罗门诺夫复杂度才更准确！然而，大概是因为所罗门诺夫不巧将他的复杂度与在美国被认为是异端的贝叶斯主义联系在了一起，所以最终还是俄国的柯尔莫哥洛夫的研究结果被广泛阅读和引用。讽刺的是，所罗门诺夫在 2003 年被授予柯尔莫哥洛夫奖，获奖原因正是他发现了柯尔莫哥洛夫复杂度！

因此，从某种意义上来说，本章也是对所罗门诺夫的致敬，我在这里斗胆不沿用被广泛接受的术语，将相关概念称为所罗门诺夫复杂度，而不是柯尔莫哥洛夫复杂度。

粗略地说，所罗门诺夫复杂度就是运行时能生成给定数列的最短源代码的长度。但所有程序员都知道，这段最短源代码的长度取决于采用何种编程语言。用 Java 写的源代码几乎总会比用 Matlab 写的长。所以所罗门诺夫复杂度并没有良好的定义，它依赖于使用的编程语言。如果我们考虑直接用机器语言写成的源代码的话，那么它就依赖于我们考虑的图灵机 ⁴。

万幸的是，这种依赖性并不太大。这是因为，有一些被称为“编译器”的计算机程序可以将用某种语言写成的源代码翻译成机器语言，或者用另一种编程语言写成的代码。写成一个编译器可能要花很长时间，但它的代码长度是有限的，而且关键在于，这个长度不依赖于需要翻译的源代码。

我们详细探讨一下。考虑两台通用图灵机 和 。令 为一个从 到 的编译器，也就是一段运行在机器 上的代码，它可以将机器 上的源代码翻译成可以在机器 上执行的代码。这个编译器源代码 的长度也就独立于需要翻译的任何代码的长度。

现在假设我们有一段在机器 上运行的源代码 ，它会生成一段数列。我们可以通过下面的方法获得一段在机器 上运行后生成同样数列的源代码。我们首先写出编译器 ，然后写出源代码 ，接下来我们让图灵机 执行经编译器 翻译的源代码 。于是图灵机 就会进行源代码 在图灵机 上执行的那些计算。粗略地说，我们可以将这个过程写成 。也就是说，机器 会生成正确的数列 ^[6]。

更厉害的是，这样得到的在图灵机 上运行的源代码并不比图灵机 上的源代码长多少，它的长度就是 的长度加上 的长度。所以，该数列在 上的所罗门诺夫复杂度至多是它在 上的所罗门诺夫复杂度再加上一个独立于数列本身的常数，如果将数列记作 ，写成公式就是 。将同样的论证用在从 到 的编译器上，就能得到不等式 。我们就此得到结论，除去一个加法常数以外，机器 上的所罗门诺夫复杂度与机器 上的复杂度相同。

虽然这些论证看起来很晦涩，但我们只要记住这一点：一个数列的所罗门诺夫复杂度的确不是一个客观的量，虽不中，亦不远矣——特别是当我们考虑那些“合理”的通用图灵机时。无论如何，计算机科学家已经习惯了这一点。而且之后我们会再看到，这种所罗门诺夫复杂度的主观性正是所罗门诺夫妖的概率主观性的来源。就像计算机科学家那样，贝叶斯主义者也已经习惯了这一点。

我们回到数列 1, 2, 4, 8, 16。要搞清楚这个数列最“显然”的下一项到底是 31 还是 32，我们可以研究数列 1, 2, 4, 8, 16, 31 和 1, 2, 4, 8, 16, 32 的所罗门诺夫复杂度。根据奥卡姆剃刀，所罗门诺夫复杂度最小的数列就是最可能的答案。当然，因为所罗门诺夫复杂度有主观成分，所以这个问题的答案也是主观的。然而，所有计算机科学家都会觉得，在所有“合理”⁵ 的编程语言里，接上 32 的第二个数列比第一个“代码更好写”。

实际上，我们的例子对于所罗门诺夫复杂度的直接应用来说还是太简单了。这是因为，在这种情况下，在很多编程语言中生成这个数列的最简洁的方式就是将它一项一项直接写出来。在考虑长得多的数列时，所罗门诺夫复杂度才会变得更重要。

一般来说，如果我们现在考虑的是 2 的前 100 个次方而不是前 5 个次方的话，这时写出整个数列的每一项就变成了繁重的任务。对于所有“合理”的编程语言来说，程序员都可以做得更好，写出一个小程序来逐次计算这些 2 的次方。在这种情况下，这个数列的所罗门诺夫复杂度就显然比数列的长度小，无论用什么编程语言，只要这个编程语言是“合理”的即可。所以，我们可以合理地说这个数列的第 项非常可能是 。