Kolmogorov 复杂度与算法随机性：「随机」就是压不短

原文：Kolmogorov Complexity and Algorithmic Randomness · Shen、Uspensky、Vereshchagin · 美国数学学会（AMS）出版 ｜ i 系列 02 / 27 · 板块一：理论地基

论文名片

这是书单里少有的纯数学教材。它的每一个结论都不靠实验，只靠证明——而恰恰是它，给全书单的「压缩」主线打下了最硬的地基。

Ilya 为什么选它

一份以论文为主的书单里突然出现一本教材，值得停下来想一想。它说明在 Ilya 眼里，「压缩」不只是工程技巧或漂亮的比喻，而是一个可以严格定义、严格证明的数学对象；后面各篇用的每一把「描述长度」尺子，源头都在这里。

这本书回答的问题极简单：随便给一串符号——一段数字、一张图片、一条录音——它最短能被压到多短？答案由 Kolmogorov 复杂度（Kolmogorov complexity）给出。而这个答案最惊人的地方在于：那把「最短」的终极尺子，被证明永远造不出来。理论天花板的存在与不可触及，写进了同一本书。

读懂它再看 i01 的 MDL，两者的关系立刻清楚：MDL 是「能落地的近似」，Kolmogorov 复杂度是「不可企及的理想极限」。书单先给能用的，再给极限的，这个顺序本身就是一种治学方法。

从生活说起

乐谱与演奏。乐团排一部交响曲，指挥递过去几十页总谱就够了：纸页虽厚，整部作品却被一份「说明书」完整捕捉，换个乐团照样演。反过来，录一段猫在琴键上乱踩的即兴「曲子」，任何乐谱都帮不上忙——每个音符与其他音符毫无关系，要复现只能逐音照抄。信息的多少，不在于纸的厚薄，而在于能不能找到一份更短的说明书。

九的海洋与硬币的沼泽。让两个孩子各交一份一千个字符的作业：一个写的是 9 重复一千次，他只交了一行字——「9 写一千遍」；另一个掷了一千次硬币记正反面，抄到手酸，而且无论怎么缩写都会丢信息，因为那串正反组合里没有可找的规律。「连写一千个 9」一句话说清，随机记录只能原样搬运。到这里，「随机」第一次有了形状：它就是描述长度被顶到了下限，压无可压。

核心思想拆解

定义：一个对象的最短程序。一个对象（比如某串 0 与 1）的 Kolmogorov 复杂度，等于「能在计算机上输出它、然后停机」的最短程序的长度。注意三个细节。其一，这把尺子量的是对象本身，不迁就任何人的聪明程度——你个人觉得好记没有用，程序说了算。其二，它以某台计算机为基准，换一台机器，数值只差一个固定的小开销，相当于换台计算器要付的「说明书翻译费」，不影响大势。其三，「最短」是硬指标：在所有能生成它的程序里取最短的，没有商量余地。

圆周率与硬币：两种命运。π 的前一百万位小数，复杂度极低：一张纸条写下计算公式，任何人都能照着重算出全部一百万位——描述只需要纸条上的几行字。真随机硬币记录则相反：它的复杂度约等于它自身的长度，因为不存在比照抄更短的生成办法。「随机的本质 = 压不短」——这就是算法随机性（algorithmic randomness）的核心直觉：一串 0 和 1 是不是真随机，就看它有没有比自身更短的描述。

尺子本身造不出来。最惊人的结论来了：不存在一个万能程序，能对任意一串符号算出它的 Kolmogorov 复杂度。用大白话走一遍反证：假如这种「最短描述检测器」存在，我们就能让它找出「第一个无法用一百字以内的程序描述的对象」；可这句话本身恰恰就是它的一百字以内的描述——自我矛盾。矛盾从哪来？只能来自那个假设的检测器。所以它不存在：最短的描述可以定义，却不能系统地计算出来。

理论如何照亮工程。既然终极尺子造不出来，工程上怎么办？用压缩器等可操作的近似去逼近——这正是 i01 的 MDL 的处境：它是「不可计算的最短描述」的现实替身。后面的 i03 把这把尺子架到神经网络的权重上，i04 甚至拿压缩后的文件长度去量一杯咖啡的复杂度。整份书单的「压缩主线」，源头就是这本教材里那些看似抽象的定义与定理。

动手算一算

玩具对比一：那串一千个 9。照抄要写 1000 个字符；写成「9×1000」只要 6 个字符——把这六个字符当作一个小「程序」，交给任何懂乘法的人都能还原出原串。描述长度从 1000 缩到 6，缩了约 166 倍。

玩具对比二：一千次硬币记录。想一字不差地还原，目前只能写满 1000 个字符；任何更短的写法——比如「正反正反」式的规律描述——还原出来的结果都对不上原记录。所以前者复杂度按「程序长度」计，很小；后者只能按自身长度计，接近 1000。要提醒的是：我们没法证明后者绝对压不短（那需要用到不可计算的复杂度本身），只能说：在你我能想到的所有办法里，都找不到更短的写法。

这正是教材与科普的分界线：教材用证明把「找不到更短写法」钉成定理；本页只取直觉。而直觉已经够用——它解释了为什么压缩软件能给文本瘦身（文本有语言规律），却对加密后的数据束手无策（加密后的数据看起来就像随机硬币记录）。

它改变了什么

给 MDL 一个家。i01 里「总描述长度最短」之所以理直气壮，是因为它背后站着「最短描述」的严格理论；工程做法与理论极限各安其位。想回看那个能落地的版本，读 i01 最小描述长度。

给全书单一把尺。「拿压缩长度量复杂度」的思路后来被用得淋漓尽致：Hinton 用它管住神经网络的权重（i03 用描述长度精简神经网络），Aaronson 用它量一杯咖啡先复杂、后简单的弧线（i04 咖啡自动机）。一根理论上「造不出来」的尺子，反而成了全书单最常用的工作比喻——这正是基础理论独特的回报方式。

术语小词典

原文与代码

• 出版社页面（AMS Bookstore）：Kolmogorov Complexity and Algorithmic Randomness · Shen, Uspensky, Vereshchagin
• 代码：理论教材，没有官方代码，也不需要。
• 系列续读：上一篇 i01 最小描述长度；下一篇 i03 用描述长度精简神经网络。