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:
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