|
In algorithmic information theory, the invariance theorem, originally proved by Ray Solomonoff, states that a universal Turing machine provides an optimal means of description, up to a constant. Formally, for every machine M there exists a constant c such that for all binary strings x we have
- <math>C(x)=C_U(x) \leq C_M(x) + c<math>.
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.
This article incorporates material from invariance theorem (http://planetmath.org/?op=getobj&from=objects&id=4420) on PlanetMath, which is licensed under the GFDL.
|
