invariance theorem

The invariance theorem states that a universal Turing machineMathworldPlanetmathPlanetmath provides an optimal means of description, up to a constant. Formally, for every Turing machineMathworldPlanetmath M there exists a constant c such that for all binary strings x we have


Here, CU means the complexity with respect to the universal Turing machine and CM 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 conditionalMathworldPlanetmathPlanetmath 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