|
|
|
|
|
Invariance TheoremIn 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|