Siguiente: Ejemplos y observaciones Un nivel arriba: Presentación de la teoría Anterior: Ejemplos

Incomprimibilidad

Como una consecuencia del Teorema de Invarianza se tiene que para alguna constante c:

$$K(x)\leq n(x)+c.$$

Ahora bien,puesto que hay 2ⁿ cadenas de longitud n y hay a lo sumo 2ⁿ-1 descripciones de longitud menor que n necesariamente alguna cadena de longitud n ha de tener una descripción de longitud al menos de n. Tal cadena es incomprimible. Formalmente: x es incomprimible si

$$K(x)\geq \vert x\vert.$$

Similarmente podemos ver que para todos n,y existe un objeto x tal que

$$K(x\vert y)\geq n(x).$$