|
|
|
|
invariance theorem
|
(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.
|
"invariance theorem" is owned by rspuzio. [ full author list (3) | owner history (2) ]
|
|
(view preamble | get metadata)
Cross-references: conditional, prefix, length, strings, binary, Turing machine, universal Turing machine, states
There are 2 references to this entry.
This is version 4 of invariance theorem, born on 2003-07-04, modified 2006-11-07.
Object id is 4420, canonical name is InvarianceTheorem.
Accessed 2859 times total.
Classification:
| AMS MSC: | 68Q30 (Computer science :: Theory of computing :: Algorithmic information theory ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
