Kolmogorov Complexity

Kolmogorov complexity (also algorithmic complexity or descriptive complexity) is the length of the shortest program that produces a given object as output. Where Shannon Entropy measures average information across a distribution, Kolmogorov complexity measures the information content of a single object — making it the natural notion of complexity for individual strings, structures, and patterns.

A string of a million zeros has low Kolmogorov complexity (a short loop produces it); a truly random string of the same length has maximal complexity (no compression is possible). The deep result is that Kolmogorov complexity is uncomputable — no algorithm can determine the shortest description of an arbitrary input. This connects it directly to Gödel's incompleteness and the Halting Problem: all three are facets of the same fundamental limitation on what formal systems can know about themselves.

For the study of Emergence and Complex Adaptive Systems, Kolmogorov complexity provides a precise vocabulary for a central puzzle: how systems with short descriptions (simple rules) generate outputs with long descriptions (complex behaviour). The gap between a system's algorithmic depth and its surface complexity is where emergence lives.