Complejidad de Kolmogorov

Medida de complejidad algorítmica

Esta imagen ilustra parte del fractal del conjunto de Mandelbrot . Simplemente almacenar el color de 24 bits de cada píxel en esta imagen requeriría 23 millones de bytes, pero un pequeño programa de computadora puede reproducir estos 23 MB usando la definición del conjunto de Mandelbrot y las coordenadas de las esquinas de la imagen. Por tanto, la complejidad Kolmogorov de esta imagen es mucho menor que 23 MB en cualquier modelo pragmático de cálculo . La compresión de imágenes de propósito general de PNG solo la reduce a 1,6 MB, más pequeña que los datos sin procesar pero mucho mayor que la complejidad de Kolmogorov.

En la teoría algorítmica de la información (un subcampo de la informática y las matemáticas ), la complejidad 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 . Lleva el 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 se puede utilizar 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 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 (ver sección § Teorema de incompletitud de Chaitin); por tanto, ningún programa puede calcular la complejidad exacta de Kolmogorov para una infinidad de textos.

Definición

Intuición

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, a saber, "escribir ab 16 veces", que consta de 17 caracteres. El segundo no tiene una descripción simple obvia (usando el mismo juego de caracteres) aparte de escribir la cadena misma, es decir, "escribir 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 relativa a la elección del lenguaje de descripción se analiza más adelante). Se puede demostrar que la complejidad Kolmogorov de cualquier cadena no puede ser más que unos pocos bytes mayor que la longitud de la cadena misma. Las cadenas como el ejemplo de abab anterior, cuya complejidad 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 por simplicidad el alcance de este artículo se limita a cadenas. Primero debemos especificar un lenguaje de descripción para las cadenas. Un lenguaje de descripción de este tipo 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 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 una 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 :

la 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, el número de bits en la cadena mínima descripción) es la complejidad Kolmogorov de s , escrita K ( s ). Simbólicamente,

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

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

Complejidad simple de Kolmogorov C

Hay dos definiciones de complejidad de Kolmogorov: simple y sin prefijos . La complejidad simple es la longitud mínima de descripción de cualquier programa y se denota, 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 . La complejidad simple es más intuitiva, pero la complejidad sin prefijos es más fácil de estudiar. ${\displaystyle C(x)}$ ${\displaystyle K(x)}$

De forma predeterminada, todas las ecuaciones solo se mantienen hasta una constante aditiva. Por ejemplo, realmente significa que , es decir ,. ${\displaystyle f(x)=g(x)}$ ${\displaystyle f(x)=g(x)+O(1)}$ ${\displaystyle \exists c,\forall 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 sólo si, para cualquier computable , podemos codificar la función en un "programa" , tal que . Podemos pensar en 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^{*}\to 2^{*}}$ ${\displaystyle f:2^{*}\to 2^{*}}$ ${\displaystyle s_{f}}$ ${\displaystyle \forall x\in 2^{*},U(s_{f}x)=f(x)}$ ${\displaystyle U}$

