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