第 6 天 · 熵一路上升，复杂度为什么先升后降？

一句话

物理学家 Sean Carroll 问：熵随时间单调上升，为什么系统的“复杂度”先升后降？Aaronson 在这篇博文里提出“复杂熵”（complextropy）：在计算时间受限时，描述状态所属的典型集合需要的最短程序长度。他猜想它先升后降，并提议用咖啡与牛奶混合的模拟来检验。

论文讲了什么

问题。往咖啡上倒一层牛奶。开始时两层分明，状态简单。最后完全混匀，状态也简单。中间阶段出现卷须和漩涡，看起来最复杂。熵（entropy）从头到尾单调上升，符合热力学第二定律。“复杂度”却先升后降。宇宙也一样：大爆炸后很简单，热寂时也简单，现在有星系和生命。2011 年，Sean Carroll 在 FQXi 的一次时间主题会议上提出这个问题：怎样严格定义这种“复杂度”，并证明它先升后降？

候选 1：Kolmogorov 复杂度。不行。完全混匀的状态没有规律，Kolmogorov 复杂度最高。它度量的是随机性，和熵一起单调上升。

候选 2：精巧度（sophistication）。这个概念源自 Kolmogorov 1970 年代的观察：随机串的 Kolmogorov 复杂度接近最大，却是最无趣的串。Aaronson 采用的定义如下。找一个集合 S，满足：

• x 属于 S。
• 已知 S 后，描述 x 仍需约 log2 |S| 比特，即 K(x|S) ≥ log2|S| - c。这表示 x 是 S 里的“普通成员”。

精巧度是所有这类 S 中 K(S) 的最小值，也就是 x 中“非随机部分”的长度。全 0 串可以取 S = {x}，随机串可以取 S = 全部 n 位串，二者的精巧度都很低。只有“既不简单也不随机”的串精巧度高。

精巧度的缺陷。确定性系统从简单初始状态出发时，时刻 t 的状态可以用“初始状态 + 演化规则 + t”描述。所以它的精巧度不超过 log2 t + c，永远很小。概率性系统在多数情况下也受同样的上界限制。

Aaronson 的提议：复杂熵（complextropy）。他把计算资源限制加进定义，加在 2 个地方：

• 描述 S 的程序必须在 n log n 时间内输出 S 的近似均匀样本。
• 任何能借助 S 的样本、在 n log n 时间内输出 x 的程序，长度至少为 log2|S| - c 比特。

复杂熵是满足条件的最短采样程序的长度。缺少第 1 个限制，“初始状态 + 跑 t 步”的捷径又会被允许，上界退回 log2 t + c。缺少第 2 个限制，复杂熵可能一直上升，不会回落。

猜想与检验。Aaronson 猜想：复杂熵在初始时小，中间大，混匀后又变小。他不知道怎样证明。他建议先做数值实验：在二维黑白像素格上模拟咖啡和牛奶，每一步随机交换一对相邻的异色像素。复杂熵无法计算，就用 gzip 压缩后的文件大小作粗略代理。博文发布时，MIT 本科生 Lauren Ouellette 已经开始和他做这个项目，成果就是第 7 天的论文。

关键概念

Kolmogorov 复杂度（Kolmogorov complexity）

输出某个字符串的最短程序长度，记作 K(x)。有规律的串 K 小，随机串 K 接近串长。它不可计算，实践中常用压缩器的输出大小作上界近似。

精巧度（sophistication）

把 x 的描述拆成“所属集合 S”和“S 中的编号”两部分，取集合部分的最短长度。它只计规律部分，随机细节不计入，所以简单串和随机串的精巧度都低。

复杂熵（complextropy）

Aaronson 提出的度量，等于加了计算时间限制的精巧度。时间限制排除了“从初始状态模拟 t 步”这种耗时捷径，使中间状态的值可以变大。

粗粒化（coarse-graining）

把细节平均掉，只保留宏观结构。例如把像素格分成 4×4 的小块，每块取平均颜色。不粗粒化时，压缩大小主要反映随机噪声。

资源受限 Kolmogorov 复杂度（resource-bounded Kolmogorov complexity）

只允许运行时间不超过给定上限的程序，再取最短长度。确定性系统的状态在这种定义下复杂度会随时间增长，更接近人对“熵”的直觉。

历史位置：为什么值得读

这是一篇博文，不是论文。它没有定理，只有一个定义和一个猜想。它进清单的原因是：它问了一个好问题，并给出了一条可检验的路线。

它站在两条线的交汇点上：

