Science Fair Project Encyclopedia
Invariance theorem
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.
Last updated: 05-28-2005 20:14:25
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details