Siguiente: Observaciones Un nivel arriba: Presentación de la teoría Anterior: Definiciones básicas

Observación

Si $\left(S_i\right)_{i\in[1,r]}$ es una colección de métodos para generar a D entonces se puede construir un método S tal que

$$\exists c(<\log(r))\;\forall x\in D:\;K_S(x)\leq \mathop{\rm Min}_{i\leq r}\{K_{S_i}(x)\}+c.$$

En efecto, para obtener S lo que hay que hacer es, a cada programa p que genere a x, adjuntarle una cadena de $\log(r)$ bits que indique el procedimiento S_i a elegir entre los r diponibles.


Dados dos procedimientos S,T se dice que S absorbe a T si

$$\exists c:\;K_S(x)\leq K_T(x)+c\;\forall x.$$

Los dos métodos son c-equivalentes si uno absorbe al otro con precisión c, es decir,

$$\vert K_S(x)- K_T(x)\vert\leq c.$$