柯莫哥洛夫复杂度

考虑两个字符串：

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
```

EJHKQZXMPWLVTFBNRSOGDYUICAEJHKQZXMPWLVTFBNRSOGDYUI
```

第一个字符串只是一串 A。你可以用一句话描述它："一串 A"，或者写一段极短的程序：print('A' * 50)。第二个字符串看起来是随机的，描述它的唯一方法似乎是把它原样写出来。

但这里就藏着这套理论最微妙的陷阱："看起来随机"不等于"真的随机"。仔细看第二个字符串，它其实是 26 个英文字母的一个固定乱序排列循环重复——只要给出那个排列，就能用一行短程序生成它。它的柯莫哥洛夫复杂度其实很低。能否判断一个字符串"有没有短描述"，远比肉眼看上去困难——事实上，正如后文将证明的，这个判断在一般情况下根本无法用算法完成。

这个简单的观察——有些字符串有比自身更短的描述，有些则没有——是柯莫哥洛夫复杂度（Kolmogorov Complexity）的核心直觉，也是整个算法信息论（Algorithmic Information Theory）的出发点。

1960 年代，苏联数学家安德烈·柯莫哥洛夫（Andrei Kolmogorov）、美国数学家雷·所罗门诺夫（Ray Solomonoff）和格雷格里·蔡廷（Gregory Chaitin）独立地发展了这套理论。它为"什么是随机性"给出了有史以来最精确的数学定义。

破除误解：柯莫哥洛夫复杂度不是"描述的难度"#

在日常语言中，"这个字符串很复杂"可能意味着"我看不懂它"或"它很难记"。柯莫哥洛夫复杂度是精确的数学量，与人的理解无关。

$C(x)$ 的定义是：能够输出字符串 $x$ 的最短程序（在某个固定的通用图灵机上运行）的长度，以比特为单位。

这里有两个关键词： - 程序：是在某个编程语言/图灵机上运行的指令序列，不是自然语言描述 - 最短：我们要的是最优的压缩，即最简洁的描述

现场：三位独立的发现者#

所罗门诺夫（Ray Solomonoff）的动机是哲学性的：他想用数学形式化归纳推理（inductive inference）——如何从观察到的数据中做出最优的未来预测。他在 1960 年（正式发表于 1964 年）提出了"算法概率"（algorithmic probability）：一个字符串的先验概率与其最短程序长度的负指数成正比。

柯莫哥洛夫（Andrei Kolmogorov）的动机是数学的：他对概率论和随机性的数学基础不满意——经典概率论把"随机序列"定义为满足频率收敛性的序列，但直觉上，一个具体的字符串说"是随机的"或"不是随机的"应该是可判断的。他在 1965 年定义了算法复杂度。

蔡廷（Gregory Chaitin）的动机最为激进：他想把哥德尔不完备定理与信息论联系起来，说明数学本身存在根本性的随机性和不可知性。他在 1966 年独立发展了类似的理论，并后来发现了 $\Omega$ 数（见下文）。

三人的定义从技术细节上略有不同，但被证明在加减一个常数的意义上是等价的——这种等价性是柯莫哥洛夫复杂度最重要的性质之一。

形式定义#

固定一个通用图灵机 $U$。字符串 $x$ 的柯莫哥洛夫复杂度定义为：

$$C(x) = \min\{|p| : U(p) = x\}$$

即，输出 $x$ 的所有程序 $p$ 中，最短程序的长度（以比特计）。

不变性定理（Invariance Theorem）：对于任意两个通用图灵机 $U_1$ 和 $U_2$，存在常数 $c$（仅依赖于 $U_1$ 和 $U_2$，不依赖于 $x$），使得：

$$|C_{U_1}(x) - C_{U_2}(x)| \leq c$$

这意味着：复杂度的定义（在加减常数的意义下）与选择哪台通用图灵机无关。这个常数项等于"把一台通用图灵机模拟到另一台的程序"的长度，是固定的开销，随 $x$ 的增长可以忽略。

不变性定理是柯莫哥洛夫复杂度"客观性"的保证：它不依赖于用哪种编程语言、哪台计算机，在渐近意义上是通用的定义。

随机性的精确定义#

传统的概率论随机性是统计的（统计检验、频率收敛），是针对分布的，而不是针对单个字符串的。柯莫哥洛夫复杂度给出了针对单个字符串的随机性定义：

定义：字符串 $x$（长度为 $n$）是柯莫哥洛夫随机的（Kolmogorov random），如果 $C(x) \geq n$（即，没有比 $x$ 本身更短的描述）。

实际上，考虑到程序本身需要几个比特的开销，常用的定义是 $C(x) \geq n - c$（其中 $c$ 是一个小常数）。

大多数字符串是随机的。对于长度为 $n$ 的字符串，共有 $2^n$ 个，而长度小于 $n - c$ 的程序只有 $2^{n-c}$ 个，因此可以被这些程序描述（即"不随机"）的字符串不超过 $2^{n-c}$ 个——仅占全体的 $2^{-c}$ 分之一。绝大多数字符串无法被压缩。

这与信息压缩的实际限制相符：无损压缩算法（如 ZIP、PNG）不可能对所有文件都产生更小的输出——如果它能压缩某些文件，就必然让另一些文件变大。

柯莫哥洛夫复杂度的性质#

加法对称性： $$C(x, y) = C(x) + C(y|x) + O(\log n)$$ 给定 $x$ 后描述 $y$ 的复杂度，加上描述 $x$ 的复杂度，约等于联合描述 $(x, y)$ 的复杂度。这与香农信息论中的条件熵公式 $H(X, Y) = H(X) + H(Y|X)$ 形式完全对应——但这里针对的是单个字符串，而非概率分布。

