Teorema d'invariància

Dintre de la teoria algorísmica de la informació, el teorema d'invariància , inicialment proposat per Ray Solomonoff, estableix que una màquina universal de Turing proporciona un mitjà òptim de descripció, fins a una constant additiva. Formalment, per a cada màquina M existeix una constant c tal que per a totes les cadenes binàries x tenim:

$C(x)=C_{U}(x)\leq C_{M}(x)+c\,$

Això es dedueix de la definició d'una màquina universal de Turing, tenint c = l (< M >) com la longitud de la codificació de M. El teorema de la invariància defineix de la mateixa manera les complexitats prefixades i condicionals.

Referències

• Aquest article incorpora material del teorema de la invariància de PlanetMath, que es troba sota llicència Creative Commons Attribution / Share-Alike License CC-BY-SA