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 de un programa informático más corto (en un lenguaje de programación predeterminado ) que produce el objeto como salida. 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 del tamaño del 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] [2]} 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 detención de Turing . En particular, ningún programa P que calcule un límite inferior para la complejidad de Kolmogorov de cada texto puede devolver un valor esencialmente mayor que la propia longitud de P (véase la sección § Teorema de incompletitud de Chaitin); por lo tanto, ningún programa puede calcular la complejidad de Kolmogorov exacta para infinitos textos. La complejidad de Kolmogorov es la longitud de la versión finalmente comprimida de un archivo (es decir, cualquier cosa que se pueda poner en una computadora). Formalmente, es la longitud de un programa más corto a partir del cual se puede reconstruir el archivo. Analizamos la incomputabilidad de la complejidad de Kolmogorov, qué lagunas formales nos deja, enfoques recientes para calcular o aproximar la complejidad de Kolmogorov, qué enfoques son problemáticos y cuáles son viables. ^[3]

Considere las siguientes dos cadenas de 32 letras minúsculas y dígitos:

abababababababababababababababab, y

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

La primera cadena tiene una breve descripción en inglés, concretamente "write ab 16 times", que consta de 17 caracteres. La segunda no tiene una descripción simple obvia (que utilice el mismo conjunto de caracteres) más allá de escribir la cadena en sí, es decir, "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7", que tiene 38 caracteres. Por lo tanto, se puede decir que la operación de escribir la primera cadena tiene "menos complejidad" que escribir la segunda.

Más formalmente, la complejidad de una cadena es la longitud de la descripción más corta posible de la cadena en algún lenguaje de descripción universal fijo (la sensibilidad de la complejidad en relación con la elección del lenguaje de descripción se analiza más adelante). Se puede demostrar que la complejidad de Kolmogorov de cualquier cadena no puede ser más de unos pocos bytes mayor que la longitud de la cadena misma. Las cadenas como el ejemplo abab anterior, cuya complejidad de Kolmogorov es pequeña en relación con el tamaño de la cadena, no se consideran complejas.

La complejidad de Kolmogorov se puede definir para cualquier objeto matemático, pero para simplificar el alcance de este artículo se limita a cadenas. Primero debemos especificar un lenguaje de descripción para cadenas. Dicho lenguaje de descripción puede basarse en cualquier lenguaje de programación informática, como Lisp , Pascal o Java . Si P es un programa que genera una cadena x , entonces P es una descripción de x . La longitud de la descripción es simplemente la longitud de P como cadena de caracteres, multiplicada por el número de bits de un carácter (por ejemplo, 7 para ASCII ).

Alternativamente, podríamos elegir una codificación para las máquinas de Turing , donde una codificación es una función que asocia a cada máquina de Turing M una cadena de bits < M >. Si M es una máquina de Turing que, en la entrada w , genera la cadena x , entonces la cadena concatenada < M > w es una descripción de x . Para el análisis teórico, este enfoque es más adecuado para construir pruebas formales detalladas y generalmente se prefiere en la literatura de investigación. En este artículo, se analiza un enfoque informal.

Cualquier cadena s tiene al menos una descripción. Por ejemplo, la segunda cadena anterior se genera mediante el pseudocódigo :

función GenerateString2() devuelve "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

Mientras que la primera cadena se genera mediante el pseudocódigo (mucho más corto):

función GenerateString1() devuelve "ab" × 16

Si una descripción d ( s ) de una cadena s tiene una longitud mínima (es decir, utiliza la menor cantidad de bits), se denomina descripción mínima de s , y la longitud de d ( s ) (es decir, la cantidad de bits en la descripción mínima) es la complejidad de Kolmogorov de s , escrita K ( s ). Simbólicamente,

K ( s ) = | d ( s )|.

La longitud de la descripción más corta dependerá del lenguaje de descripción elegido, pero el efecto de cambiar de lenguaje es limitado (un resultado llamado teorema de invariancia ).

Existen dos definiciones de complejidad de Kolmogorov: simple y sin prefijo . La complejidad simple es la longitud mínima de descripción de cualquier programa, y ​​se denota por , mientras que la complejidad sin prefijo es la longitud mínima de descripción de cualquier programa codificado en un código sin prefijo, y se denota por . La complejidad simple es más intuitiva, pero la complejidad sin prefijo es más fácil de estudiar.${\estilo de visualización C(x)}$${\estilo de visualización K(x)}$

