complejidad de Kolmogorov

En la teoría de la información algorítmica (un subcampo de la informática y las matemáticas ), la complejidad de Kolmogorov de un objeto, como un fragmento de texto, es la longitud del programa informático más corto (en un lenguaje de programación predeterminado ) que produce dicho objeto como resultado. Es una medida de los recursos computacionales necesarios para especificar el objeto y también se conoce como complejidad algorítmica , complejidad de Solomonoff-Kolmogorov-Chaitin , complejidad de tamaño de programa , complejidad descriptiva o entropía algorítmica . Recibe su nombre de Andrey Kolmogorov , quien publicó por primera vez sobre el tema en 1963 ^{[ 1 ] [ nota 1 ]} y es una generalización de la teoría de la información clásica.

La noción de complejidad de Kolmogorov puede utilizarse para enunciar y demostrar resultados de imposibilidad similares al argumento diagonal de Cantor , el teorema de incompletitud de Gödel y el problema de la parada de Turing . En particular, ningún programa P que calcule una cota inferior para la complejidad de Kolmogorov de cada texto puede devolver un valor esencialmente mayor que la longitud de P (véase la sección § Teorema de incompletitud de Chaitin ); por lo tanto, ningún programa individual puede calcular la complejidad exacta de Kolmogorov para un número infinito de textos. 

La teoría de la información algorítmica es el área de la informática que estudia la complejidad de Kolmogorov y otras medidas de complejidad en cadenas (u otras estructuras de datos ).

El concepto y la teoría de la complejidad de Kolmogorov se basan en un teorema crucial descubierto por primera vez por Ray Solomonoff , quien lo publicó en 1960, describiéndolo en "Un informe preliminar sobre una teoría general de la inferencia inductiva" ^{[ 5 ]} como parte de su invención de la probabilidad algorítmica . Dio una descripción más completa en sus publicaciones de 1964, "Una teoría formal de la inferencia inductiva", Parte 1 y Parte 2 en Information and Control . ^{[ 6 ] [ 7 ]}

Andrey Kolmogorov publicó posteriormente este teorema de forma independiente en Problems Inform. Transmission en 1965. ^{[ 8 ]} Gregory Chaitin también presenta este teorema en el Journal of the ACM  ; el artículo de Chaitin se envió en octubre de 1966 y se revisó en diciembre de 1968, y cita los artículos de Solomonoff y Kolmogorov. ^{[ 9 ]}

El teorema establece que, entre los algoritmos que decodifican cadenas a partir de sus descripciones (códigos), existe uno óptimo. Este algoritmo, para todas las cadenas, permite códigos tan cortos como los que permite cualquier otro algoritmo, hasta una constante aditiva que depende de los algoritmos, pero no de las cadenas mismas. Solomonoff utilizó este algoritmo y las longitudes de código que permite para definir una "probabilidad universal" de una cadena, sobre la cual se puede basar la inferencia inductiva de los dígitos subsiguientes de la cadena. Kolmogorov utilizó este teorema para definir varias funciones de las cadenas, incluyendo complejidad, aleatoriedad e información.

Cuando Kolmogorov conoció el trabajo de Solomonoff, reconoció su prioridad. ^{[ 10 ]} Durante varios años, el trabajo de Solomonoff fue más conocido en la Unión Soviética que en Occidente. Sin embargo, el consenso general en la comunidad científica era asociar este tipo de complejidad con Kolmogorov, quien se ocupaba de la aleatoriedad de una secuencia, mientras que la probabilidad algorítmica se asoció con Solomonoff, quien se centró en la predicción utilizando su invención de la distribución de probabilidad a priori universal. El área más amplia que abarca la complejidad descriptiva y la probabilidad se denomina a menudo complejidad de Kolmogorov. El científico informático Ming Li considera esto un ejemplo del efecto Mateo : «...a todo aquel que tiene, más se le dará...» ^{[ 11 ]}

Existen varias variantes de la complejidad de Kolmogorov o información algorítmica. La más utilizada se basa en programas autodelimitantes y se debe principalmente a Leonid Levin (1974).

Mark Burgin introdujo un enfoque axiomático de la complejidad de Kolmogorov basado en los axiomas de Blum (Blum 1967) en el artículo presentado para su publicación por Andrey Kolmogorov. ^{[ 12 ]}

