invariance theorem

The invariance theorem states that a universal Turing machine provides anoptimal means of description, up to a constant. Formally, for everyTuring machine $M$ there exists a constant $c$ such that forall binary strings $x$ we have

$$C_U(x)\le C_M(x)+c.$$

Here, $C_U$ means the complexity with respect to the universalTuring machine and $C_M$ means the complexity with respect to $M$.

This follows trivially from the definition of a universal Turing machine,taking as the length of the encoding of $M$.

The invariance theorem holds likewise for prefix and conditional complexities.