De manera predeterminada, todas las ecuaciones se cumplen solo hasta una constante aditiva. Por ejemplo, realmente significa que , es decir, .${\displaystyle f(x)=g(x)}$${\displaystyle f(x)=g(x)+O(1)}$${\displaystyle \existe c,\para todo x,|f(x)-g(x)|\leq c}$

Sea una función computable que asigna cadenas binarias finitas a cadenas binarias. Es una función universal si, y solo si, para cualquier computable , podemos codificar la función en un "programa" , tal que . Podemos pensar en ella como un intérprete de programas, que toma un segmento inicial que describe el programa, seguido de los datos que el programa debe procesar.${\displaystyle U:2^{*}\a 2^{*}}$${\displaystyle f:2^{*}\a 2^{*}}$$estilo de visualización s_ {f}}$${\displaystyle \para todo x\en 2^{*},U(s_{f}x)=f(x)}$${\estilo de visualización U}$

Un problema con la complejidad simple es que , intuitivamente hablando, no hay una manera general de saber dónde dividir una cadena de salida simplemente mirando la cadena concatenada. Podemos dividirla especificando la longitud de o , pero eso requeriría símbolos adicionales. De hecho, para cualquier existe tal que . ^[4]${\displaystyle C(xy)\no <C(x)+C(y)}$${\estilo de visualización x}$${\estilo de visualización y}$${\displaystyle O(\min(\ln x,\ln y))}$${\displaystyle c>0}$${\estilo de visualización x,y}$${\displaystyle C(xy)\geq C(x)+C(y)+c}$

Normalmente, las desigualdades con complejidad simple tienen un término como en un lado, mientras que las mismas desigualdades con complejidad libre de prefijo solo tienen .${\displaystyle O(\min(\ln x,\ln y))}$${\estilo de visualización O(1)}$

El principal problema de la complejidad simple es que hay algo extra que se introduce en el programa. Un programa no sólo representa algo con su código, sino que también representa su propia longitud. En particular, un programa puede representar un número binario hasta , simplemente por su propia longitud. Dicho de otra manera, es como si estuviéramos usando un símbolo de terminación para indicar dónde termina una palabra, y por lo tanto no estamos usando 2 símbolos, sino 3. Para corregir este defecto, introducimos la complejidad de Kolmogorov sin prefijo. ^[5]${\estilo de visualización x}$$estilo de visualización {\log _{2}|x|}$

Un código sin prefijo es un subconjunto de tal manera que, dadas dos palabras diferentes en el conjunto, ninguna es prefijo de la otra. El beneficio de un código sin prefijo es que podemos construir una máquina que lea palabras del código hacia adelante en una dirección y, tan pronto como lea el último símbolo de la palabra, sepa que la palabra está terminada y no necesita retroceder ni un símbolo de terminación.${\estilo de visualización 2^{*}}$${\estilo de visualización x,y}$

Definamos una máquina de Turing sin prefijo como una máquina de Turing que viene con un código sin prefijo, de modo que la máquina de Turing puede leer cualquier cadena del código en una dirección y dejar de leer tan pronto como lee el último símbolo. Después, puede calcular en una cinta de trabajo y escribir en una cinta de escritura, pero ya no puede mover su cabezal de lectura.

Esto nos da la siguiente forma formal de describir K. ^[6 ]

• Arreglar una máquina de Turing universal sin prefijo, con tres cintas: una cinta de lectura infinita en una dirección, una cinta de trabajo infinita en dos direcciones y una cinta de escritura infinita en una dirección.
• La máquina puede leer la cinta de lectura en una sola dirección (sin retroceso) y escribir en la cinta de escritura en una sola dirección. Puede leer y escribir la cinta de trabajo en ambas direcciones.
• La cinta de trabajo y la cinta de escritura comienzan con todos los ceros. La cinta de lectura comienza con un código de prefijo de entrada, seguido de todos los ceros.
• Sea el código sin prefijo en , utilizado por la máquina de Turing universal.${\estilo de visualización S}$${\estilo de visualización 2^{*}}$

Tenga en cuenta que algunas máquinas de Turing universales pueden no ser programables con códigos de prefijo. Debemos elegir solo una máquina de Turing universal sin prefijo.