Escribimos${\displaystyle K(x,y)}$ser${\displaystyle K((x,y))}$, dónde${\displaystyle (x,y)}$significa alguna forma fija de codificar una tupla de cadenas x e y.

def kolmogorov_complexity ( s : str ): para i = 1 hasta infinito : para cada cadena p de longitud exactamente i si is_valid_program ( p ) y evaluate ( p ) == s return i

def kolmogorov_complexity ( s : str )

def generate_complex_string (): str para i = 1 a infinito : para cada cadena s de longitud exactamente i si kolmogorov_complexity ( s ) >= 8000000000 return s

Regla de la cadena para la complejidad de Kolmogorov

La regla de la cadena ^{[ 15 ]} para la complejidad de Kolmogorov establece que existe una constante c tal que para todo X e Y :

${\displaystyle K(X,Y)=K(X)+K(Y|X)+c\cdot max(1,log(K(X,Y)))}$.

Establece que el programa más corto que reproduce X e Y no es más que un término logarítmico mayor que un programa para reproducir X y un programa para reproducir Y dado X. Utilizando esta afirmación, se puede definir un análogo de la información mutua para la complejidad de Kolmogorov .

Es sencillo calcular los límites superiores de K ( s )  – simplemente comprime la cadena s con algún método, implementa el descompresor correspondiente en el lenguaje elegido, concatena el descompresor a la cadena comprimida y mide la longitud de la cadena resultante  – concretamente, el tamaño de un archivo autoextraíble en el lenguaje dado.

Una cadena s es compresible por un número c si su descripción tiene una longitud que no excede | s | − c bits. Esto equivale a decir que K ( s ) ≤ | s | − c . De lo contrario, s es incompresible por c . Una cadena incompresible por 1 se denomina simplemente incompresible  ; por el principio del palomar , que se aplica porque cada cadena comprimida se corresponde con una única cadena sin comprimir, deben existir cadenas incompresibles , ya que hay 2n ^cadenas de bits de longitud n , pero solo ²ⁿ − 1 cadenas más cortas, es decir, cadenas de longitud menor que n (es decir, con longitud 0, 1, ..., n  −  1). ^{[ nota 7 ]}

Por la misma razón, la mayoría de las cadenas son complejas en el sentido de que no se pueden comprimir significativamente  : su K ( s ) no es mucho menor que | s |, la longitud de s en bits. Para ser más precisos, fijemos un valor de n . Hay 2n ^cadenas de bits de longitud n . La distribución de probabilidad uniforme en el espacio de estas cadenas de bits asigna exactamente el mismo peso 2 ^{− n} a cada cadena de longitud n .

Teorema : Con la distribución de probabilidad uniforme en el espacio de cadenas de bits de longitud n , la probabilidad de que una cadena sea incompresible por c es al menos 1 − 2 ^{− c +1} + 2 ^{− n} .

Para demostrar el teorema, observe que el número de descripciones de longitud que no excede n − c viene dado por la serie geométrica:

Quedan al menos

cadenas de bits de longitud n que son incompresibles por c . Para determinar la probabilidad, divida por 2 ⁿ .

Según el teorema anterior ( §  Compresión ), la mayoría de las cadenas son complejas en el sentido de que no pueden describirse de ninguna manera significativamente "comprimida". Sin embargo, resulta que el hecho de que una cadena específica sea compleja no puede probarse formalmente si su complejidad supera cierto umbral. La formalización precisa es la siguiente. Primero, se fija un sistema axiomático particular S para los números naturales . El sistema axiomático debe ser lo suficientemente potente como para que, a ciertas afirmaciones A sobre la complejidad de las cadenas, se pueda asociar una fórmula F _A en S. Esta asociación debe tener la siguiente propiedad:

Si F _A es demostrable a partir de los axiomas de S , entonces la afirmación correspondiente A debe ser verdadera. Esta "formalización" se puede lograr basándose en una numeración de Gödel .

Teorema : Existe una constante L (que solo depende de S y de la elección del lenguaje de descripción) tal que no existe una cadena s para la cual la afirmación

${\displaystyle K(s)\geq L}$   (tal como se formaliza en S )