• 物理：Sean Carroll 长期研究时间箭头和复杂结构的起源，著有讨论熵与时间的科普书 From Eternity to Here（2010）。
• 算法信息论：Kolmogorov 复杂度、Koppel 1988 年形式化的精巧度、Kolmogorov 结构函数，以及 Gács、Tromp 和 Vitányi 的算法统计学（algorithmic statistics）。

Aaronson 是计算复杂性理论学者。他的贡献是用“计算资源限制”这个复杂性理论的工具，把两条线接起来。

后续：2014 年，Aaronson、Carroll 和 Ouellette 发表 The Coffee Automaton 论文，用模拟和压缩代理检验了“复杂度先升后降”（第 7 天）。

和清单的关系：第 4–5 天讲“压缩即学习”，第 26 天讲 Kolmogorov 复杂度。本篇把同一套工具用来回答“什么是有趣的结构”。对机器学习的启发是：好模型应该抓住数据的规律部分，不要把随机细节也背下来。精巧度的两部分划分，正是这个要求的形式化。

学前准备

• 了解熵的直观含义和热力学第二定律
• 知道 Kolmogorov 复杂度的定义（可先看第 26 天前半）
• 先看第 5 天的两部分编码，精巧度是它的理论版
• 会用 Python 的 gzip 或 zlib 压缩字节串

在原仓库怎么学

原仓库第 6 天实现了博文提议的咖啡混合模拟，并用 4 种压缩代理测量复杂度。建议按下面的顺序学：

1. 先读 Aaronson 原博文，再打开 README.md 看本天的结构。
2. 读 implementation.py。先看模拟部分 create_initial_grid 和 swap_step，再看测量部分 gzip_complexity、coarse_grained_kc、multiscale_kc、sophistication_proxy。
3. 运行 train_minimal.py。它是模拟的命令行入口，跑完后检查复杂度曲线是否先升后降。
4. 打开 notebook.ipynb，用 visualization.py 画“复杂度驼峰”和熵的单调曲线。数据说明见 data/README.md。
5. 做 exercises/ 里的 5 个练习：gzip 复杂度、咖啡混合、多尺度分析、两部分编码、几种度量的对比。
6. 对照 exercises/solutions/ 检查答案，最后用 CHEATSHEET.md 复习。

建议：练习 2 和 3 是核心。先不做粗粒化，确认 gzip 曲线单调上升；再加上粗粒化，看驼峰是否出现。这一组对照能说明粗粒化为什么必不可少，也能对应博文中复杂熵的直觉。

今天再看

问题仍然开放。Aaronson 的猜想至今没有被严格证明。复杂熵无法计算，研究者仍然用压缩器做代理。

压缩代理在大模型时代更常见了。Jiang 等人 2023 年用 gzip 加最近邻做文本分类，引发了大量讨论。研究者也常用语言模型的压缩率评估数据质量和模型能力。“用压缩后大小衡量信息量”，正是本篇的实用部分。

和大语言模型的联系。精巧度把数据拆成“规律”和“随机细节”。语言模型训练时，参数学到的是规律部分，不可预测的部分留在损失里。损失降到某个值后不再下降，剩下的就是数据本身的不可约熵。2022 年 Chinchilla 论文的规模定律拟合公式里就有这一常数项。从这个角度看，模型参数存的东西接近数据的“精巧度”。

容易卡住的地方

• gzip 输出大小不是 Kolmogorov 复杂度，只是粗略的上界。gzip 至少有 18 字节的固定头尾，查找窗口只有 32 KB。比较时必须用同一压缩器和同样大小的数据。
• 不做粗粒化时，完全混匀的状态压缩后最大，曲线单调上升，看不到“先升后降”。必须先在格子上做局部平均，再压缩。
• 粗粒化的块大小决定结果。块太小时随机噪声主导，块太大时结构被抹掉。建议扫描 2、4、8、16 几个尺度，把曲线画在一起对比。
• 精巧度定义里的常数 c 很容易读晕。先用全 0 串和随机串 2 个极端例子手算一遍，再看一般情况。

延伸阅读

• 原论文：The First Law of Complexodynamics
• 原仓库第 6 天目录：06_Complexodynamics/ —— 代码、笔记本、练习与答案（英文）
• Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton —— 本文猜想的数值检验，即第 7 天
• Algorithmic Statistics —— Gács、Tromp、Vitányi，精巧度的理论基础
• Kolmogorov complexity（维基百科） —— 概念速查

← 返回 30 天目录