Para una cadena binaria finita, la complejidad de Kolmogorov es la longitud (en bits) del programa más corto en una máquina de Turing universal fija que genera esa cadena y luego se detiene; formaliza la compresibilidad algorítmica.

Principio

La complejidad depende de la máquina salvo una constante aditiva (teorema de invariancia) y en general es no computable; las cadenas sin descripción más corta que ellas mismas se consideran aleatorias algorítmicamente.

Demostración

Una cadena formada por 10.000 repeticiones de '01' tiene baja complejidad de Kolmogorov porque un programa corto puede generar el patrón, mientras que una cadena de 10.000 lanzamientos independientes de moneda probablemente tendrá complejidad cercana a 10.000.

Aplicación incorrecta

Tratar la complejidad de Kolmogorov como una métrica computable para compresión práctica o confundirla directamente con la entropía de Shannon de una fuente sin considerar la dependencia al modelo y a la máquina.

Consecuencia

Proporciona una noción rigurosa de aleatoriedad y una cota inferior absoluta sobre la compresión sin pérdida para objetos individuales; sustenta la teoría de la información algorítmica y los límites de la inferencia con descripciones finitas.

Inversión

Reformular la incertidumbre en términos probabilísticos (información de Shannon) produce medidas computables en promedio derivadas de distribuciones en lugar de la medida no computable y centrada en la instancia que ofrece Kolmogorov.

Límite

Se aplica a objetos discretos finitos respecto a una máquina universal elegida; no es computable en general, depende de convenciones de codificación de programas hasta una constante aditiva, y extensiones (prefijo, monotónica) ajustan detalles técnicos.

Tensión semántica

A menudo se confunde con las ratios de compresión prácticas o con la tasa de entropía de una fuente estocástica; la tensión está entre la irreductibilidad algorítmica centrada en la instancia y las medidas de información promedio basadas en el conjunto.

Síntesis

La complejidad de Kolmogorov cuantifica la longitud de la descripción algorítmica más corta de un objeto individual relativa a un modelo de computación universal, formalizando la compresibilidad y la aleatoriedad algorítmica a pesar de su no computabilidad.