puede demostrarse dentro de S. ^{[ 16 ] [ 17 ]}

Idea de la prueba : La prueba de este resultado se basa en una construcción autorreferencial utilizada en la paradoja de Berry . Inicialmente, obtenemos un programa que enumera las pruebas dentro de S y especificamos un procedimiento P que toma como entrada un entero L e imprime las cadenas x que se encuentran dentro de las pruebas dentro de S de la afirmación K ( x ) ≥ L. Al establecer L mayor que la longitud de este procedimiento P , tenemos que la longitud requerida de un programa para imprimir x, como se indica en K ( x ) ≥ L, como al menos L, es entonces menor que la cantidad L desde que la cadena x fue impresa por el procedimiento P. Esto es una contradicción. Por lo tanto, no es posible que el sistema de prueba S demuestre K ( x ) ≥ L para L arbitrariamente grande, en particular, para L mayor que la longitud del procedimiento P (que es finita).

Prueba :

Podemos encontrar una enumeración efectiva de todas las pruebas formales en S mediante algún procedimiento.

def nth_proof ( n : int )

que toma como entrada n y produce alguna prueba. Esta función enumera todas las pruebas. Algunas de ellas son pruebas de fórmulas que no nos interesan aquí, ya que se produce cualquier prueba posible en el lenguaje de S para algún n . Algunas de ellas son fórmulas de complejidad de la forma K ( s )  ≥ n , donde s y n son constantes en el lenguaje de S. Hay un procedimiento 

def nth_proof_proves_complexity_formula ( n : int ): bool

que determina si la n -ésima prueba realmente demuestra una fórmula de complejidad K ( s )  ≥ L. Las cadenas s , y el entero L a su vez, se pueden calcular mediante el procedimiento: 

def string_nth_proof ( n : int )

def complexity_lower_bound_nth_proof ( n : int ): int

Considere el siguiente procedimiento:

def generate_provably_complex_string ( n : int ): for i = 1 to infinity : if nth_proof_proves_complexity_formula ( i ) and complexity_lower_bound_nth_proof ( i ) ≥ n return string_nth_proof ( i )

Dado un${\displaystyle n}$Este procedimiento prueba todas las pruebas hasta que encuentra una cadena y una prueba en el sistema formal S de la fórmula.${\displaystyle K(s)\geq L}$para algunos${\displaystyle L\geq n}$; si no existe tal prueba, el bucle se repite indefinidamente.

Finalmente, consideremos el programa que consta de todas estas definiciones de procedimiento y una llamada principal:

generar_cadena_de_complejidad_demostrable ( n ₀ )

donde la constante${\displaystyle n_{0}}$se determinará más adelante. La duración total del programa se puede expresar como${\displaystyle U+log_{2}(n_{0})}$, dónde${\displaystyle U}$es alguna constante y${\displaystyle log_{2}(n_{0})}$representa la longitud del valor entero${\displaystyle n_{0}}$, bajo el supuesto razonable de que está codificado en dígitos binarios. Elegiremos${\displaystyle n_{0}}$ser mayor que la duración del programa, es decir, de tal manera que${\ Displaystyle n_ {0}> U + log_ {2} (n_ {0})}$Esto es claramente cierto para${\displaystyle n_{0}}$suficientemente grande, porque el lado izquierdo crece linealmente en${\displaystyle n_{0}}$mientras que el lado derecho crece logarítmicamente en${\displaystyle n_{0}}$hasta la constante fija${\displaystyle U}$.

Entonces no hay prueba de la forma "${\displaystyle K(s)\geq L}$" con${\displaystyle L\geq n_{0}}$se puede obtener en S , como se puede ver por un argumento indirecto : Si complexity_lower_bound_nth_proof(i)pudiera devolver un valor${\displaystyle \geq n_{0}}$, entonces el bucle interno generate_provably_complex_stringterminaría eventualmente, y ese procedimiento devolvería una cadena s tal que

Esto es una contradicción, QED

Como consecuencia, el programa anterior, con el valor elegido de${\displaystyle n_{0}}$, debe repetirse indefinidamente.

Se utilizan ideas similares para demostrar las propiedades de la constante de Chaitin .

