第 26 天 · 最短程序有多长，信息就有多少

一句话

这本书系统讲解柯氏复杂度：一个对象的信息量等于输出它的最短程序长度。全书从这一个定义出发，推出不变性定理、不可压缩性和不可计算性，并给单个序列的“随机”下了严格定义。

论文讲了什么

这是一本约 500 页的数学教科书，不是论文。全书围绕一个定义展开：字符串 x 的柯氏复杂度 C(x)，是能输出 x 的最短程序的长度。例如，把 “01” 重复 500 次得到一个 1000 位的串。一个很短的循环程序就能生成它，所以它的复杂度很低。抛 1000 次硬币得到的串，通常没有更短的描述，复杂度接近 1000。

前几章建立 4 个基本结论：

• 不变性定理：换一种编程语言，复杂度最多相差一个常数。这个常数只取决于两种语言，与 x 无关。因此 C(x) 主要反映对象本身，而不是某种语言的偏好。
• 大多数串不可压缩：长度小于 n 的程序少于 2^n 个，所以每个长度 n 至少有 1 个串无法压缩。能压缩 k 位以上的串，占全部长度为 n 的串不到 2^(−k)。
• 不可计算：不存在一个算法能对任意 x 输出 C(x)。证明思路类似贝里悖论：“不能用 20 个字以内描述的最小正整数”这句话本身就是一个短描述。我们只能计算上界，例如 gzip 压缩后的长度。
• 信息的对称性：C(x, y) = C(x) + C(y | x) + O(log n)。由此可证，x 含有的关于 y 的信息，与 y 含有的关于 x 的信息近似相等。

接下来几章处理随机性。书中介绍马丁-洛夫随机（Martin-Löf randomness）：一个无限 0/1 序列是随机的，当且仅当它能通过所有可计算的统计检验。Levin 和 Schnorr 证明了一个等价刻画：序列随机，当且仅当它的每个前缀都几乎不可压缩。为了让这个等价严格成立，需要把简单复杂度换成前缀复杂度（prefix complexity）K 或单调复杂度（monotone complexity）。前缀复杂度还和概率直接对应：2^(−K(x)) 近似等于 x 的先验概率，这就是 Solomonoff 的通用先验。

后半部分扩展到 6 个主题：

• 柯氏复杂度与香农熵的关系：对独立同分布的信源，每个符号的平均复杂度趋近于熵。
• 不可压缩性方法：用“大多数串不可压缩”证明组合问题和算法问题的下界。
• 随机性的频率视角和博弈视角。
• 熵、复杂度、集合大小 3 者之间的不等式。
• 共同信息与多源信息论。
• 算法统计：怎样区分数据里的“结构”和“噪声”。

对机器学习读者，最重要的一条连接是：压缩就是建模。模型对数据预测得越准，配合算术编码压缩数据所需的位数就越少。语言模型的交叉熵损失，就是它压缩文本的平均码长。

关键概念

柯氏复杂度（Kolmogorov complexity）

在固定的通用图灵机上，能输出字符串 x 的最短程序长度，本书记作 C(x)。它度量单个对象的信息量，不需要先假设概率分布。

不变性定理（Invariance theorem）

任意两种通用描述方式下，同一个 x 的复杂度之差有一个与 x 无关的常数上界。它让定义不依赖具体语言，但这个常数在短字符串上可能比串本身还长。

前缀复杂度（Prefix complexity）

只允许前缀无关程序（没有一个程序是另一个的前缀）时的最短长度，记作 K(x)。它满足 Kraft 不等式，所以 <code>2^(−K(x))</code> 可以当作概率使用。

马丁-洛夫随机（Martin-Löf randomness）

无限序列通过所有可计算的统计检验时称为随机。等价地，存在常数 c，使它的每个长度为 n 的前缀都满足 <code>K ≥ n − c</code>。

归一化压缩距离（Normalized Compression Distance）

用真实压缩器 Z 近似复杂度：<code>NCD(x,y) = (Z(xy) − min(Z(x),Z(y))) / max(Z(x),Z(y))</code>。两份数据共享的结构越多，距离越接近 0。

不可压缩性方法（Incompressibility method）

一种证明技巧：取一个不可压缩的串作为输入。如果算法在它上面表现很好，就能构造出该串的更短描述，产生矛盾。常用于证明平均情况下界。

历史位置：为什么值得读