Un problema con la simple complejidad es que , hablando intuitivamente, no existe una forma general de saber dónde dividir una cadena de salida con solo mirar la cadena concatenada. Podemos dividirlo especificando la longitud de o , pero eso requeriría símbolos adicionales. De hecho, para cualquiera existe tal que . ^[3] ${\displaystyle C(xy)\not <C(x)+C(y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle O(\min(\ln x,\ln y))}$ ${\displaystyle c>0}$ ${\displaystyle 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 sin prefijo solo tienen . ${\displaystyle O(\min(\ln x,\ln y))}$ ${\displaystyle O(1)}$

El principal problema con la simple complejidad es que hay algo extra escondido en un 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, por lo que no estamos usando 2 símbolos, sino 3. Para solucionar este defecto, introducimos la complejidad de Kolmogorov sin prefijos. ^[4] ${\displaystyle x}$ ${\displaystyle \log _{2}|x|}$

Complejidad Kolmogorov K sin prefijo

Un código sin prefijo es un subconjunto de tal que, dadas dos palabras diferentes en el conjunto, ninguna es un prefijo de la otra. El beneficio de un código sin prefijos es que podemos construir una máquina que lee palabras del código en una dirección, y tan pronto como lee el último símbolo de la palabra, sabe que la palabra está terminada y no necesidad de retroceder o un símbolo de terminación. ${\displaystyle 2^{*}}$ ${\displaystyle x,y}$

Defina una máquina de Turing sin prefijos como una máquina de Turing que viene con un código sin prefijos, de modo que la máquina de Turing pueda leer cualquier cadena del código en una dirección y dejar de leer tan pronto como lea el último símbolo. Posteriormente, 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. ^[5]

• Arreglar una máquina de Turing universal sin prefijos, 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 de 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 ceros. La cinta leída comienza con un código de prefijo de entrada, seguido de ceros.
• Sea el código sin prefijo en , utilizado por la máquina universal de Turing. ${\displaystyle S}$ ${\displaystyle 2^{*}}$

Tenga en cuenta que es posible que algunas máquinas de Turing universales no sean programables con códigos de prefijo. Debemos elegir sólo una máquina de Turing universal sin prefijos.

La complejidad sin prefijos de una cadena es el código de prefijo más corto que genera la máquina : ${\displaystyle x}$ ${\displaystyle x}$

$${\displaystyle K(x):=\min\{|c|:c\in S,U(c)=x\}}$$

Teorema de invariancia

Trato informal

Hay algunos lenguajes de descripción que son óptimos, en el siguiente sentido: dada cualquier descripción de un objeto en un lenguaje de descripción, dicha descripción puede usarse en el lenguaje de descripción óptimo con una sobrecarga constante. La constante depende sólo 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 tendrá 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), siendo la segunda parte 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.

Prueba: cualquier descripción D en L se puede convertir en una descripción en el lenguaje óptimo describiendo primero L como un programa de computadora P (parte 1) y luego usando 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 mucho una sobrecarga constante, independientemente del objeto descrito. Por tanto, el lenguaje óptimo es universal hasta esta constante aditiva.

Un trato más formal

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

∀ s . - C ≤ K ₁ ( s ) - K ₂ ( s ) ≤ C .

Prueba : Por simetría, basta demostrar que existe una constante c tal que para todas las cuerdas s

K ₁ ( s ) ≤ K ₂ ( s ) + c .

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

función InterpretLanguage ( cadena  p )

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

Ejecutar InterpretLanguageen la entrada p 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.

Historia y contexto

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 y lo describió en "Un informe preliminar sobre una teoría general de la inferencia inductiva" ^[6] como parte de su invención de la complejidad algorítmica . probabilidad . 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 . ^{[7] [8]}

Andrey Kolmogorov publicó más tarde de forma independiente este teorema en Problems Inform. Transmisión ^[9] 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 los artículos de Solomonoff y Kolmogorov. ^[10]

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 lo 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 posteriores 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ó la prioridad de Solomonoff. ^[11] Durante varios años, el trabajo de Solomonoff fue más conocido en la Unión Soviética que en el mundo occidental. El consenso general en la comunidad científica, sin embargo, fue asociar este tipo de complejidad con Kolmogorov, quien estaba preocupado por 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 previa universal. . El área más amplia que abarca la complejidad descriptiva y la probabilidad a menudo se denomina complejidad de Kolmogorov. El informático Ming Li considera esto un ejemplo del efecto Matthew : "...a todo el que tenga, se le dará más..." ^[12]

Existen varias otras variantes de la complejidad de Kolmogorov o de la información algorítmica. El más utilizado 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. ^[13]

Resultados básicos

Escribimos to be , donde significa alguna forma fija de codificar una tupla de cadenas xey. ${\displaystyle K(x,y)}$ ${\displaystyle K((x,y))}$ ${\displaystyle (x,y)}$

Desigualdades

Omitimos factores aditivos de . Esta sección se basa en. ^[5] ${\displaystyle 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 prefijos codificando primero la longitud del programa en binario y luego convierta la longitud a codificación sin prefijos. Por ejemplo, supongamos que el programa tiene una longitud de 9, entonces podemos convertirlo de la siguiente manera:

$${\displaystyle 9\mapsto 1001\mapsto 11-00-00-11-\color {red}{01}}$$

$${\displaystyle [{\text{code for simulating the other machine}}][{\text{coded length of the program}}][{\text{the program}}]}$$

${\displaystyle O(1)}$ ${\displaystyle \leq 2\log _{2}C(x)+3}$ ${\displaystyle C(x)}$

Teorema : Existe tal que . Más sucintamente, . De manera similar, , y . ^{[ se necesita aclaración ]} ${\displaystyle c}$ ${\displaystyle \forall 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 mayor complejidad, simplemente escriba un programa que simplemente copie la entrada en la salida. Para la complejidad sin prefijos, primero debemos describir la longitud de la cadena, antes de escribir la cadena misma.

Teorema. (límites de información adicional, 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 or or or . Hay cadenas tales que la cadena completa es fácil de describir, 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 información) . ${\displaystyle K(x,y)=K(x|y,K(y))+K(y)=K(y,x)}$

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

Teorema. (información no aumenta) 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 posteriores, 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)}$

Incomputabilidad de la complejidad de Kolmogorov

Un intento ingenuo de un programa para calcular K

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 el infinito: para cada cadena p de longitud exactamente i si isValidProgram(p) y evalua(p) == s devuelve i

Este programa itera a través de todos los programas posibles (iterando a través de 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 las entradas . Si el resultado coincide, se devuelve la duración del programa.

Sin embargo, esto no funcionará porque algunos de los programas 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 puede calcular la función K , por muy sofisticada que sea. Esto se demuestra a continuación.

Prueba formal de incomputabilidad de K

Teorema : Existen cadenas de complejidad 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 ser generadas por un número finito de programas ^{[nota 2]} 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 una cadena s como entrada y produzca el número entero K ( s ) como salida.

La siguiente prueba por contradicción utiliza un lenguaje simple tipo Pascal para denotar programas; Para simplificar la prueba, supongamos que su descripción (es decir, un intérprete ) tiene una longitud de1.400.000 bits .​ Supongamos por contradicción que hay un programa.

función KolmogorovComplejidad ( cadena s)

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

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

Utilizando KolmogorovComplexitycomo subrutina, el programa prueba cada cadena, comenzando por la más corta, hasta que devuelve una cadena con al menos complejidad de Kolmogorov.8 000 000 000 bits, ^{[nota 3]} es decir, una cadena que no puede ser producida por ningún programa más corto que8.000.000.000 bits .​​ Sin embargo, la duración total del programa anterior que produjo s es 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 apropiadamente.) ^{[nota 5]}

La prueba anterior utiliza una contradicción similar a la de la paradoja de Berry : " ₁ El ₂ más pequeño ₃ positivo ₄ entero ₅ que _{6 no 7} puede ser ₈ definido ₉ en ₁₀ menos ₁₁ que ₁₂ veinte _{13 14} palabras en inglés ". También es posible mostrar la no computabilidad de K mediante la reducción de la no computabilidad del problema de detención H , ya que K y H son equivalentes de Turing . ^[15]

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

Regla de la cadena para la complejidad de Kolmogorov

La regla de la cadena ^[16] para la complejidad de Kolmogorov establece que

K ( X , Y ) = K ( X ) + K ( Y | X ) + O (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, se puede definir un análogo de información mutua para la complejidad de Kolmogorov .

Compresión

Es sencillo calcular los límites superiores para K ( s ): simplemente comprima la cadena s con algún método, implemente el descompresor correspondiente en el idioma 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 idioma dado.

Una cadena s es comprimible por un número c si tiene una descripción cuya longitud no exceda | s | − c bits. Esto equivale a decir que K ( s ) ≤ | s | −c .​ De lo contrario, s es incompresible por c . Se dice que una cadena incompresible por 1 es simplemente incompresible  : según el principio del casillero , que se aplica porque cada cadena comprimida se asigna a solo una cadena no comprimida, deben existir cadenas incompresibles , ya que hay cadenas de 2 ⁿ 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 pueden comprimirse 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 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 probar el teorema, tenga en cuenta que el número de descripciones de longitud que no exceden n − c viene dado por la serie geométrica:

1 + 2 + 2 ² + ... + 2 ^{norte - do} = 2 ^{norte - do +1} - 1.

Quedan al menos

2 ^norte - 2 ^{norte - c +1} + 1

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

Teorema de incompletitud de Chaitin

Complejidad de Kolmogorov K ( s ) , y dos funciones computables de límite inferior prog1(s). prog2(s)El eje horizontal ( escala logarítmica ) enumera todas las cadenas s , ordenadas por longitud; el eje vertical ( escala lineal ) mide la complejidad de Kolmogorov en bits . La mayoría de las cuerdas son incompresibles, es decir, su complejidad Kolmogorov excede su longitud en una cantidad constante. En la imagen se muestran 9 cuerdas comprimibles, que aparecen como pendientes casi verticales. Debido al teorema de incompletitud de Chaitin (1974), la salida de cualquier programa que calcule un límite inferior de la complejidad de Kolmogorov no puede exceder algún límite fijo, que es independiente de la cadena de entrada s .

Según el teorema anterior (§ Compresión), la mayoría de las cuerdas 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 se puede probar formalmente si la complejidad de la cadena está por encima de un cierto umbral. La formalización precisa es la siguiente. Primero, fije 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 cuerdas, 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 a partir de 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 formalizado en S )

se puede probar dentro de S . ^{[17] [18]}

Idea de prueba : La prueba de este resultado se basa en 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 número entero L e imprime las cadenas x que están dentro de las pruebas dentro de S del enunciado K ( x ) ≥ L. Luego, configurando L como 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 ya que la cadena x fue impreso por el procedimiento P . Esto es una contradicción. Por lo tanto, no es posible que el sistema de prueba S demuestre que K ( x ) ≥ L para L es arbitrariamente grande, en particular, para L mayor que la duración 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 estas son pruebas de fórmulas que no nos interesan aquí, ya que todas las pruebas posibles en el lenguaje de S se producen 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 )