El principio de longitud mínima del mensaje (MML) de la inferencia estadística e inductiva y del aprendizaje automático fue desarrollado por C.S. Wallace y D.M. Boulton en 1968. El MML es bayesiano (es decir, incorpora creencias previas) y se basa en la teoría de la información. Posee las propiedades deseables de invariancia estadística (es decir, la inferencia se transforma con una reparametrización, como de coordenadas polares a coordenadas cartesianas), consistencia estadística (es decir, incluso para problemas muy difíciles, el MML converge a cualquier modelo subyacente) y eficiencia (es decir, el modelo MML converge a cualquier modelo subyacente verdadero tan rápido como sea posible). C.S. Wallace y D.L. Dowe (1999) demostraron una conexión formal entre el MML y la teoría de la información algorítmica (o complejidad de Kolmogorov). ^{[ 18 ]}

La aleatoriedad de Kolmogorov define una cadena (generalmente de bits ) como aleatoria si el programa informático más corto que puede producir esa cadena tiene aproximadamente la misma longitud que la cadena misma. Para ser más precisos, una cadena${\displaystyle x}$de longitud${\displaystyle n}$se denomina aleatorio de Kolmogorov si ${\displaystyle K(x)\geq n+O(1)}$dónde${\displaystyle K}$es la complejidad de Kolmogorov sin prefijos definida anteriormente. Una cadena aleatoria en este sentido es incompresible , ya que es imposible "comprimir" la cadena en un programa más corto que la propia cadena. Existe al menos una cadena aleatoria de Kolmogorov de cada longitud. ^{[ 19 ]}

Esta definición puede extenderse para definir una noción de aleatoriedad para secuencias infinitas a partir de un alfabeto finito. Estas secuencias aleatorias algorítmicas pueden definirse de tres maneras equivalentes. Una manera utiliza un análogo efectivo de la teoría de la medida ; otra utiliza martingalas efectivas . La tercera manera define una secuencia infinita como aleatoria si la complejidad de Kolmogorov sin prefijos de sus segmentos iniciales crece lo suficientemente rápido  ; debe existir una constante c tal que la complejidad de un segmento inicial de longitud n sea siempre al menos n − c . ^{[ 20 ]}

Para los sistemas dinámicos, la tasa de entropía y la complejidad algorítmica de las trayectorias están relacionadas por un teorema de Brudno, que establece que la igualdad${\displaystyle K(x;T)=h(T)}$se aplica a casi todos${\displaystyle x}$. ^{[ 21 ]}

Se puede demostrar ^{[ 22 ]} que, para la salida de fuentes de información de Markov , la complejidad de Kolmogorov está relacionada con la entropía de la fuente de información. Más precisamente, la complejidad de Kolmogorov de la salida de una fuente de información de Markov, normalizada por la longitud de la salida, converge casi con seguridad (cuando la longitud de la salida tiende a infinito) a la entropía de la fuente.

Teorema. (Teorema 14.2.5 ^{[ 23 ]} ) La complejidad de Kolmogorov condicional de una cadena binaria${\displaystyle x_{1:n}}$Satisface$${\displaystyle {\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)}$$dónde${\displaystyle H_{b}}$es la función de entropía binaria (que no debe confundirse con la tasa de entropía).

La función de complejidad de Kolmogorov es equivalente a decidir el problema de la parada.

Si disponemos de un oráculo de parada, la complejidad de Kolmogorov de una cadena se puede calcular simplemente probando todos los programas de parada, en orden lexicográfico, hasta que uno de ellos genere la cadena.

La otra dirección es mucho más compleja. ^{[ 24 ] [ 25 ]} Muestra que, dada una función de complejidad de Kolmogorov, podemos construir una función${\displaystyle p}$, de tal manera que${\displaystyle p(n)\geq BB(n)}$para todos los grandes${\displaystyle n}$, dónde${\displaystyle BB}$es la función de desplazamiento Busy Beaver (también denominada como${\displaystyle S(n)}$). Al modificar la función en valores más bajos de${\displaystyle n}$obtenemos un límite superior en${\displaystyle BB}$, lo que resuelve el problema de la parada.

Considere este programa${\textstyle p_{K}}$, que toma la entrada como${\textstyle n}$y utiliza${\textstyle K}$.

