## You are here

Homeinvariance theorem

## Primary tabs

# 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.

Type of Math Object:

Theorem

Major Section:

Reference

Groups audience:

## Mathematics Subject Classification

68Q30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections