柯尔莫哥洛夫复杂度
柯尔莫哥洛夫复杂度（亦称描述复杂度、算法熵）是衡量对象信息量的理论概念，由安德雷·柯尔莫哥洛夫于1963年提出。它定义为能够产生该对象的最短计算机程序（以某种通用编程语言）的长度。这一概念将随机性与不可压缩性联系起来——一个字符串如果无法被任何比它自身更短的程序生成，则被认为是随机的。柯尔莫哥洛夫复杂度在算法信息论、归纳推理和计算复杂性理论中具有基础性意义，但其核心缺陷在于不可计算性：不存在通用算法能在有限步骤内精确计算任意字符串的复杂度。
背景速读
- 柯尔莫哥洛夫复杂度（Kolmogorov complexity）是计算机科学和信息论中的一个核心概念，由苏联数学家安德烈·柯尔莫哥洛夫于 1960 年代提出。它衡量的是一个字符串（如一段文字、一组数据）在最短情况下能被压缩到多小——简单说，一段数据的复杂度等于能生成它的最短计算机程序（通常指图灵机程序）的长度。
- 该理论的核心思想是：如果一个字符串能被一个很短的算法生成（比如"打印 100 万个 1"），那么它的柯尔莫哥洛夫复杂度就很低，说明数据具有规律或模式；如果一个字符串本质上随机（比如抛硬币的结果），任何能生成它的程序都和字符串本身差不多长，复杂度就高。
- 柯尔莫哥洛夫复杂度与信息论中的香农熵有深刻联系，但熵是概率性的（假定数据来自某个概率分布），而柯尔莫哥洛夫复杂度是确定性的，不依赖任何概率假设——它直接从程序长度的角度定义"信息量"。
- 一个重要的定理（柯尔莫哥洛夫不可压缩性定理）指出：大多数字符串都是不可压缩的——它们的复杂度接近其自身长度。这意味着"随机"和"复杂"在本质上是普遍存在的，而可描述的模式才是少数。
- 该概念在算法信息论、机器学习（用于定义奥卡姆剃刀的严格形式）、生物信息学、哲学（随机性与确定性）等多个领域都有深远影响。不过，柯尔莫哥洛夫复杂度本身是不可计算的——没有通用算法能给出任意字符串的精确最短程序长度。