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

The invariance theorem holds likewise for prefix and conditional^{} complexities.

Title | invariance theorem |
---|---|

Canonical name | InvarianceTheorem |

Date of creation | 2013-03-22 13:43:54 |

Last modified on | 2013-03-22 13:43:54 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 7 |

Author | rspuzio (6075) |

Entry type | Theorem |

Classification | msc 68Q30 |