lo que determina si la enésima prueba realmente prueba una fórmula de complejidad K ( s ) ≥  L . Las cadenas s y el número entero L a su vez son computables mediante el procedimiento:

función StringNthProof ( int  n )

función ComplejidadLowerBoundNthProof( int  n )

Considere el siguiente procedimiento:

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

Dado un n , este procedimiento prueba todas las pruebas hasta encontrar 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 para siempre.

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

GenerarProvablyComplexString( 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 puede verse 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 para siempre.

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

Longitud mínima del mensaje

El principio de longitud mínima de mensaje de inferencia estadística e inductiva y aprendizaje automático fue desarrollado por CS Wallace y DM Boulton en 1968. 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 reparametrización, como de coordenadas polares a coordenadas cartesianas), consistencia estadística (es decir, incluso para problemas muy difíciles, MML convergerá a cualquier modelo subyacente) y eficiencia ( es decir, el modelo MML convergerá a cualquier modelo subyacente verdadero lo más rápido posible). CS Wallace y DL Dowe (1999) mostraron una conexión formal entre MML y la teoría algorítmica de la información (o complejidad de Kolmogorov). ^[19]

aleatoriedad de Kolmogorov

La aleatoriedad de Kolmogorov define una cadena (generalmente de bits ) como aleatoria si y sólo 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 de Turing universal ), 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 algorítmicamente aleatoria de cada longitud. ^[20] 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 entonces simplemente hacer referencia a esta cadena codificada usando 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 eficaz de la teoría de la medida ; otro utiliza efectivas martingalas . La tercera forma define una secuencia infinita como aleatoria si la complejidad 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 prefijos. ^[21]

