Teorema de la invariancia (teoría de la información)

Teorema de la invariancia (teoría de la información)

En la teoría algorítmica de la información, el teorema de invariancia, inicialmente probado por Ray Solomonoff, establece que una máquina universal de Turing proporciona un medio óptimo de la descripción, salvo una constante aditiva. Formalmente, para cada máquina M existe una constante c tal que para todas las cadenas binarias x se tiene

C (x) = C_U (x)\leq C_M (x)+c\,

Esto se deduce trivialmente de la definición de una máquina universal de Turing, siendo c = ℓ (<M>) la longitud de la codificación de M.

El teorema de invariancia se cumple igualmente por el prefijo y la complejidad condicional.

Este artículo incorpora material del teorema de la invariancia de PlanetMath, que está bajo la licencia Creative Commons Attribution / Share-Alike License


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Teorema de la invariancia — En diversos campos de la matemática se pueden encontrar teoremas denominados teorema de la invariancia: Teorema de la invariancia, utilizado en teoría de la información. Teorema de la invariancia del dominio, utilizado en topología. Teorema de la …   Wikipedia Español

  • Teoría cuántica de campos — Dispersión de neutrones. La dispersión inelástica de …   Wikipedia Español

  • Emmy Noether — Amalie Emmy Noether Nacimiento 23 de marzo de 1882 Erlangen, Baviera, Alemania Fallecimiento …   Wikipedia Español

  • Evidencia (filosofía) — Saltar a navegación, búsqueda Una evidencia (del latín, video, ver) es un conocimiento que se nos aparece intuitivamente de tal manera que podemos afirmar la validez de su contenido, como verdadero, con certeza, sin sombra de duda. Todos tenemos… …   Wikipedia Español

Compartir el artículo y extractos

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