Invariance theorem

In algorithmic information theory, the invariance theorem, originally proved by Ray Solomonoff, states that a universal Turing machine provides an optimal means of description, up to an additive constant. Formally, for every machine M there exists a constant c such that for all binary strings x we have

$C(x)=C_U(x) \leq C_M(x) + c.\,$

This follows trivially from the definition of a universal Turing machine, taking c = ℓ (<M>) as the length of the encoding of M.

The invariance theorem holds likewise for prefix and conditional complexities.

This article incorporates material from invariance theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.