La complejidad sin prefijo de una cadena es el código de prefijo más corto que genera la máquina :${\estilo de visualización x}$${\estilo de visualización x}$$${\displaystyle K(x):=\min\{|c|:c\in S,U(c)=x\}}$$

Existen algunos lenguajes de descripción que son óptimos en el sentido siguiente: dada cualquier descripción de un objeto en un lenguaje de descripción, dicha descripción puede utilizarse en el lenguaje de descripción óptimo con una sobrecarga constante. La constante depende únicamente de los lenguajes involucrados, no de la descripción del objeto ni del objeto que se describe.

A continuación se muestra un ejemplo de un lenguaje de descripción óptimo. Una descripción constará de dos partes:

• La primera parte describe otro lenguaje de descripción.
• La segunda parte es una descripción del objeto en ese idioma.

En términos más técnicos, la primera parte de una descripción es un programa de computadora (específicamente: un compilador para el lenguaje del objeto, escrito en el lenguaje de descripción), y la segunda parte es la entrada a ese programa de computadora que produce el objeto como salida.

El teorema de invariancia es el siguiente: dado cualquier lenguaje de descripción L , el lenguaje de descripción óptimo es al menos tan eficiente como L , con una sobrecarga constante.

Demostración: Cualquier descripción D en L puede convertirse en una descripción en el lenguaje óptimo describiendo primero L como un programa informático P (parte 1) y luego utilizando la descripción original D como entrada para ese programa (parte 2). La longitud total de esta nueva descripción D′ es (aproximadamente):

| D′ | = | P | + | D |

La longitud de P es una constante que no depende de D. Por lo tanto, hay como máximo una sobrecarga constante, independientemente del objeto descrito. Por lo tanto, el lenguaje óptimo es universal hasta esta constante aditiva.

Teorema : Si K ₁ y K ₂ son las funciones de complejidad relativas a los lenguajes de descripción completa de Turing L ₁ y L ₂ , entonces existe una constante c  – que depende únicamente de los lenguajes L ₁ y L ₂ elegidos – tal que

∀ s . − c ≤ K ₁ ( s ) − K ₂ ( s ) ≤ c .

Demostración : Por simetría, basta demostrar que existe alguna constante c tal que para todas las cuerdas s

K1 ( s ) ≤K2 ( _s ) + c ._​

Ahora, supongamos que hay un programa en el lenguaje L ₁ que actúa como intérprete de L ₂ :

función InterpretarLenguaje( cadena  p )

donde p es un programa en L ₂ . El intérprete se caracteriza por la siguiente propiedad:

Al ejecutarse InterpretLanguageen la entrada p se devuelve el resultado de ejecutar p .

Por lo tanto, si P es un programa en L ₂ que es una descripción mínima de s , entonces InterpretLanguage( P ) devuelve la cadena s . La longitud de esta descripción de s es la suma de

1. La longitud del programa InterpretLanguage, que podemos tomar como la constante c .
2. La longitud de P que por definición es K ₂ ( s ).

Esto demuestra el límite superior deseado.

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" ^[7] 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 Información y control . ^{[8] [9]}

Posteriormente, Andrey Kolmogorov publicó de forma independiente este teorema en Problems Inform. Transmission ^[10] en 1965. Gregory Chaitin también presenta este teorema en J. ACM  – el artículo de Chaitin fue presentado en octubre de 1966 y revisado en diciembre de 1968, y cita tanto los artículos de Solomonoff como de Kolmogorov. ^[11]

El teorema dice 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 permita cualquier otro algoritmo hasta una constante aditiva que depende de los algoritmos, pero no de las cadenas en sí. Solomonoff utilizó este algoritmo y las longitudes de código que permite para definir una "probabilidad universal" de una cadena en la que 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, incluidas la complejidad, la aleatoriedad y la información.

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

Existen otras variantes de la complejidad de Kolmogorov o información algorítmica. La más utilizada se basa en programas autodelimitados 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. ^[14]

Escribimos como , donde significa una forma fija de codificar una tupla de cadenas x e y.${\displaystyle K(x,y)}$${\displaystyle K((x,y))}$${\estilo de visualización (x,y)}$

Omitimos los factores aditivos de . Esta sección se basa en. ^[6]${\estilo de visualización O(1)}$

Teorema. ${\displaystyle C(x)\leq K(x)+2\log _{2}C(x)}$

