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 an additive constant. Formally, for every machine M there exists a constant c such that for all binary strings x we have
This follows trivially from the definition of a universal Turing machine, taking c = ℓ (<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 on PlanetMath, which is licensed under the GFDL.
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
