一杯咖啡里没被证明的定律

2011 年 9 月，理论计算机科学家斯科特·阿伦森在一场海上会议上听了肖恩·卡罗尔的开幕演讲。会是在游轮上开的，从挪威卑尔根到丹麦哥本哈根，FQXi 组织，主题是时间的本质。卡罗尔演讲时放出一张图：三杯咖啡。第一杯黑白分明，结构简单；第二杯奶和咖啡绞出复杂的卷须，最好看；第三杯均匀的灰色，什么都分辨不出来了。熵从左到右单调上升，但「有趣程度」看起来是中间那杯最高。

这张图后来流传很广。很少有人知道的是，中间那杯不是模拟出来的。卡罗尔自己在博客评论区承认：图片里的混合图案，是他伸手用勺子戳出来的。真实世界里，杯子自己放着不动，奶会慢慢扩散成均匀的灰——单调、无聊、没有卷须。卷须需要搅拌，而搅拌是一种外力。这个彩蛋值得记住，因为它点破了这整件事的微妙之处：我们直觉里那个「先变复杂再变简单」的宇宙，其实也一直在被什么东西搅着。

卡罗尔的问题于是非常干净：热力学第二定律说熵只增不减，可为什么「复杂性」看起来是先增后减？宇宙起点是低熵的粒子汤，终点也是高熵的粒子汤，中间这几百亿年却有星系和大脑。有没有一条「复杂动力学第一定律」，能解释这条驼峰曲线？

阿伦森回去后写了一篇博文，把这个问题做了一次认真的手术。手术对象不是答案，是问题本身。

先把「复杂」这个词治好

问题听起来像哲学，阿伦森的解法是纯技术的：给「复杂」找一个可计算的替身。

第一个候选是柯氏复杂度——描述一个字符串所需的最短程序长度。它不行，原因很直接：一串完全随机的雪花噪声，柯氏复杂度是最大的，但你不会说雪花噪声「复杂」或「有趣」——它没有任何结构。这把尺子量的是「不可压缩性」，而我们要的尺子得对简单的东西和随机的东西都给低分，只对中间那种「有结构但不简单」的东西给高分。

第二个候选叫「复杂性程度」（sophistication），用两部分码把结构和随机分开：先找最短的程序描述一个集合 S，使得目标串 x 属于 S、且 x 在 S 里是典型的随机元素；这个「模型」的长度就是 sophistication。全零串的模型是平凡的，得零分；随机串的模型是「所有等长串」，也得零分；只有真正的结构需要花钱描述。这个概念出自 Koppel 和 Gács、Tromp、Vitányi 等人的工作，方向对了。

但一到动力学系统，这两把尺子一起撞墙。阿伦森指出：对一个确定性系统，t 时刻的状态可以用三样东西描述——初始状态、演化规则、还有 t 这个数字。数字 t 只需要 log(t) 个比特。所以不管系统演化多久，柯氏复杂度也好 sophistication 也好，都涨不过对数——而直觉上，复杂性应该随时间多项式地涨落。墙的根源：描述可以「作弊」，把整个演化历史压缩成一行公式加一个计数器。

阿伦森的补丁是给定义加两道锁。他的「复杂熵」（complextropy）大致是这样定义的：描述集合 S 的那个程序，必须在 n·log(n) 时间内跑完——不许用「初始状态加计数器」这种会随时间越来越慢的偷懒程序；重构端同样要在时限内完成。「初始状态加演化规则加 t」这个描述依然存在，但用它的代价随 t 涨得飞快，被时限一票否决。两道锁一上，对数墙消失了。

于是猜想可以陈述了，也就是标题里那个「第一定律」：复杂熵在初始时刻接近零，在中间时刻很大，在系统到达平衡后又回到接近零。

阿伦森的原话是：「我还不知道怎么证明这个猜想。」这篇博文的贡献不是答案，是把问题磨到了可以被证明或证伪的形状。

评论区吵了十年的一架

博文评论区来了几位重量级人物，吵出一场很有内容墨水的架。