Relación con la entropía

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 la igualdad se cumple para casi todos . ^[22] ${\displaystyle K(x;T)=h(T)}$ ${\displaystyle x}$

Se puede demostrar ^[23] 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 Kolmogorov de la salida de una fuente de información de Markov, normalizada por la longitud de la salida, converge casi con seguridad (a medida que la longitud de la salida llega al infinito) a la entropía de la fuente.

Teorema. (Teorema 14.2.5 ^[24] ) La complejidad condicional de Kolmogorov de una cadena binaria satisface ${\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)}$$

función de entropía binaria ${\displaystyle H_{b}}$

Problema de detención

La función de complejidad de Kolmogorov equivale a resolver el problema de detención.

Si tenemos un oráculo de detención, entonces la complejidad 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 complicada. ^{[25] [26]} Muestra que dada una función de complejidad de Kolmogorov, podemos construir una función tal que para todos los grandes , ¿dónde está la función Busy Beaver? ^{[ aclarar ]} . Modificando la función en valores más bajos de obtenemos un límite superior en , lo que resuelve el problema de la detención. ${\displaystyle p}$ ${\displaystyle p(n)\geq BB(n)}$ ${\displaystyle n}$ ${\displaystyle BB}$ ${\displaystyle n}$ ${\displaystyle BB}$

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

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