• Enumera todas las cadenas de longitud${\textstyle \leq 2n+1}$.
• Para cada una de esas cadenas${\textstyle x}$, enumerar todos los programas (sin prefijo) de longitud${\displaystyle K(x)}$hasta que uno de ellos haga una salida${\textstyle x}$Registrar su tiempo de ejecución${\textstyle n_{x}}$.
• Produce la mayor${\textstyle n_{x}}$.

Demostramos por contradicción que${\textstyle p_{K}(n)\geq BB(n)}$para todos los grandes${\textstyle n}$.

Dejar${\textstyle p_{n}}$ser un castor ocupado de longitud${\displaystyle n}$Consideremos este programa (sin prefijos), que no requiere ninguna entrada:

• Ejecutar el programa${\textstyle p_{n}}$y registrar su duración de ejecución${\textstyle BB(n)}$.
• Generar todos los programas con longitud${\textstyle \leq 2n}$Ejecuta cada uno de ellos durante un máximo de${\textstyle BB(n)}$pasos. Observe los resultados de aquellos que se han detenido.
• Muestra la cadena con el orden lexicográfico más bajo que no haya sido mostrada por ninguna de las anteriores.

Sea la cadena de salida del programa${\textstyle x}$.

El programa tiene duración${\textstyle \leq n+2\log _ {2}n+O(1)}$, dónde${\displaystyle n}$proviene de la longitud del Busy Beaver${\textstyle p_{n}}$,${\displaystyle 2\log _{2}n}$proviene del uso del código delta de Elias (sin prefijo) para el número${\displaystyle n}$, y${\displaystyle O(1)}$proviene del resto del programa. Por lo tanto,$${\displaystyle K(x)\leq n+2\log _{2}n+O(1)\leq 2n}$$para todos los grandes${\textstyle n}$Además, dado que solo hay un número limitado de programas posibles con una duración determinada,${\textstyle \leq 2n}$, tenemos${\textstyle l(x)\leq 2n+1}$por el principio del palomar . Por suposición,${\textstyle p_{K}(n)<BB(n)}$, por lo que cada cadena de longitud${\textstyle \leq 2n+1}$tiene un programa mínimo con tiempo de ejecución${\textstyle <BB(n)}$. Por lo tanto, la cadena${\textstyle x}$tiene un programa mínimo con tiempo de ejecución${\textstyle <BB(n)}$Además, ese programa tiene duración${\textstyle K(x)\leq 2n}$Esto contradice cómo${\textstyle x}$fue construido.

Reparar una máquina de Turing universal${\displaystyle U}$, la misma que se utiliza para definir la complejidad de Kolmogorov (sin prefijos). Defina la probabilidad universal (sin prefijos) de una cadena${\displaystyle x}$ser$${\displaystyle P(x)=\sum _{U(p)=x}2^{-l(p)}}$$En otras palabras, es la probabilidad de que, dada una secuencia binaria aleatoria uniforme como entrada, la máquina de Turing universal se detenga después de leer un cierto prefijo de la secuencia y genere una salida.${\displaystyle x}$.

Nota.${\displaystyle U(p)=x}$no significa que el flujo de entrada sea${\displaystyle p000\cdots }$pero que la máquina de Turing universal se detendría en algún momento después de leer el segmento inicial.${\displaystyle p}$, sin leer ninguna otra entrada, y que, cuando se detiene, ha escrito${\displaystyle x}$a la cinta de salida.

Teorema. (Teorema 14.11.1 ^{[ 23 ]} )${\displaystyle \log {\frac {1}{P(x)}}=K(x)+O(1)}$

La complejidad de Kolmogorov se ha utilizado en el contexto de la biología para argumentar que las simetrías y los arreglos modulares observados en múltiples especies surgen de la tendencia de la evolución a preferir la complejidad mínima de Kolmogorov. ^{[ 26 ]} Considerando el genoma como un programa que debe resolver una tarea o implementar una serie de funciones, se preferirían los programas más cortos, ya que son más fáciles de encontrar mediante los mecanismos de la evolución. ^{[ 27 ]} Un ejemplo de este enfoque es la simetría óctuple del circuito de la brújula que se encuentra en diversas especies de insectos, la cual corresponde al circuito que es funcional y requiere la complejidad mínima de Kolmogorov para ser generado a partir de unidades autorreplicantes. ^{[ 28 ]}