Prueba. Tome cualquier programa para la máquina universal de Turing utilizada para definir la complejidad simple y conviértalo en un programa sin prefijo codificando primero la longitud del programa en binario, luego convirtiendo la longitud a codificación sin prefijo. Por ejemplo, supongamos que el programa tiene una longitud de 9, entonces podemos convertirlo de la siguiente manera: donde duplicamos cada dígito, luego agregamos un código de terminación. La máquina universal de Turing sin prefijo puede entonces leer cualquier programa para la otra máquina de la siguiente manera: La primera parte programa la máquina para simular la otra máquina, y es una sobrecarga constante . La segunda parte tiene una longitud . La tercera parte tiene una longitud .$${\displaystyle 9\mapsto 1001\mapsto 11-00-00-11-\color {rojo}{01}}$$$${\displaystyle [{\text{código para simular la otra máquina}}][{\text{longitud codificada del programa}}][{\text{el programa}}]}$$${\estilo de visualización O(1)}$$estilo de visualización \leq 2\log _{2}C(x)+3$${\estilo de visualización C(x)}$

Teorema : Existe tal que . Más sucintamente, . De manera similar, , y . ^{[ aclaración necesaria ]}${\estilo de visualización c}$${\displaystyle \para todo x,C(x)\leq |x|+c}$${\displaystyle C(x)\leq |x|}$${\displaystyle K(x)\leq |x|+2\log _{2}|x|}$${\displaystyle K(x||x|)\leq |x|}$

Prueba. Para la complejidad simple, basta con escribir un programa que simplemente copie la entrada en la salida. Para la complejidad sin prefijo, primero debemos describir la longitud de la cadena, antes de escribir la cadena en sí.

Teorema. (límites de información extra, subaditividad)

• ${\displaystyle K(x|y)\leq K(x)\leq K(x,y)\leq \max(K(x|y)+K(y),K(y|x)+K(x))\leq K(x)+K(y)}$

• ${\displaystyle K(xy)\leq K(x,y)}$

Tenga en cuenta que no hay forma de comparar and con or or or . Hay cadenas en las que es fácil describir toda la cadena, pero sus subcadenas son muy difíciles de describir.${\displaystyle K(xy)}$${\displaystyle K(x|y)}$${\displaystyle K(x)}$${\displaystyle K(y|x)}$${\displaystyle K(y)}$${\displaystyle xy}$

Teorema. (simetría de la información) .${\displaystyle K(x,y)=K(x|y,K(y))+K(y)=K(y,x)}$

Demostración. Un lado es simple. Para el otro lado con , necesitamos usar un argumento de conteo (página 38 ^[15] ). ${\displaystyle K(x,y)\geq K(x|y,K(y))+K(y)}$

Teorema. (no aumento de información) Para cualquier función computable , tenemos .${\displaystyle f}$${\displaystyle K(f(x))\leq K(x)+K(f)}$

Prueba. Programe la máquina de Turing para que lea dos programas sucesivos, uno que describa la función y otro que describa la cadena. Luego ejecute ambos programas en la cinta de trabajo para producir y escríbalo.${\displaystyle f(x)}$

A primera vista podría parecer trivial escribir un programa que pueda calcular K ( s ) para cualquier s , como el siguiente:

función KolmogorovComplexity( cadena s) para i = 1 hasta infinito: para cada cadena p de longitud exactamente i si isValidProgram(p) y evaluation(p) == s devuelve i

Este programa recorre todos los programas posibles (recorriendo todas las cadenas posibles y considerando solo aquellos que son programas válidos), comenzando por el más corto. Cada programa se ejecuta para encontrar el resultado producido por ese programa, comparándolo con la entrada s . Si el resultado coincide, se devuelve la longitud del programa.

Sin embargo, esto no funcionará porque algunos de los programas p probados no terminarán, por ejemplo, si contienen bucles infinitos. No hay forma de evitar todos estos programas probándolos de alguna manera antes de ejecutarlos debido a la no computabilidad del problema de detención .

Es más, ningún programa, por sofisticado que sea, puede calcular la función K. Esto se demuestra a continuación.

Teorema : Existen cadenas de complejidad de Kolmogorov arbitrariamente grande. Formalmente: para cada número natural n , existe una cadena s con K ( s ) ≥ n . ^{[nota 1]}

