柯尔莫哥洛夫复杂性

概述

柯尔莫哥洛夫复杂性 K(x) 是产生字符串 x 的最短程序长度（以 bit 计），度量了单个对象的内在信息含量，是算法信息论的核心概念。

关键内容

定义

K(x) = min{|p| : U(p) = x}

其中 U 是一台固定的通用图灵机，|p| 是程序 p 的长度。

直觉

一个字符串的柯尔莫哥洛夫复杂性等于"描述它所需的最短程序"的长度。 - "000...0"（1000 个 0）的 K(x) 很小——只需一行代码 print("0" * 1000) - 真正的随机字符串的 K(x) ≈ |x|——没有比直接存储更短的描述

与 Solomonoff 先验的关系

$$K(x) \leq -\log_2 M(x) \leq K(x) + O(\log K(x))$$

算法概率的负对数近似等于柯尔莫哥洛夫复杂性。一个字符串的先验概率主要由能产生它的最短程序决定。

不可计算性

K(x) 是不可计算的——不存在算法能在有限时间内精确计算任意字符串的柯尔莫哥洛夫复杂性。这与停机问题密切相关。

发现历史

• Solomonoff (1960)：第一个提出程序长度作为复杂性度量（技术报告）
• Kolmogorov (1965)：独立发现，给出了严格的数学处理
• Chaitin (1966)：独立发现，引入了 Ω 常数

尽管 Solomonoff 最早提出，但这一概念以 Kolmogorov 命名，因为 Kolmogorov 是 20 世纪最伟大的数学家之一，名声远超 Solomonoff。

应用

• MDL 原理：最小描述长度是 K(x) 的可计算近似
• 算法随机性：如果 K(x) ≈ |x|，则 x 是算法随机的
• 机器学习正则化：模型复杂度惩罚项可以理解为对 K(模型) 的近似

来源

• raw/books/信息论/08_solomonoff_1964_formal_theory_of_inductive_inference.md — Solomonoff (1964) 深度解析
• raw/books/信息论/09_kolmogorov_1965_three_approaches_to_information.md — Kolmogorov (1965) 深度解析

相关

• 雷·所罗门诺夫 — 最早提出者
• 算法信息论 — 所属学科
• Solomonoff先验 -M(x) 的负对数近似等于 K(x)
• 信息论 — 相关学科