invariance theorem

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

$C_{U}(x)\leq C_{M}(x)+c.$

Here, $C_{U}$ means the complexity with respect to the universal Turing machine and $C_{M}$ means the complexity with respect to $M$ .

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

The invariance theorem holds likewise for prefix and conditional complexities.