柯氏复杂度在 1960 年代由 3 个人独立提出。Solomonoff 在 1964 年从归纳推理出发，想定义“先验概率”。Kolmogorov 在 1965 年从“单个对象含有多少信息”出发。Chaitin 的两篇论文在 1966 年和 1969 年发表，给出了同样的定义。1970 年代，Levin 和 Schnorr 把它与 Martin-Löf 在 1966 年提出的随机性连接起来。

本书作者来自 Kolmogorov 在莫斯科的学派。Uspensky 是 Kolmogorov 的学生，Shen 和 Vereshchagin 是这个学派的下一代。英文版由美国数学会（AMS）在 2017 年出版。与 Li 和 Vitányi 的百科式教材相比，本书选题更少，证明更细。

Ilya 把一本数学书放进清单，是因为他多次表达一个观点：好的预测器就是好的压缩器，所以无监督学习有效。柯氏复杂度给出了“最好的压缩器”的理论极限。2023 年，他在伯克利 Simons 研究所的演讲专门讨论了这个联系。

在清单里，本书是第 4–5 天最小描述长度（MDL）的理论根基，也是第 6–7 天讨论“复杂度”的形式化工具。第 27 天 Legg 的通用智能定义直接用 2^(−K) 给环境加权。先读本篇，再读第 27 天会顺畅很多。

学前准备

• 知道图灵机或“通用编程语言”的含义
• 理解香农熵 H = −Σ p log p 和编码长度的关系
• 能读懂简单的反证法和计数论证
• 先看第 4–5 天的 MDL，体会“描述长度”的含义

在原仓库怎么学

仓库代码只能计算复杂度的上界。书里的定理需要读原书第 1–4 章。

1. README.md：看本日的内容安排和文件清单。
2. setup.py：运行它，检查环境和依赖。
3. implementation.py：读 HuffmanCoder、ArithmeticCoder、ComplexityMetrics 3 个类。前两个是压缩器，第 3 个用压缩长度估算复杂度和 NCD。
4. data/：查看 patterned.txt 和 random_noise.txt 两份样本，一份有规律，一份是噪声。
5. train_minimal.py：运行复杂度诊断扫描，比较两份样本的压缩率。
6. visualization.py：生成复杂度谱图和 NCD 热力图，对照目录里的 complexity_spectrum.png 和 ncd_heatmap.png。
7. notebook.ipynb：在笔记本里逐步运行上面的流程。
8. exercises/：做 5 个练习，依次是 Huffman 树构建、码率与香农熵对比、用 NCD 测相似度、算术编码、不可压缩性实验。答案在 exercises/solutions/。

今天再看

柯氏复杂度不可计算，所以没有人直接用它训练模型。它在 2026 年活在 3 个地方：

• 理论基础：Solomonoff 归纳和第 27 天提到的 AIXI 都建立在它之上。它给“偏好简单解释”提供了严格版本。
• 压缩即智能：DeepMind 2023 年的论文《Language Modeling Is Compression》显示，大语言模型配合算术编码可以压缩图像块和音频，压缩率超过 PNG 和 FLAC。这些模型只在文本上训练过。
• 实用工具：NCD 和“gzip + 近邻”文本分类仍被用作小数据场景的基线。Hutter Prize 用压缩 1 GB 维基百科文本来衡量算法的智能水平。

需要记住一点：语言模型的损失只是复杂度的一个可计算上界。严格的描述长度还要计入模型参数本身，这就是第 4 天 MDL 讨论的“两部分编码”。

容易卡住的地方

• 把 gzip 压缩长度当成 C(x)：压缩长度只是上界，真实复杂度可能小得多。例如圆周率的前 100 万位几乎无法被 gzip 压缩，但一个很短的程序就能生成它。
• 被常数项误导：不变性定理的常数可能有几千位。对很短的字符串比较复杂度没有意义。书中的结论大多是渐近结论，适用于长串。
• 混淆 C 和 K：本书用 C 表示简单复杂度，K 表示前缀复杂度，两者相差 O(log n)。Kolmogorov 本人还用过 H。读其他资料时先确认记号。
• 从第 1 页硬读到最后：全书约 500 页。建议先读开头的“本书讲什么”综述和第 1–4 章，其余章节按兴趣挑读。

延伸阅读

• 原论文：Kolmogorov Complexity and Algorithmic Randomness
• 原仓库第 26 天目录：26_kolmogorov_complexity/ —— 代码、笔记本、练习与答案（英文）
• Clustering by Compression —— Cilibrasi 与 Vitányi：NCD 的原始论文
• Language Modeling Is Compression —— DeepMind 2023：大语言模型作为通用压缩器
• Hutter Prize —— 用压缩维基百科文本衡量智能的比赛

← 返回 30 天目录