Medida del contenido informativo algorítmico de un objeto finito, definida como la longitud de la descripción más corta (programa más entrada) en una máquina de descripción universal fija que produce el objeto.

Principio

La complejidad de una cadena finita individual es la longitud mínima, salvo una constante aditiva dependiente de la máquina universal elegida, de un programa que imprime esa cadena y se detiene.

Demostración

Una cadena binaria periódica como '010101...0101' tiene baja complejidad de Kolmogorov porque un programa corto puede generar la repetición, mientras que una cadena larga obtenida por lanzamientos de moneda tiene típicamente complejidad cercana al máximo.

Aplicación incorrecta

Tratar la cantidad como computable para entradas arbitrarias, o comparar valores sin especificar entre distintas máquinas universales sin ajustar las constantes aditivas, conduce a conclusiones inválidas.

Consecuencia

Proporciona una base formal para el algoritmoismo de la aleatoriedad individual, cotas inferiores de no compresibilidad y límites teóricos sobre compresión algorítmica e inferencia.

Inversión

Pasar a medidas basadas en conjuntos (como la incertidumbre media de una distribución) invierte el foco desde la minimalidad descriptiva de un objeto único hacia la incertidumbre estadística entre muestras.

Límite

Definida para objetos discretos finitos relativa a una elección de método de descripción universal; en general no es computable y depende de la invariancia hasta una constante aditiva dependiente de la máquina.

Tensión semántica

Contrasta con la información al estilo Shannon, que cuantifica la incertidumbre media de una fuente estocástica; la complejidad de Kolmogorov cuantifica la longitud de descripción de un individuo independiente de conjuntos probabilísticos.

Síntesis

La complejidad de Kolmogorov formaliza la longitud de la descripción efectiva más corta de un objeto concreto respecto a un esquema de descripción universal, fundamentando la aleatoriedad algorítmica y la compresibilidad como propiedades de instancias individuales.