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 In computer science, algorithmic information theory is a field of study which attempts to define the complexity (aka descriptive complexity, Kolmogorov complexity, Kolmogorov-Chaitin complexity, or algorithmic entropy) of a string as the length of the shortest binary program which outputs that string. ... Ray Solomonoff (born 1926) invented the concept of algorithmic probability around 1960. ... Artists conception of a universal Turing machine. ...
.
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. PlanetMath is a free, collaborative, online mathematics encyclopedia. ...
The formal statement of the theorem derives an expression for the physical quantity (and hence also defines it) that is conserved, from the condition of invariance alone.
For example, the invariance of physical systems with respect to translation (when simply stated, it is just that the laws of physics don't vary with location in space) translates into the law of conservation of linear momentum.
Invariance with respect to rotation gives law of conservation of angular momentum, invariance with respect to time gives the well known law of conservation of energy, et cetera.
Feeds |
Contact