Prueba: De lo contrario, todas las infinitas cadenas finitas posibles podrían generarse mediante los finitos ^{[nota 2]} programas con una complejidad inferior a n bits.

Teorema : K no es una función computable . En otras palabras, no existe ningún programa que tome cualquier cadena s como entrada y produzca el entero K ( s ) como salida.

La siguiente prueba por contradicción utiliza un lenguaje simple similar a Pascal para denotar programas; para simplificar la prueba, suponga que su descripción (es decir, un intérprete ) tiene una longitud de1 400 000 bits. Supongamos por contradicción que existe un programa

Función Complejidad de Kolmogorov ( cadena s)

que toma como entrada una cadena s y devuelve K ( s ). Todos los programas tienen una longitud finita, por lo que, para simplificar la prueba, supongamos que es7 000 000 000 bits. Ahora, considere el siguiente programa de longitud1288 bits:

función GenerateComplexString() para i = 1 hasta infinito: para cada cadena s de longitud exactamente i si KolmogorovComplexity(s) ≥ 8000000000 devuelve s

Al usarlo KolmogorovComplexitycomo subrutina, el programa prueba cada cadena, comenzando con la más corta, hasta que devuelve una cadena con una complejidad de Kolmogorov de al menos8 000 000 000 bits, ^{[nota 3]} es decir, una cadena que no puede ser producida por ningún programa más corta que8 000 000 000 bits. Sin embargo, la longitud total del programa anterior que produjo s es de sólo7 001 401 288 bits, ^{[nota 4]} lo cual es una contradicción. (Si el código de KolmogorovComplexityes más corto, la contradicción persiste. Si es más largo, la constante utilizada en GenerateComplexStringsiempre se puede cambiar de manera apropiada.) ^{[nota 5]}

_{La prueba anterior utiliza una contradicción similar} a la de la paradoja de Berry : " ₁ El ₂ entero ₃ positivo ₄ más pequeño ₅ que ₆ no puede ₇ estar ₈ definido ₉ en ₁₀ menos ₁₁ que ₁₂ veinte ₁₃ palabras inglesas ". También es posible demostrar la no computabilidad de K por reducción a partir de la no computabilidad del problema de detención H , ya que K y H son equivalentes de Turing . ^[16]

Existe un corolario, llamado humorísticamente " teorema de pleno empleo " en la comunidad de lenguajes de programación, que establece que no existe un compilador perfecto que optimice el tamaño.

La regla de la cadena ^[17] para la complejidad de Kolmogorov establece que existe una constante c tal que para todos los X e Y :

K ( X , Y ) = K ( X ) + K ( Y | X ) + c*max(1,log( K ( X , Y )))).

Afirma 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. Usando esta afirmación, uno puede definir un análogo de información mutua para la complejidad de Kolmogorov .

Es sencillo calcular límites superiores para K ( s ): simplemente comprima la cadena s con algún método, implemente el descompresor correspondiente en el lenguaje elegido, concatene el descompresor a la cadena comprimida y mida la longitud de la cadena resultante, concretamente, el tamaño de un archivo autoextraíble en el lenguaje dado.

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

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 que esto sea preciso, fije un valor de n . Hay 2 ⁿ cadenas de bits de longitud n . La distribución de probabilidad uniforme en el espacio de estas cadenas de bits asigna un peso exactamente igual 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 exceden n − c está dado por la serie geométrica:

1 + 2 + 2 ² + ... + 2 ^{n − c} = 2 ^{n − c +1} − 1.

Quedan al menos

2n ^- 2n ^{- c +1} + ¹

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 se pueden describir de ninguna manera significativamente "comprimida". Sin embargo, resulta que el hecho de que una cadena específica sea compleja no se puede demostrar formalmente si la complejidad de la cadena es superior a un cierto umbral. La formalización precisa es la siguiente. Primero, fijemos un sistema axiomático particular S para los números naturales . El sistema axiomático tiene que 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 con base en una numeración de Gödel .

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

K ( s ) ≥ L       (como se formaliza en S )

puede probarse dentro de S. [ ^{18] [19]}