与香农熵的关系：对于均匀随机字符串，柯莫哥洛夫复杂度的期望值与香农熵相等（到常数项）。但柯莫哥洛夫复杂度适用于任何单个字符串，而香农熵只是对整个概率分布而言的。

不可计算性：$C(x)$ 是不可计算的。不存在算法能对任意输入 $x$ 计算 $C(x)$ 的精确值。

证明：假设 $C$ 可计算，考虑"能够输出一个复杂度大于 $k$ 的字符串的最短程序"——这个程序的长度约为 $\log k$ 比特（表示 $k$ 所需的位数）。但对足够大的 $k$，$\log k < k$，这意味着我们用一个长为 $\log k$ 的程序描述了一个"复杂度大于 $k$"的字符串——矛盾。这是贝里悖论（Berry Paradox，"最小无法用 13 个词描述的正整数"）的算法版本。

蔡廷的 Omega 数：最随机的实数#

格雷格里·蔡廷（Gregory Chaitin）的 $\Omega$（Omega）数是算法信息论最令人惊奇的对象之一：

定义：$\Omega$ 是一台通用图灵机在随机输入下停机的概率： $$\Omega = \sum_{p: U(p)\text{ 停机}} 2^{-|p|}$$

$\Omega$ 的性质： - 它是一个定义明确的实数，其值在 0 和 1 之间。 - 它的二进制展开中每一位都是数学上完全确定的——但这每一位都编码了关于图灵机停机问题的信息。 - 它是一个"最大随机"的实数：$\Omega$ 的前 $n$ 位的柯莫哥洛夫复杂度至少为 $n - c$（即，无法被压缩）。 - $\Omega$ 的精确值无法被任何算法计算到任意精度——尽管它被完全精确地定义了。

蔡廷把 $\Omega$ 解读为数学真理的"极限"：存在一个完全确定的数学常数，其任意精度的值超出了所有数学证明系统的能力。这是哥德尔不完备定理的算法信息论版本。

应用：压缩、学习与奥卡姆剃刀#

数据压缩：ZIP、gzip、LZW 等无损压缩算法，本质上是在寻找输入数据的短描述。柯莫哥洛夫复杂度是所有压缩算法的理论上限——没有算法能产生比 $C(x)$ 更短的描述。

机器学习与奥卡姆剃刀：机器学习中的"简单模型优于复杂模型"（正则化、奥卡姆剃刀原则）有一个算法信息论的解释：最优模型应该是能以最短描述（最低柯莫哥洛夫复杂度）解释训练数据的模型。所罗门诺夫归纳推理理论从这个角度给出了贝叶斯推理的算法基础。

相似度度量：基于压缩的相似度度量（如"归一化压缩距离"，NCD）用压缩率来衡量两段数据的相似程度：$NCD(x, y) = \frac{C(xy) - \min(C(x), C(y))}{\max(C(x), C(y))}$。这种方法不需要任何领域知识，在文本、音乐、基因序列的聚类分析中都有应用。

代价与哲学含义#

不可计算性的限制：$C(x)$ 不可计算，意味着所有基于柯莫哥洛夫复杂度的"理论最优"方案都无法被精确实现——压缩算法、最优预测等，都只能是近似。

哥德尔的影子：蔡廷的 $\Omega$ 数揭示了数学的内在随机性：并不是所有数学真理都可以被证明，不是所有定义明确的数都可以被计算。这把柯莫哥洛夫复杂度从纯粹的计算工具，提升为关于数学和知识本质的哲学陈述。

跨域连接#

• 信息论：香农熵衡量一个分布，柯氏复杂度衡量一个具体对象。两者在期望意义下对应，却不能互换使用：对一段已拿到手的字符串谈"它的熵"是范畴错误，对一个分布谈"它不可压缩"同样无意义。压缩极限的两种说法由此分工明确，一种管信源，一种管个体。
• 概率论：经典概率把随机性定义在序列族上，答不了"这一串是不是随机的"。不可压缩性给出了单个对象的随机性定义，并顺带解释了为何几乎所有串都随机：短程序的个数随所省比特数指数下降，能被短描述覆盖的对象只占全体的极小一部分，"有规律"才是稀缺的。
• 贝叶斯推断：把先验取成描述长度的负指数，奥卡姆剃刀就从审美偏好变成一条可写下的先验分布，简单假设自动获得更高的先验权重。代价是这个先验不可计算——最优归纳有定义却无法执行，实际用的正则化项只是它的粗糙替身。
• 机器学习概览：模型选择的准则可以统一读成"描述模型加描述残差的总长度最短"。这解释了惩罚项为何不是随手加的：参数越多，写下模型本身越贵，只有当它换来更短的残差编码时才值得。过拟合在这套语言里就是"模型长得比它省下的还多"。
• 哥德尔不完备定理：任何形式系统能证明的"某串复杂度大于某个门槛"只有有限多条，因为系统自身有一个固定的描述长度。不完备性在这里变成一份可量化的额度：证明能力的上限被系统本身的信息量卡死，想证更多，就得先往公理里塞进更多信息。

参考文献#

• Kolmogorov, A. N. Three Approaches to the Quantitative Definition of Information. Problems of Information Transmission 1(1) (1965): 1–7. （原始论文）
• Chaitin, G. J. Algorithmic Information Theory. Cambridge University Press (1987). （蔡廷对该理论的系统阐述）
• Li, M. & Vitányi, P. An Introduction to Kolmogorov Complexity and Its Applications. 3rd ed. Springer (2008). （最权威的教材）
• Solomonoff, R. J. A Formal Theory of Inductive Inference. Information and Control 7(1–2) (1964). （所罗门诺夫的归纳推理理论）