Teorema d'invariància

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]