Compresibilidad

def. Una cadena $ x \in \Sigma^* $, es c-compresible cuando

def. Una cadena $ x \in \Sigma^* $, es c-incompresible si no es c-compresible, es decir

Teorema. Existen cadenas 1-incompresibles de todas las longitudes.

Dem. Consideremos un $ n \in \mathbb{N} $ y pensemos en las cadenas de longitud n.

¿cuántas cadenas de longitud n?

$ 2 * 2 *.. * 2 $

$ 2^n $