Invariance theorem

From Wikipedia, the free encyclopedia

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

.

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 on PlanetMath, which is licensed under the GFDL.