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.

The Uncomputability and Its Implications

The uncomputability of Kolmogorov complexity is not merely a technical inconvenience — it is a foundational fact about the limits of formal reasoning. To compute K(x), the Kolmogorov complexity of string x, one would need to solve the Halting Problem: determine whether each candidate program halts and produces x. Since no algorithm can decide halting in general, no algorithm can compute K(x) in general. This means that the most fundamental measure of information complexity is inaccessible to the systems whose complexity it measures.

This has a precise epistemic consequence: no sufficiently powerful formal system can prove its own information-theoretic complexity. A theory of nature that included its own complexity as a derivable theorem would be a theory that computed its own Kolmogorov complexity — which is impossible. The universe, if it is a formal system, cannot contain a complete description of its own information content. This is a generalization of Gödel's incompleteness from arithmetic to computation.

Universality and Invariance

The definition of Kolmogorov complexity appears to depend on the choice of programming language or universal Turing machine — different machines may assign different shortest programs to the same string. This apparent arbitrariness is resolved by the invariance theorem: for any two universal Turing machines U₁ and U₂, the Kolmogorov complexities they assign to any string x differ by at most a constant C that depends only on the pair of machines, not on x. For long strings, this constant is negligible. This means that Kolmogorov complexity is a machine-independent measure — it captures something objective about the string, not something about the measuring apparatus.

The universality result is deep: it means that any universal computer is, in the limit, an equally valid complexity measure. The choice of computational substrate does not affect the fundamental complexity relationships. This is a form of substrate independence that appears nowhere else in information theory and suggests that algorithmic complexity is tracking something more fundamental than mere syntactic length.

Minimum Description Length and Scientific Inference

The Minimum Description Length (MDL) principle, developed by Jorma Rissanen, applies Kolmogorov complexity to scientific inference: the best theory of a dataset is the one that, together with the data it describes, yields the shortest total description. MDL operationalizes Occam's Razor in information-theoretic terms — simpler theories are preferred not because of an aesthetic preference for simplicity, but because shorter descriptions carry less risk of encoding noise as signal.

MDL connects to Bayesian model selection at a fundamental level: the Kolmogorov complexity of a hypothesis is approximately proportional to the negative log of its prior probability under a universal Bayesian prior. The 'simplicity' that MDL and Bayes both favor is not arbitrary — it is the simplicity of short algorithmic descriptions, which correspond to deep structural regularities rather than surface coincidences.

The implication for philosophy of science is uncomfortable: the criterion of scientific theory choice has an objective information-theoretic grounding, but that grounding is uncomputable. We can approximate MDL in practice (and this is what compressor-based machine learning effectively does), but no algorithm can apply the criterion exactly. Science is playing an approximation game to an uncomputable optimum.

Kolmogorov Complexity and Randomness

The most philosophically significant application of Kolmogorov complexity is to the definition of randomness. A string is algorithmically random (or Martin-Löf random) if its Kolmogorov complexity is approximately equal to its length — if there is no substantially shorter program that produces it. This gives a precise definition of randomness for individual objects, something that classical probability theory cannot do (classical probability assigns the same probability to every specific outcome of a fair coin sequence, including the all-heads sequence, which is not intuitively random).

The Kolmogorov-Martin-Löf definition reveals that most strings are random — almost all binary strings of length n have complexity close to n. Random strings are, in a sense, the default case; structured strings with short descriptions are the exceptional ones. The universe of compressible patterns is measure-zero in the space of all possible strings. If physical reality is a string, and if the regularities we call 'laws of nature' are its short description, then the existence of laws is not the default — it requires explanation.

Whether the simplicity of physical law is a anthropic selection effect (complex laws cannot sustain observers to notice them), a fact about the computational cost of dynamic systems (simple update rules can produce complex behavior without requiring complex descriptions), or a genuine deep feature of the universe's structure is one of the most open questions at the intersection of physics of computation and cosmology.

The question is not whether Kolmogorov complexity is the right tool for understanding nature. It manifestly is — it provides the only objective measure of pattern and structure that does not depend on an arbitrary prior choice. The question is what we do with the answer, given that the answer is in principle inaccessible to the very systems asking the question.