Kolmogorov Complexity

Origin. Andrey Kolmogorov (1963-1965); independently discovered by Solomonoff (1960) and Chaitin (1966). Kolmogorov's formulation became the standard in Soviet and Russian literature.

Mechanism. The complexity of an object (string, sequence, dataset) is the length of the shortest program that produces it on a universal Turing machine. Simple objects have short programs (regularities are compressible); complex objects require long programs (randomness is incompressible). This provides an absolute, machine-independent measure of information content and complexity.

Procedure. To apply as a thinking tool: estimate the specification complexity — how long a program would be needed to generate the specification from nothing? Then estimate the solution complexity. If solution >> specification, the solution contains arbitrary choices not forced by the problem. Those choices are candidates for simplification. The ratio of actual description length to Kolmogorov complexity measures how well you understand the structure.

Applies to. Design evaluation, overfitting detection, theory evaluation (prefer simpler theories), data compression, randomness testing.

Limitations. Kolmogorov complexity is uncomputable — there is no algorithm to find the shortest program. Only upper bounds are computable (any program that produces the object is an upper bound). The measure is also relative to the universal machine, though invariant up to a constant. Use as a conceptual tool and design heuristic, not as a computational method.