• Para cada una de estas cadenas , enumere todos los programas (sin prefijos) de longitud hasta que uno de ellos genere resultados . Registre su tiempo de ejecución . ${\textstyle x}$ ${\displaystyle K(x)}$ ${\textstyle x}$ ${\textstyle n_{x}}$
• Salida el más grande . ${\textstyle n_{x}}$

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

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

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

• Genera todos los programas con longitud . Ejecute cada uno de ellos hasta alcanzar los pasos. Tenga en cuenta las salidas de aquellos que se han detenido. ${\textstyle \leq 2n}$ ${\textstyle BB(n)}$

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

Sea la cadena generada por el programa . ${\textstyle x}$

El programa tiene longitud , de donde proviene la longitud de Busy Beaver , proviene del uso del código delta de Elias (sin prefijo) para el número y proviene del resto del programa. Por lo tanto, ${\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}$$

principio de casillero ${\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}$

probabilidad universal

Arreglar una máquina de Turing universal , la misma que se usó para definir la complejidad (sin prefijos) de Kolmogorov. Defina la probabilidad universal (sin prefijo) de que una cadena sea ${\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 momento después de leer el segmento inicial , sin leer ninguna entrada adicional, y que, cuando se detenga, habrá escrito en la cinta de salida. ${\displaystyle U(p)=x}$ ${\displaystyle p000\cdots }$ ${\displaystyle p}$ ${\displaystyle x}$

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

Versiones condicionales

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

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

Ver también

• Paradoja de las bayas
• código de golf
• Compresión de datos
• Teoría descriptiva de la complejidad
• 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

Notas

1. Sin embargo, no es necesario que exista una s con K ( s ) = n para cada n . Por ejemplo, si n no es múltiplo de 7, ningún programa ASCII puede tener una longitud exacta de n bits.
2. Hay 1 + 2 + 2 ² + 2 ³ + ... + 2 ⁿ = 2 ^{n +1} − 1 textos de programa diferentes de longitud hasta n bits; cf. series geométricas . Si la longitud de los programas debe ser múltiplo de 7 bits, existen aún menos textos de programa.
3. Según el teorema anterior, dicha cadena existe, por lo tanto, el forbucle eventualmente terminará.
4. incluido el intérprete de idioma y el código de subrutina paraKolmogorovComplexity
5. Si KolmogorovComplexitytiene una longitud de n bits, la constante m utilizada GenerateComplexStringdebe adaptarse para satisfacer n +1 400 000 +1218 + 7·log ₁₀ ( m ) < m , lo cual siempre es posible ya que m crece más rápido que log ₁₀ ( m ).
6. Como hay N _L = 2 ^L cadenas de longitud L , el número de cadenas de longitud L = 0, 1, ..., n − 1 es N ₀ + N ₁ + ... + N _{n −1} = 2 ⁰ + 2 ¹ + ... + 2 ^{n −1} , que es una serie geométrica finita con suma 2 ⁰ + 2 ¹ + ... + 2 ^{n −1} = 2 ⁰ × (1 − 2 ⁿ ) / (1 − 2) = 2 ^norte - 1

Referencias

1. Kolmogorov, Andrey (1963). "Sobre tablas de números aleatorios". Sankhya Ser. A . 25 : 369–375. SEÑOR  0178484.
2. Kolmogorov, Andrey (1998). "Sobre tablas de números aleatorios". Informática Teórica . 207 (2): 387–395. doi : 10.1016/S0304-3975(98)00075-9 . SEÑOR  1643414.
3. (Downey y Hirschfeldt, 2010), Teorema 3.1.4
4. (Downey y Hirschfeldt, 2010), Sección 3.5
5. Hutter, Marcus (6 de marzo de 2007). "Teoría de la información algorítmica". Scholarpedia . 2 (3): 2519. doi : 10.4249/scholarpedia.2519. hdl : 1885/15015 . ISSN  1941-6016.
6. Solomonoff, Ray (4 de febrero de 1960). Un informe preliminar sobre una teoría general de la inferencia inductiva (PDF) . Informe V-131 (Informe). Revisión publicada en noviembre de 1960. Archivado (PDF) desde el original el 9 de octubre de 2022.
7. Solomonoff, Ray (marzo de 1964). "Una teoría formal de la inferencia inductiva, parte I" (PDF) . Información y Control . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 . Archivado (PDF) desde el original el 9 de octubre de 2022.
8. Solomonoff, Ray (junio de 1964). "Una teoría formal de la inferencia inductiva, parte II" (PDF) . Información y Control . 7 (2): 224–254. doi : 10.1016/S0019-9958(64)90131-7 . Archivado (PDF) desde el original el 9 de octubre de 2022.
9. Kolmogorov, AN (1965). "Tres enfoques para la definición cuantitativa de información". Informe de problemas. Transmisión . 1 (1): 1–7. Archivado desde el original el 28 de septiembre de 2011.
10. Chaitin, Gregory J. (1969). "Sobre la simplicidad y velocidad de los programas para calcular conjuntos infinitos de números naturales". Revista de la ACM . 16 (3): 407–422. CiteSeerX 10.1.1.15.3821 . doi :10.1145/321526.321530. S2CID  12584692. 
11. Kolmogorov, A. (1968). "Base lógica de la teoría de la información y la teoría de la probabilidad". Transacciones IEEE sobre teoría de la información . 14 (5): 662–664. doi :10.1109/TIT.1968.1054210. S2CID  11402549.
12. Li, Ming; Vitányi, Paul (2008). "Preliminares". Introducción a la complejidad de Kolmogorov y sus aplicaciones . Textos en Informática. págs. 1–99. doi :10.1007/978-0-387-49820-1_1. ISBN 978-0-387-33998-6.
13. Burgin, M. (1982). "Complejidad y dualidad generalizada de Kolmogorov en la teoría de los cálculos". Avisos de la Academia de Ciencias de Rusia . 25 (3): 19-23.
14. Hutter, Marcus (2005). Inteligencia artificial universal: decisiones secuenciales basadas en probabilidad algorítmica . Textos de informática teórica. Berlín Nueva York: Springer. ISBN 978-3-540-26877-2.
15. Dicho sin pruebas en: PB Miltersen (2005). "Notas del curso de compresión de datos: complejidad de Kolmogorov" (PDF) . pag. 7. Archivado desde el original (PDF) el 9 de septiembre de 2009.
16. Zvonkin, A.; L. Levin (1970). "La complejidad de los objetos finitos y el desarrollo de los conceptos de información y aleatoriedad mediante la teoría de algoritmos" (PDF) . Encuestas matemáticas rusas . 25 (6): 83-124. Código bibliográfico : 1970RuMaS..25...83Z. doi :10.1070/RM1970v025n06ABEH001269. S2CID  250850390.
17. Gregory J. Chaitin (julio de 1974). "Limitaciones teóricas de la información de los sistemas formales" (PDF) . Revista de la ACM . 21 (3): 403–434. doi :10.1145/321832.321839. S2CID  2142553.Aquí: Thm.4.1b
18. Calude, Cristian S. (12 de septiembre de 2002). Información y aleatoriedad: una perspectiva algorítmica. Saltador. ISBN 9783540434665.
19. Wallace, CS; Dowe, DL (1999). "Longitud mínima del mensaje y complejidad de Kolmogorov". Diario de informática . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . doi : 10.1093/comjnl/42.4.270. 
20. Hay 2 ⁿ cadenas de bits de longitud n , pero solo 2 ⁿ -1 cadenas de bits más cortas, por lo que, como máximo, se produce esa compresión.
21. Martin-Löf, Per (1966). "La definición de secuencias aleatorias". Información y Control . 9 (6): 602–619. doi : 10.1016/s0019-9958(66)80018-9 .
22. Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal (2010). «Dinámica simbólica efectiva, puntos aleatorios, comportamiento estadístico, complejidad y entropía» (PDF) . Información y Computación . 208 : 23–41. arXiv : 0801.0209 . doi :10.1016/j.ic.2009.05.001. S2CID  5555443. Archivado (PDF) desde el original el 9 de octubre de 2022.
23. Alexei Kaltchenko (2004). "Algoritmos para la estimación de la distancia de la información con aplicación a la bioinformática y la lingüística". arXiv : cs.CC/0404039 .
24. Portada, Thomas M.; Thomas, alegría A. (2006). Elementos de la teoría de la información (2ª ed.). Wiley-Interscience. ISBN 0-471-24195-4.
25. Chaitín, G.; Arslanov, A.; Calude, Cristian S. (1 de septiembre de 1995). "La complejidad del tamaño del programa calcula el problema de la detención". Toro. EATCS .
26. Li, Ming; Vitányi, Paul (2008). "Una introducción a la complejidad de Kolmogorov y sus aplicaciones". Textos en Informática . Ejercicio 2.7.7. doi :10.1007/978-0-387-49820-1. ISSN  1868-0941.
27. Jorma Rissanen (2007). Información y complejidad en la modelización estadística . Springer S. p. 53.ISBN​ 978-0-387-68812-1.
28. Ming Li; Paul MB Vitányi (2009). Introducción a la complejidad de Kolmogorov y sus aplicaciones . Saltador. págs. 105-106. ISBN 978-0-387-49820-1.
29. Ming Li; Paul MB Vitányi (2009). Introducción a la complejidad de Kolmogorov y sus aplicaciones . Saltador. pag. 119.ISBN​ 978-0-387-49820-1.
30. Vitányi, Paul MB (2013). "Complejidad condicional de Kolmogorov y probabilidad universal". Informática Teórica . 501 : 93-100. arXiv : 1206.0983 . doi :10.1016/j.tcs.2013.07.009. S2CID  12085503.

Otras lecturas

• 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). "La entropía y la complejidad de las trayectorias de un sistema dinámico". Transacciones de la Sociedad Matemática de Moscú . 2 : 127-151.
• Portada, Thomas M.; Thomas, alegría 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. ISSN  2190-619X.

enlaces externos

• El legado de Andrei Nikolaevich Kolmogorov
• Publicaciones en línea de Chaitin
• Página IDSIA de Solomonoff
• Generalizaciones de información algorítmica por J. Schmidhuber
• "Revisión de Li Vitányi 1997".
• Tromp, Juan. "Zona de juegos de lógica combinatoria y cálculo Lambda de John".El modelo informático de cálculo lambda de Tromp ofrece una definición concreta de K()]
• IA universal basada en la complejidad de Kolmogorov ISBN 3-540-22139-5 por M. Hutter : ISBN 3-540-22139-5  
• Longitud mínima de mensaje (MML) de David Dowe y páginas de la navaja de Occam.
• Grunwald, P.; Pitt, MA (2005). Myung, IJ (ed.). Avances en la longitud mínima de la descripción: teoría y aplicaciones . Prensa del MIT. ISBN 0-262-07262-9.