Kolmogorov complexity: a standalone construct

Ray Solomonoff introduced the core idea in 1964 as part of a formal theory of inductive inference, and Andrey Kolmogorov (1965) and Gregory Chaitin (1966) independently arrived at the same measure, which now carries Kolmogorov's name and anchors the field of algorithmic information theory. The Kolmogorov complexity of a string is the length, in bits, of the shortest computer program that prints that string and then halts, so a highly regular string such as a million repetitions of "01" has a short program and low complexity, while a patternless string needs a program about as long as itself and has high complexity. The value is defined relative to a chosen universal computer, but Solomonoff, Kolmogorov, and Chaitin showed that switching to any other universal machine changes it only by a fixed additive constant, so the measure is well defined up to that constant, a result known as the invariance theorem. It is a machine-independent measure of the intrinsic information, or randomness, of an individual object, and unlike Shannon entropy, which describes the average uncertainty of a random source, it assigns a definite descriptive length to a single fixed string. A basic result, treated in depth in Li and Vitányi's standard reference, is that the function is uncomputable: no algorithm can return the exact Kolmogorov complexity of an arbitrary string, so applications rely on computable upper bounds such as the output length of general-purpose compressors.[1][2][3][4]

Unit

A non-negative integer count of bits, the length of the shortest description, defined relative to a fixed universal machine up to an additive constant

Recovery means

Not applicable

Measured by

Not exactly computable; the true value is uncomputable, so in practice it is bounded from above by the compressed size a general-purpose data compressor achieves and by related estimators