贝内特（Charles Bennett，逻辑深度的提出者）本人在第 110 楼下场，主张另一个候选：逻辑深度——生成一个对象的最短程序需要跑多久。他的直觉：中间态咖啡卷须确实「深」，因为任何想生成它的短程序都得近似模拟整个混合过程；而平衡态可以抄近路直接采样，很浅。

阿伦森的怀疑也说得干脆：「我看不出任何直觉上的理由，深度为什么会在中间时刻变大。」他的论证值得展开：想生成一杯卷须状态的近似，你只需要描述黑白区域的边界（这要花很多比特——所以 sophistication 高），然后在这些区域内部独立采样像素（这很快——所以深度不高）。一个描述可以是「结构上很贵、时间上很便宜」的。深度和 sophistication 量的是两种不同的贵。

这场架 2011 年没有胜负。卡罗尔在第 6、7 楼贡献了粗粒化的思路——在合适的尺度上把图模糊掉再看柯氏复杂度；卢卡·特雷维桑在第 17 楼补了一个漂亮的推广：不要只在一个尺度上看，把所有尺度都算一遍。如果你画一张「尺度×时间×复杂度」的三维图，驼峰会出现在中间尺度、中间时间的位置——尺度太小，你看到的是熵；尺度太大，整杯咖啡缩成一个格子，复杂度恒为零。

十四年后，这个猜想在一个下午被跑出来了

2014 年，阿伦森和卡罗尔跟当时还在 MIT 读本科的劳伦·奥莱特一起发了后续论文（那正是 2011 年博文里提到的「刚跟我开始做一个项目」的学生）：在二维元胞自动机里模拟咖啡混合，定义「表观复杂度」=粗粒化近似状态的柯氏复杂度。论文给了两个结果：非相互作用粒子下，解析证明复杂度永远不会变大；粒子相互作用时，数值证据显示复杂度冲到一个峰值，高度与咖啡杯的水平尺寸同量级。解析证明相互作用情形的驼峰，到今天仍是公开问题。

猜想的核心可以直接用 gzip 复现——柯氏复杂度不可计算，但压缩文件大小是个粗粝的上界，这是这个领域惯用的替身。我跑了一遍：64×64 的格子，上半黑下半白，每步随机挑一对相邻的黑白像素交换，一路交换到完全混合，在九个时间点、五个粗粒化尺度上各量一次 gzip 大小。

原始像素的 gzip 曲线没有驼峰：从 39 字节一路单调涨到 747 字节，而随机噪声图的参考值是 744——三个字节之差。原始柯氏复杂度（哪怕 gzip 版）量的从来是「随机性」，混合到头它就贴住随机噪声的天花板。想要驼峰，就得先粗粒化。

4×4 粗粒化（16×16 的图）的曲线是教科书式的：27 字节起，涨到 179 字节的峰，然后回落到平衡时的 158。小-大-小，驼峰清晰。更妙的是尺度依赖：2×4 块的粗粒化（太细）驼峰浅得几乎看不见，16×16 块（太粗）整条曲线躺平在 36 字节左右。驼峰只活在中间尺度上——特雷维桑 2011 年预言的那张三维图，把切片拿出来就是这个样子。驼峰的顶点出现在混合完成三成左右的位置，远早于平衡。

一杯咖啡、一个下午、一段 gzip 调用，跑出了 2011 年那篇博文设想的全部现象学：熵的尺子只会单调涨，复杂性的尺子得先选对尺度才能看见驼峰。猜想本身还站在那里等一个证明——阿伦森留的这道题，现在轮到拿着更快的压缩器和更大的格子的人接着跑。

信源：Scott Aaronson, The First Law of Complexodynamics（shtetl-optimized 博客，2011-09-23，含评论区 #6/#7 卡罗尔、#17 特雷维桑、#110 贝内特）；Aaronson, Carroll & Ouellette, Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton（arXiv:1405.6903，2014）；本文实验为 64×64 格子、随机相邻异色对交换动力学、gzip -9 压缩、块平均粗粒化，随机参考曲线用同尺寸二值噪声图。