Kolmogorov Complexity
Source: Ray Solomonoff, 1960; Andrei Kolmogorov, 1965; Gregory Chaitin, 1966
Finding
Kolmogorov complexity defines the complexity of a finite object as the length of the shortest program that produces it on a universal Turing machine. A string is random if its complexity approximately equals its length — it cannot be compressed because it contains no exploitable structure. A string is structured if it can be described by a program shorter than itself. Crucially, Kolmogorov complexity is uncomputable: no algorithm can determine the shortest program for an arbitrary string. This follows from the Halting Problem.
Pattern Mapping
Non-fabrication — The pattern, in this framework, is precisely what can be compressed. Structure is regularity permitting shorter description. Randomness is the absence of structure. The honest response to genuine randomness is to acknowledge no shorter description exists, not to fabricate patterns where there are none.
Honesty — Kolmogorov complexity provides a formal criterion for distinguishing genuine structure from noise. A claim that data contains a pattern is testable: does the pattern allow compression? If not, the “pattern” may be fabrication.
Humility — The uncomputability means even the concept of “shortest description” has inherent limits. We can bound complexity from above (by exhibiting a short program) but never certify from below.
Connections
- Halting Problem — uncomputability of Kolmogorov complexity follows from undecidability (→ Meta-Pattern 06)
- Big-O Notation — both formalize relationships between structure and resource cost
- Topology — both strip inessential detail to reveal core structure (→ Meta-Pattern 16)
- Golden Ratio — Kolmogorov is the formal test for whether a claimed pattern is real
- Disinformation Ecosystems — fabricated patterns fail the compression test
Status
See Li and Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications (3rd ed., 2008). The three independent discoveries are documented. The connection between incompressibility and randomness is a theorem. The mapping is this project’s interpretation.
The mapping to the five properties is this project’s structural interpretation.