Idea de prueba : La prueba de este resultado se modela sobre una construcción autorreferencial utilizada en la paradoja de Berry . Primero 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 están dentro de las pruebas dentro de S de la declaración K ( x ) ≥ L . Al establecer entonces L a mayor que la longitud de este procedimiento P , tenemos que la longitud requerida de un programa para imprimir x como se establece en K ( x ) ≥ L como siendo al menos L es entonces menor que la cantidad L ya que la cadena x fue impresa por el procedimiento P . Esto es una contradicción. Por lo tanto, no es posible para el sistema de prueba S demostrar K ( x ) ≥ L para L arbitrariamente grande, en particular, para L mayor que la longitud del procedimiento P , (que es finito).

Prueba :

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

función NthProof( int  n )

que toma como entrada n y genera alguna prueba. Esta función enumera todas las pruebas. Algunas de ellas son pruebas para fórmulas que no nos interesan aquí, ya que cada prueba posible en el lenguaje de S se produce 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

función NthProofProvesComplexityFormula( int  n )

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

función StringNthProof( int  n )

función ComplejidadLímiteInferiorNthProof( int  n )

Considere el siguiente procedimiento:

función GenerateProvablyComplexString( int  n ) para i = 1 hasta infinito: si NthProofProvesComplexityFormula(i) y ComplexityLowerBoundNthProof(i) ≥ n  devuelve StringNthProof( i )

Dado un n , este procedimiento prueba cada prueba hasta que encuentra una cadena y una prueba en el sistema formal S de la fórmula K ( s ) ≥  L para algún L  ≥  n ; si no existe tal prueba, se repite eternamente.

Finalmente, considere el programa que consta de todas estas definiciones de procedimientos y una llamada principal:

Generar cadena probadamente compleja ( n 0 )

donde la constante n ₀ se determinará más adelante. La longitud total del programa se puede expresar como U +log ₂ ( n ₀ ), donde U es una constante y log ₂ ( n ₀ ) representa la longitud del valor entero n ₀ , bajo la suposición razonable de que está codificado en dígitos binarios. Elegiremos que n ₀ sea mayor que la longitud del programa, es decir, tal que n ₀ > U +log ₂ ( n ₀ ). Esto es claramente cierto para n ₀ suficientemente grande, porque el lado izquierdo crece linealmente en n ₀ mientras que el lado derecho crece logarítmicamente en n ₀ hasta la constante fija U .

Entonces no se puede obtener ninguna prueba de la forma " K ( s )≥ L " con L ≥ n _{0 en} S , como se puede ver mediante un argumento indirecto : Si ComplexityLowerBoundNthProof(i)pudiera devolver un valor ≥ n ₀ , entonces el bucle interno GenerateProvablyComplexStringeventualmente terminaría, 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 n ₀ , debe repetirse eternamente.

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

El principio de longitud mínima de mensaje de la inferencia estadística e inductiva y del aprendizaje automático fue desarrollado por CS Wallace y DM Boulton en 1968. El MML es bayesiano (es decir, incorpora creencias previas) y teórico de la información. Tiene las propiedades deseables de invariancia estadística (es decir, la inferencia se transforma con una re-parametrización, como de coordenadas polares a coordenadas cartesianas), consistencia estadística (es decir, incluso para problemas muy difíciles, el MML convergerá a cualquier modelo subyacente) y eficiencia (es decir, el modelo MML convergerá a cualquier modelo subyacente verdadero tan rápido como sea posible). CS Wallace y DL Dowe (1999) mostraron una conexión formal entre el MML y la teoría de la información algorítmica (o complejidad de Kolmogorov). ^[20]

La aleatoriedad de Kolmogorov define una cadena (generalmente de bits ) como aleatoria si y solo si cada programa de computadora que puede producir esa cadena es al menos tan largo como la cadena misma. Para que esto sea preciso, se debe especificar una computadora universal (o máquina universal de Turing ), de modo que "programa" signifique un programa para esta máquina universal. Una cadena aleatoria en este sentido es "incompresible" en el sentido de que es imposible "comprimir" la cadena en un programa que sea más corto que la cadena misma. Para cada computadora universal, hay al menos una cadena aleatoria algorítmicamente de cada longitud. ^[21] Sin embargo, si una cadena particular es aleatoria depende de la computadora universal específica que se elija. Esto se debe a que una computadora universal puede tener una cadena particular codificada en sí misma, y ​​un programa que se ejecuta en esta computadora universal puede simplemente hacer referencia a esta cadena codificada utilizando una secuencia corta de bits (es decir, mucho más corta que la cadena misma).

