Invariance theorem

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

:C(x)=C_U(x) leq C_M(x) + c.

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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Invariance of domain — is a theorem in topology about homeomorphic subsets of Euclidean space R n . It states: :If U is an open subset of R n and f : U rarr; R n is an injective continuous map, then V = f ( U ) is open and f is a homeomorphism between U and V .The… …   Wikipedia

  • Noether's theorem — This article discusses Emmy Noether s first theorem, which derives conserved quantities from symmetries. For her related theorem on infinite dimensional Lie algebras and differential equations, see Noether s second theorem. For her unrelated… …   Wikipedia

  • Coase theorem — In law and economics, the Coase theorem (pronounced /ˈkoʊs/), attributed to Ronald Coase, describes the economic efficiency of an economic allocation or outcome in the presence of externalities. The theorem states that if trade in an externality… …   Wikipedia

  • Spin-statistics theorem — Statistical mechanics Thermodynamics · …   Wikipedia

  • CPT-Theorem — Das CPT Theorem (für engl. charge, parity, time = Ladung, Parität, Zeit) ist ein fundamentales physikalisches Gesetz, das 1955 von Wolfgang Pauli aufgestellt wurde. Es besagt, dass jeder Vorgang, der durch Vertauschen von Materie mit Antimaterie… …   Deutsch Wikipedia

  • Nyquist–Shannon sampling theorem — Fig.1: Hypothetical spectrum of a bandlimited signal as a function of frequency The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular… …   Wikipedia

  • Atiyah–Singer index theorem — In the mathematics of manifolds and differential operators, the Atiyah–Singer index theorem states that for an elliptic differential operator on a compact manifold, the analytical index (closely related to the dimension of the space of solutions) …   Wikipedia

  • Stokes' theorem — For the equation governing viscous drag in fluids, see Stokes law. Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables Implicit differentiatio …   Wikipedia

  • Liouville's theorem (Hamiltonian) — In physics, Liouville s theorem, named after the French mathematician Joseph Liouville, is a key theorem in classical statistical and Hamiltonian mechanics. It asserts that the phase space distribution function is constant along the trajectories… …   Wikipedia

  • Weinberg-Witten theorem — Steven Weinberg and Edward Witten consider the so called emergent theories to be misguided. During the 80 s, preon theories, technicolor and the like were very popular and some people were speculating that gravity might be an emergent phenomena… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”