Invariance theorem

The invariance theorem is the foundational result of algorithmic information theory that makes Kolmogorov complexity a well-defined mathematical object. It states that for any two universal Turing machines U and V, the Kolmogorov complexity of any string x measured on U differs from its complexity measured on V by at most a constant c_UV that depends only on the machines, not on x. This means the choice of reference machine affects complexity by a fixed overhead that becomes negligible for long strings.

The theorem is often treated as a technical nicety, but it carries deeper significance. It establishes that Kolmogorov complexity is not merely a property of particular programming languages but a universal measure — the information-theoretic analogue of physical constants that are independent of measurement apparatus. The invariance theorem is what allows algorithmic information theory to make claims about "the" complexity of an object, rather than merely the complexity relative to a chosen formalism.