El valor exacto de la complejidad de Kolmogorov depende del idioma elegido para representar las cadenas. Este lenguaje tiene que ser Turing completo, por lo que representar todas las cadenas como ellos mismos no es una opción.
Según el principio del casillero, si hay al menos una cadena de longitud como máximo cuya representación es más corta que sí misma, entonces también hay al menos una cadena de longitud como máximo n cuya representación es más larga que sí misma. (La representación es un algoritmo de compresión).nortenorte
Puede tener un lenguaje de descripción donde cada cadena tenga una representación que sea como máximo un poco más larga que ella misma: comience cada representación con un bit que indique "imprimir literalmente" o "interpretar". Sin embargo, no todos los lenguajes de descripción son tan simples.
CC
Gilles 'SO- deja de ser malvado'
fuente