Esta definición se puede ampliar para definir una noción de aleatoriedad para secuencias infinitas de un alfabeto finito. Estas secuencias algorítmicamente aleatorias se pueden definir de tres formas equivalentes. Una forma utiliza un análogo efectivo de la teoría de la medida ; otra utiliza martingalas efectivas . La tercera forma define una secuencia infinita como aleatoria si la complejidad de Kolmogorov sin prefijo de sus segmentos iniciales crece lo suficientemente rápido: debe haber una constante c tal que la complejidad de un segmento inicial de longitud n sea siempre al menos n − c . Esta definición, a diferencia de la definición de aleatoriedad para una cadena finita, no se ve afectada por qué máquina universal se utiliza para definir la complejidad de Kolmogorov sin prefijo. ^[22]

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 se cumple para casi todas las trayectorias . ^[23]${\displaystyle K(x;T)=h(T)}$${\displaystyle x}$

Se puede demostrar ^[24] 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 (ya que la longitud de la salida tiende al infinito) a la entropía de la fuente.

Teorema. (Teorema 14.2.5 ^[25] ) La complejidad condicional de Kolmogorov de una cadena binaria satisface donde es la función de entropía binaria (que no debe confundirse con la tasa de entropía).${\displaystyle x_{1:n}}$$${\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)}$$${\displaystyle H_{b}}$

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

Si tenemos un oráculo de detención, entonces la complejidad de Kolmogorov de una cadena se puede calcular simplemente probando cada programa de detención, en orden lexicográfico, hasta que uno de ellos genere la cadena.

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

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

• Enumere todas las cadenas de longitud .${\textstyle \leq 2n+1}$

• Para cada una de esas cadenas , enumera todos los programas (sin prefijo) de longitud hasta que uno de ellos genere una salida . Registra su tiempo de ejecución .${\textstyle x}$${\displaystyle K(x)}$${\textstyle x}$${\textstyle n_{x}}$
• Generar el valor más grande .${\textstyle n_{x}}$

Demostramos por contradicción que para todo gran .${\textstyle p_{K}(n)\geq BB(n)}$${\textstyle n}$

Sea un Busy Beaver de longitud . Considere este programa (sin prefijo), que no requiere ninguna entrada:${\textstyle p_{n}}$${\displaystyle n}$

• Ejecute el programa y registre su duración de ejecución .${\textstyle p_{n}}$${\textstyle BB(n)}$

• Generar todos los programas con una longitud de . Ejecutar cada uno de ellos durante hasta pasos. Anotar las salidas de aquellos que se han detenido.${\textstyle \leq 2n}$${\textstyle BB(n)}$

• Imprime la cadena con el orden lexicográfico más bajo que no haya sido impresa por ninguno de ellos.

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

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

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

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

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

This section needs expansion. You can help by adding to it. (July 2014)

La complejidad de Kolmogorov condicional de dos cadenas se define, en términos generales, como la complejidad de Kolmogorov de x dado y como entrada auxiliar al procedimiento. ^{[28] [29]}${\displaystyle K(x|y)}$

También existe una complejidad condicional de longitud , que es la complejidad de x dada la longitud de x como se conoce/entra. ^{[30] [31]}${\displaystyle K(x|L(x))}$

• Paradoja de las bayas
• Código de 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
• La teoría de la inferencia inductiva de Solomonoff
• Entropía de muestra

• Blum, M. (1967). "Sobre el tamaño de las máquinas". Información y 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". Transactions of the Moscow Mathematical Society . 2 : 127–151.
• Portada, 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-0387339986.
• 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ítmica". Teoría y aplicaciones de la computabilidad . doi :10.1007/978-0-387-68441-3. ISBN 978-0-387-95567-4. ISSN  2190-619X.

• El legado de Andrei Nikolaevich Kolmogorov
• Publicaciones en línea de Chaitin
• Página de IDSIA de Solomonoff
• Generalizaciones de información algorítmica de J. Schmidhuber
• "Reseña de Li Vitányi 1997".
• Tromp, John. "El patio de juegos de cálculo lambda y lógica combinatoria de John".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-5 de M. Hutter : ISBN 3-540-22139-5  
• Longitud mínima del mensaje (MML) de David Dowe y las páginas de la navaja de Occam.
• 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.