La complejidad de Kolmogorov condicional de dos cadenas${\displaystyle K(x|y)}$En términos generales, se define como la complejidad de Kolmogorov de x dado y como entrada auxiliar al procedimiento. ^{[ 29 ] [ 30 ]} Así que, mientras que la complejidad de Kolmogorov (incondicional)${\displaystyle K(x)}$de una secuencia${\displaystyle x}$es la longitud del programa binario más corto que produce${\displaystyle x}$en una computadora universal y puede considerarse como la cantidad mínima de información necesaria para producir${\displaystyle x}$, la complejidad condicional de Kolmogorov${\displaystyle K(x|y)}$se define como la longitud del programa binario más corto que calcula${\displaystyle x}$cuando${\displaystyle y}$se proporciona como entrada, utilizando una computadora universal. ^{[ 31 ]}

También existe una complejidad condicional a la longitud.${\displaystyle K(x|L(x))}$, que es la complejidad de x dada la longitud de x como conocida/de entrada. ^{[ 32 ] [ 33 ]}

La complejidad de Kolmogorov con límite de tiempo es una versión modificada de la complejidad de Kolmogorov donde el espacio de programas para buscar una solución se limita solo a programas que pueden ejecutarse dentro de un número predefinido de pasos. ^{[ 34 ]} Se plantea la hipótesis de que la posibilidad de la existencia de un algoritmo eficiente para determinar la complejidad aproximada de Kolmogorov con límite de tiempo está relacionada con la cuestión de si existen funciones unidireccionales verdaderas . ^{[ 35 ] [ 36 ]}

• paradoja de Berry
• Código golf
• Compresión de datos
• Teoría de la complejidad descriptiva
• Inducción gramatical
• razonamiento inductivo
• función de estructura de Kolmogorov
• distancia de Levenshtein
• Hipótesis múltiple
• La teoría de la inferencia inductiva de Solomonoff
• entropía de muestra
• El número del Rayo

• Blum, M. (1967). "Sobre el tamaño de las máquinas" . Information and Control . 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
• Brudno, A. (1983). "Entropía y complejidad de las trayectorias de un sistema dinámico". Transacciones de la Sociedad Matemática de Moscú . 2 : 127–151 .
• Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª  ed.). Wiley-Interscience. ISBN 0-471-24195-4.
• Lajos, Rónyai; Gábor, Ivanyos; Réka, Szabó (1999). Algoritmusok . TipoTeX. ISBN 963-279-014-6.
• Li, Ming; Vitanyi, Paul (1997). Introducción a la complejidad de Kolmogorov y sus aplicaciones . Saltador. ISBN 978-0-387-33998-6.
• Yu, Manin (1977). Un curso de lógica matemática . Springer-Verlag. ISBN 978-0-7204-2844-5.
• Sipser, Michael (1997). Introducción a la teoría de la computación . PWS. ISBN 0-534-95097-3.
• Downey, Rodney G.; Hirschfeldt, Denis R. (2010). «Aleatoriedad y complejidad algorítmicas» . Theory and Applications of Computability . doi : 10.1007/978-0-387-68441-3 . ISBN 978-0-387-95567-4ISSN 2190-619X​​ 

• El legado de Andrei Nikolaevich Kolmogorov
• Publicaciones en línea de Chaitin
• Página de Solomonoff sobre IDSIA
• Generalizaciones de la información algorítmica por J. Schmidhuber
• "Reseña de Li Vitányi 1997" .
• Tromp, John. "El campo de juego de John para el cálculo lambda y la lógica combinatoria" .El modelo informático de cálculo lambda de Tromp ofrece una definición concreta de K()]
• Inteligencia artificial universal basada en la complejidad de Kolmogorov ISBN 3-540-22139-5Por M. Hutter : ISBN 3-540-22139-5
• Las páginas sobre la longitud mínima del mensaje (MML, por sus siglas en inglés) y la navaja de Occam de David Dowe .
• Grunwald, P.; Pitt, MA (2005). Myung, IJ (ed.). Avances en la longitud mínima de descripción: teoría y aplicaciones . MIT Press. ISBN 0-262-07262-9.