The invariance theorem states that a universal Turing machine provides an optimal means of description, up to a constant. Formally, for every Turing machine there exists a constant such that for all binary strings we have
Here, means the complexity with respect to the universal Turing machine and means the complexity with respect to .
This follows trivially from the definition of a universal Turing machine, taking as the length of the encoding of .
The invariance theorem holds likewise for prefix and conditional complexities.
|Date of creation||2013-03-22 13:43:54|
|Last modified on||2013-03-22 13:43:54|
|Last modified by||rspuzio (6075)|