从 Kolmogorov 复杂度到 Martin Löf 随机性检验（上）
Per Martin-Löf, The Definition of Random Sequences, Information and Control, 9, 602-619(1966)
考虑一个在有限字母表中所有字符串的集合。记字符串 $x = \xi_1\xi_2\dots\xi_n$ 的长度 $l(x) = n$。接下来我们需要考虑的问题是，这个序列有多复杂？
很显然，直观地讲，一个“随机”（我们很快会回到这一点上来）字符串要比一个有规律的字符串复杂地多。同样很直观地，我们可以把一个字符串的复杂度定义为某种“最简单的描述方法的长度”，Kolmogorov 算术复杂度就是从这个视角出发做出的形式化定义。
“描述方法”和 Kolmogorov-Solomonoff 定理
接下来我们需要反思，“描述方法”应该如何被形式化地定义出来？既然本文的 tag 中带有计算理论，很自然的一种想法就是，“描述方法”就是一种算法。
在这里，我们使用“算法”这个概念来表达一种从一个有限二进制序列到一个有限字母表上的单子的映射。算法概念的更精确的形式化定义可以采用递归论的定义模式或者其他等价的形式（本文中将不再展开），这并不影响后文的探讨。
记 $A$ 为一种算法，$A(p) = x$，$p$ 为一个有限二进制串，$x$ 为一个有限字母表上的字符串，我们称 $p$ 是在算法 $A$ 下对 $x$ 的描述。接下来，延续我们前面的直观认识，我们可以定义相对于算法 $A$ 字符串 $x$ 的复杂度为：
那么，很自然的一个问题是，是否一定存在这样的二进制串 $p$ 来对任意字符串 $x$ 做出描述？答案是否定的。只要考虑一个平凡的算法 $A_0$，它将任意二进制串 $p$ 都映射到字符串 $x_0$，那么，其他的字符串就都不能在这个算法下做出描述。因此，为了定义的严谨性，我们需要补充说明：
现在，我们剩下的一个问题就是，我们不能摆脱算法 $A$ 对我们的定义的限制。我们在考虑一个序列的复杂度时，很显然不是要考虑一个字符串“在某种描述方法下”的复杂度，我们需要使得它成为一个只与字符串 $x$ 有关的数。为了实现这个定义，就需要引入 Kolmogorov-Solomonoff 定理：
存在一个算法 $A$，使得对于任意算法 $B$，
其中 $c$ 为一常数，且其只与 $A$ 和 $B$ 有关。
这个算法在 Kolmogorov 的著作中被称为渐进最优的（asymptotically optimal），在 Solomonoff 的著作中被称为通用的（universial），上述定理的证明如果我不鸽的话会丢进本文的附录或者其他文章里。总之，现在我们已经有了一个最好的算法来讨论如何描述字符串 $x$，于是，我们就可以定义这个字符串的复杂度 $K(x) = K_A(x)$，称其为 Kolmogorov 复杂度，或者简单地称为复杂度。
同样地，我们可以引入条件复杂度的概念。考虑一个两变量的算法 $A(p, x)$，$x$ 为一个有限字母表上的字符串，若 $A(p, x) = y$，则我们将其称为在 $x$ 的条件下对（可能不同于 $x$ 的）字母表上的字符串 $y$ 的描述。称在 $x$ 的条件下相对于算法 $A$ 的 $y$ 的复杂度为：
这个定义也是很自然的，同样与上面的讨论和我们的直观感受匹配。幸运地是，亲爱的 Kolmogorov 先生同样给出了一个与上面的定理相对应的定理：
存在一个算法 $A$，使得对于任意算法 $B$，
其中 $c$ 为一常数，且其只与 $A$ 和 $B$ 有关。
因此，我们也记 $K(y\vert x) = K_A(y \vert x)$，并称其为在 $x$ 的条件下 $y$ 的条件复杂度。
很直观的，对于任意长度为 $n$ 的二进制串 $x$，都有
其中 $n$ 是用于描述这个字符串所用的最多比特数，在最坏情况下，我们需要将整个串都硬编码到代码当中，那么当然需要 $n$ 的长度。而 $c$ 则是机器相关的常数。
同时，我们可以尝试给出一个下界，满足
的序列一共有 $(1-2^{-c})2^n$ 个。这个结论也很平凡，留给读者自证。
于是，我们发现，当 $n$ 很大的时候，会有很多字符串的复杂度的渐进上界是在 $O(n)$ 这个最大的级别的。Kolmogorov 指出，这可以使我们形式化地定义一个字符串的随机性。
一些评述
看起来，对于二元算法的定义事实上意义不是很大，因为 $n$ 同样可以以 $\log n$ 的复杂度编写到程序之中，这对于我们的结果并没有影响。事实上，很多较现代的论文提供了另外一种定义形式，例如 Peter D. Grünwald and Paul M. B. Vitányi, Algorithmic Information Theory 中给出的定义是：
这种定义形式似乎更加符合我们的预期。另外，也将一个对象的 Kolmogorov 编码定义为 $E*(x)$，是最短的能够打印 $x$ 然后停下的代码。
在这种定义形式下，我们就可以给出三种分类：
简单的对象：$O(\log n)$，其原因已经在前面解释过了，因为 $n$ 需要被硬编码进去
完全偶然对象（completely random objects）：$n + O(\log n)$，也是显然的
随机对象（stochastic objects）：$\alpha n + o(n)$ 如果 $x_i$ 是一个随机变量 $X_i$ 的实现，其分布为 $P$，则这个对象是随机的，其中 $\alpha < 1$。比较常见的例子是二项分布，其 $\alpha = H(p)$ 为二值熵（binary entrophy）
随机对象的情形可以类比于扔一个有缺陷的硬币，硬币的缺陷使得这个序列不再成为完全随机的，当然，很显然，$p = 0.5$ 时， $H(p) = 1$，序列还是完全偶然的。
另一个很遗憾的问题是，$K(x)$ 不是可计算的，在 [Li and Vitányi, 1997] 中，他们表明它是上半可计算的（upper semicomputable），或者简单地理解就是，它是可以被近似的，但近似算法很慢，且不能确定其终点。但是，也有一些方式来解决这个问题，比如通用编码（[Cover and Thomas, 1991]），最小描述长度原理（MDL, [Solomonoff, 1997]）等方式的近似。
Blum 和 Burgin 的公理系统对于这个领域来说也是相当重要的，他们给出了关于这些性质的普遍描述，如果不鸽的话大概也会专门开一篇文章来介绍他们的成果，嗯，如果不鸽的话。