La longitud (en bits) de la descripción más corta efectiva o del programa más corto que, ejecutado en una máquina de Turing universal fija, produce una cadena finita dada, considerada hasta una constante aditiva que depende de la elección de la máquina universal.

Principio

Tomar la longitud mínima de descripción sobre una máquina de referencia universal como medida objetiva del contenido de información algorítmica y de la aleatoriedad de un objeto finito individual.

Demostración

Para la cadena binaria S = '0101010101', un programa breve que genere el patrón repetido tiene baja complejidad de Kolmogorov, mientras que para una cadena R producida por lanzamientos de moneda sin patrón corto, todo programa que produzca R tendrá una longitud cercana a la de R; además, la complejidad de Kolmogorov no es computable en general, por lo que sólo pueden darse cotas superiores exhibiendo programas concretos.

Aplicación incorrecta

Tratar la complejidad de Kolmogorov como una cantidad computable para cadenas arbitrarias, o equipararla directamente con la entropía de Shannon de una distribución sin tener en cuenta que la complejidad de Kolmogorov es una propiedad de objetos individuales y depende de la máquina universal sólo hasta una constante aditiva.

Consecuencia

Su uso correcto da una clasificación invariante (hasta una constante) de cadenas por su compresibilidad, formaliza la noción de aleatoriedad para objetos individuales y explica los límites de la compresión algorítmica y la existencia de cadenas incomprimibles.

Inversión

Si se invierte la perspectiva y se busca la longitud máxima de descripción en lugar de la mínima, se destaca la incomprimibilidad: la mayoría de las cadenas de una longitud dada tienen complejidad de Kolmogorov cercana a esa longitud, de modo que la afirmación invertida subraya la tipicidad más que la compresibilidad.

Límite

La definición se aplica a cadenas finitas relativas a una máquina de Turing universal fija; está definida sólo hasta una constante aditiva, no es computable en general y no cuantifica directamente información en sentido medio o distribucional sin un modelo probabilístico adicional.

Tensión semántica

Existe tensión entre la complejidad de Kolmogorov (propiedad de objetos individuales, no computable, dependiente de la máquina hasta constantes) y la entropía de Shannon (medida estadística computable de una variable aleatoria): pueden coincidir en ciertos límites estocásticos pero cumplen funciones distintas.

Síntesis

La complejidad de Kolmogorov unifica la longitud de la descripción algorítmica y una noción formal de aleatoriedad al tomar la longitud del programa más corto en una máquina universal fija como medida canónica de cuánta información contiene una cadena finita individual, reconociendo la dependencia en la máquina y la no computabilidad.