# 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()$ as the length of the encoding of $M$.

The invariance theorem holds likewise for prefix and conditional complexities.

Title invariance theorem InvarianceTheorem 2013-03-22 13:43:54 2013-03-22 13:43:54 rspuzio (6075) rspuzio (6075) 7 rspuzio (6075) Theorem msc 68Q30