Complejidad de Kolmogorov

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de abril de 2022; las comprobaciones requieren 2 ediciones .

En la teoría algorítmica de la información, la complejidad de Kolmogorov de un objeto (como un texto) es una medida de los recursos computacionales necesarios para definir con precisión ese objeto.

La complejidad de Kolmogorov también se conoce como complejidad descriptiva, complejidad de Kolmogorov -Khaitin , complejidad estocástica , entropía algorítmica o complejidad algorítmica .

Expresa la posibilidad de una descripción fractal.

Por ejemplo, considere dos cadenas que tienen 64 caracteres y solo contienen caracteres en minúsculas y números:

ababababababababababababababababababababababababababababababababababababa 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

La primera línea tiene una descripción simple en lenguaje natural, es decir, ab 32 veces , que consta de 10 caracteres. La segunda línea no tiene una descripción simple obvia que use el mismo conjunto de caracteres que la propia línea, que tiene 64 caracteres.

Más formalmente, la complejidad de una cadena es la longitud de la descripción de esa cadena en algún lenguaje de descripción universal . La capacidad de la complejidad para cambiar con respecto a la elección del lenguaje de descripción se analiza a continuación. Se puede demostrar que la complejidad de Kolmogorov de cualquier cadena no puede ser más de unos pocos bytes más que la longitud de la propia cadena. Las cadenas cuya complejidad de Kolmogorov depende débilmente del tamaño de la cadena en sí no se consideran complejas.

Definición

Para definir la complejidad de Kolmogorov, primero debemos definir el lenguaje de descripción de cadenas. Tal lenguaje de descripción puede estar basado en cualquier lenguaje de programación como Lisp , Pascal o Java . Si es un programa cuya salida es la cadena , entonces es una descripción de . La longitud de la descripción es la longitud como una cadena. En el curso de la determinación de la longitud , las longitudes de las subrutinas utilizadas en . La longitud de cualquier constante entera que aparece en es el número de bits necesarios para representar , que es (aproximadamente) . $PAGS$ $X$ $PAGS$ $X$ $PAGS$ $PAGS$ $PAGS$ $norte$ $PAGS$ $norte$ $\ log _ {2} n$

Alternativamente, podemos elegir una codificación para la máquina de Turing , donde la codificación es una función que asigna cada máquina de Turing a una cadena de bits . Si es una máquina de Turing que da una cadena como entrada , entonces la cadena combinada es una descripción para . Este es un enfoque teórico que es más adecuado para construir pruebas formales detalladas y es el preferido en la literatura de investigación. El cálculo lambda binario puede dar la definición más simple de complejidad. En este artículo, adoptamos un enfoque informal. $METRO$ $\langle M\rangle$ $METRO$ $w$ $X$ $\ ángulo M \ ángulo w$ $X$

Cualquier línea tiene al menos una descripción, es decir, un programa $s$

función GenerateFixedString() devuelve s

Si la descripción tiene una longitud mínima, es decir, utiliza la menor cantidad de caracteres, entonces se denomina descripción mínima y la longitud , es decir, la cantidad de caracteres en esta descripción, es la complejidad de Kolmogorov . Simbólicamente: $s$ $d(s)$ $s$ $d(s)$ $s$ $Kansas)$

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

Consideremos cómo la elección del lenguaje de descripción afecta el valor de y mostremos que el efecto de cambiar el lenguaje de descripción es limitado. $k$

teorema _ Si y son funciones de complejidad relacionadas con los lenguajes de descripción y , entonces existe una constante (que depende solo de los lenguajes y ) tal que $K_1$ $K_{2}$ $L_{1}$ $L_{2}$ $C$ $L_{1}$ $L_{2}$

\forall s|K_{1}(s)-K_{2}(s)|\leqslant c.

prueba _ A la inversa, basta con probar que existe alguna constante tal que para todas las cadenas de bits $C$ $s$

K_{1}(s)\leqslant K_{2}(s)+c.

Supongamos que hay un programa en el lenguaje que actúa como intérprete para : $L_{1}$ $L_{2}$

función InterpretarIdioma ( cadena p )

¿ Dónde está el programa de idiomas ? El intérprete se caracteriza por la siguiente propiedad: $pags$ $L_{2}$

El valor devuelto como resultado del trabajo InterpretLanguageen los datos de entrada será el resultado del trabajo .

pags

pags

Por lo tanto, si es un programa en un idioma que es la descripción mínima de , entonces ( ) devuelve una cadena . La longitud de esta descripción es la suma: $PAGS$ $L_{2}$ $s$ InterpretLanguage $PAGS$ $s$ $s$

La duración del programa InterpretLanguage, que se puede tomar como una constante . $C$
La longitud definida por . $PAGS$ $K_{2}(s)$

Esto prueba el límite superior requerido.

Historia y contexto

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

La idea de la teoría de la complejidad de Kolmogorov se basa en un teorema clave descubierto por primera vez por Ray Solomonoff , quien lo publicó en 1960, describiéndolo en A Preliminary Report on a General Theory of Inductive Inference [1] como parte de su invención de la probabilidad algorítmica . . Dio una descripción más completa en sus publicaciones "Una teoría formal de la inferencia inductiva" , parte 1 y 2 en la revista Información y control [2] [3] , realizada en 1964.

Posteriormente , A. N. Kolmogorov publicó de forma independiente este teorema en la revista Information Transmission Problems [4] , Gregory Khaitin también presentó este teorema en la revista J. ACM" . El artículo de Khaitin se envió en octubre de 1966, se revisó en diciembre de 1968 y cita los artículos de Solomonoff y Kolmogorov. [5]

El teorema establece que entre los algoritmos que restauran (decodifican) cadenas a partir de sus descripciones (códigos), existe uno óptimo. Este algoritmo para todas las cadenas proporciona los mismos códigos cortos que los proporcionados por otros algoritmos, con la diferencia de una constante que depende del algoritmo, pero no de la cadena en sí. Solomonoff usó este algoritmo y las longitudes de código que proporcionó para determinar la "probabilidad universal" de las cadenas, en la que se podría basar la inferencia inductiva de los caracteres posteriores en una cadena. Kolmogorov usó este teorema para definir varias funciones de cadenas: complejidad, aleatoriedad e información.

Cuando Kolmogorov se enteró del trabajo de Solomonoff, reconoció su prioridad [6] . Durante varios años, el trabajo de Solomonoff fue más conocido en la URSS que en Occidente. Sin embargo, es común en la comunidad científica asociar este tipo de complejidad con Kolmogorov, quien hablaba de la aleatoriedad de las secuencias, mientras que la probabilidad algorítmica se ha asociado con Solomonoff, quien se centró en la predicción utilizando su descubrimiento de la distribución de probabilidad previa universal.

Hay algunas otras variantes de la complejidad de Kolmogorov o información algorítmica. Uno de los más utilizados se basa en programas autolimitantes y se asocia principalmente con L. A. Levin (1974). M. Burgin (1982) introdujo un enfoque axiomático de la complejidad de Kolmogorov basado en los axiomas de Bloom (1967 ).

Algunas personas piensan que el nombre "complejidad de Kolmogorov" es un ejemplo del efecto Mateo [7] .

Principales consecuencias

En el siguiente razonamiento, por nos referimos a la complejidad de la cadena . $Kansas)$ $s$

Es fácil ver que la descripción mínima de una cadena no puede ser mayor que la propia cadena: el programa anterior GenerateFixedString, cuya salida es mayor en una cantidad fija. $s$ $s$

teorema _ Existe una constante tal que $C$

\forall s\,K(s)\leqslant |s|+c.

Incomputabilidad de la complejidad de Kolmogorov

La primera consecuencia es que no existe una forma eficiente de calcular . $k$

teorema _ es una función no computable . $k$

En otras palabras, el problema de calcular la complejidad algorítmica de una cadena arbitraria no tiene solución algorítmica : no existe ningún programa que tome como entrada y salida un número entero . Mostremos esto con una contradicción creando un programa que crea una cadena que solo puede ser creada por un programa más largo. Supongamos que hay un programa $s$ $s$ $Kansas)$

función KolmogorovComplexity( cadena s )

que toma como entrada y devuelve . Ahora considere el programa $s$ $Kansas)$

función GenerateComplexString( int n ) for i = 1 to infinity: para cada cadena s de longitud exactamente i si KolmogorovComplexity( s ) >= n return s quit

Este programa llama a una subrutina KolmogorovComplexity. El programa prueba cada línea, empezando por la más corta, hasta que encuentra una línea con complejidad al menos , que devuelve. Por lo tanto, dado cualquier número entero positivo , produce una cadena con complejidad de Kolmogorov al menos . Este programa tiene su propia duración fija . La entrada del programa es un número entero y el tamaño se mide por el número de bits necesarios para representarlo, que es . A continuación, considere el siguiente programa: $norte$ $norte$ $norte$ $tu$ GenerateComplexString $norte$ $norte$ $\ log _ {2} n$

función GenerarCadenaParadójica() devuelve GenerarCadenaCompleja(n 0 )

Este programa llama GenerateComplexStringcomo una subrutina y también tiene un parámetro libre . Este programa genera una cadena cuya complejidad es al menos . Con una elección favorable del parámetro, llegamos a una contradicción. Para elegir este valor, tenga en cuenta que está descrito por un programa cuya longitud no es mayor que $n_ {0}$ $s$ $n_ {0}$ $n_ {0}$ $s$ GenerateParadoxicalString

U+\log _{2}n_{0}+C,

donde se suma la constante debido al programa . Como crece más rápido que , existe un valor tal que $C$ GenerateParadoxicalString $norte$ $\ log _ {2} n$ $n_ {0}$

U+\log _{2}n_{0}+C<n_{0}.

Pero esto contradice la definición de que existe una complejidad de al menos . Es decir, por definición ( ), se permite que la cadena devuelta por el programa GenerateParadoxicalString pueda ser creada por el programa con una longitud o mayor pero menor que . Entonces, el programa no puede calcular la complejidad de una cadena aleatoria. $n_ {0}$ $s$ $s$ $n_ {0}$ GenerateParadoxicalString $n_ {0}$ KolmogorovComplexity

Esta es una prueba por contradicción, donde la contradicción es similar a la paradoja de Berry : "Sea el número entero positivo más pequeño que no puede ser llamado por menos de veinte palabras en inglés". [8] También es posible mostrar la no computabilidad reduciendo la no computabilidad a un problema de parada , ya que y son equivalentes de Turing. [9] $norte$ $k$ $H$ $k$ $H$

Existe un corolario en la comunidad de programación conocido como el teorema de uso completo , que establece que no existe un compilador que esté perfectamente optimizado para el tamaño.

Regla de la cadena para la complejidad de Kolmogorov

La regla de la cadena para la complejidad de Kolmogorov establece que

K(X,Y)=K(X)+K(Y\mid X)+O{\big (}\log K(X,Y){\big )}.

Establece que el programa más corto que se reproduce y es como mucho más grande que el programa que se reproduce , y el programa que se reproduce dado . Usando esta expresión, se puede definir un análogo de información mutua para la complejidad de Kolmogorov. $X$ $Y$ ${\ estilo de visualización \ log K (X, Y)}$ $X$ $Y$ $X$

Compresión

Calcular el límite superior para es fácil: solo necesita comprimir la cadena usando algún método, implementar el descompresor apropiado en el idioma elegido, conectar el descompresor a la cadena comprimida y medir la longitud de la cadena resultante. $Kansas)$ $s$

La cadena se comprime si tiene una descripción cuya longitud no exceda . Esto es equivalente a una declaración . Si esto no se hace, entonces no está comprimido por . Una cadena que no es comprimible por 1 simplemente se llama incompresible; según el principio de Dirichlet , deben existir cadenas incompresibles , ya que hay cadenas de bits de longitud , pero solo cadenas de longitud inferior a [10] . $s$ $C$ ${\ estilo de visualización | s | -c}$ $K(s)\leqslant |s|-c$ $s$ $C$ $2^{n}$ $norte$ $2^{n}-1$ $norte$

Por la misma razón, la mayoría de las cadenas son complejas en el sentido de que no se pueden comprimir significativamente: no mucho menos que la longitud en bits. Para aclarar, fijemos el valor de . Hay cadenas de bits de longitud . La distribución de probabilidad uniforme sobre el espacio de estas cadenas de bits se determina exactamente igual al factor de ponderación para cada cadena de longitud . $Kansas)$ $|s|$ $s$ $norte$ $2^{n}$ $norte$ $2^{{-n}}$ $norte$

teorema _ La probabilidad de que una cadena no esté comprimida es al menos igual a una distribución de probabilidad uniforme sobre el espacio de cadenas de bits de longitud . $C$ ${\ estilo de visualización 1-2^{-c+1}+2^{-n))$ $norte$

Para probar este teorema, notamos que el número de descripciones de longitud no excede de , obtenido a partir de una progresión geométrica : ${\ estilo de visualización nc}$

1+2+2^{2}+\ldots +2^{nc}=2^{n-c+1}-1.

queda por lo menos

{\ estilo de visualización 2^{n}-2^{n-c+1}+1}

cadenas de bits que son incompresibles en . Divide entre para determinar la probabilidad . $C$ $2^{n}$

Teorema de incompletitud de Khaitin

Sabemos que en el conjunto de todas las cadenas posibles, la mayoría de las cadenas son complejas en el sentido de que no pueden describirse de manera suficientemente concisa. Sin embargo, resulta que el hecho de que una cadena en particular sea compleja no puede probarse formalmente si la complejidad de la cadena está por encima de cierto umbral. La formalización exacta se presenta a continuación. Para empezar, fijamos un sistema axiomático particular para los números naturales . El sistema axiomático debe ser lo suficientemente poderoso como para que un juicio preciso sobre la complejidad de una cadena pueda asignarse a una fórmula en el sistema axiomático . Esta correspondencia debe tener la siguiente propiedad: si se deriva de los axiomas , entonces la proposición correspondiente es verdadera. ${\ matemáticas {s}}$ $\matemáticas {A}$ ${\mathbf{F}}_{{\mathbf{A}}}$ $s$ ${\mathbf{F}}_{{\mathbf{A}}}$ ${\ matemáticas {s}}$ $\matemáticas {A}$

teorema _ Existe tal constante (que depende solo de un sistema axiomático particular y del lenguaje de descripción elegido) que para cualquier fila la declaración $L$

K(s)\geqslant L

no se puede probar dentro de . ${\ matemáticas {s}}$

Sin embargo, como es fácil de entender, el enunciado será verdadero para un número infinito de filas, o mejor dicho, para todas menos un número finito de filas. $K(s)\geqslant L$

La demostración del teorema se basa en la construcción autorreferencial utilizada en la paradoja de Berry . Prueba por contradicción. Si el teorema no es cierto, entonces

Supuesto (X) : Para cualquier número entero existe una cadena para la cual existe una derivación de la fórmula " " (para la cual asumimos que se puede formalizar en ).

norte

s

{\ matemáticas {s}}

{\ Displaystyle K (s) \ geqslant n}

{\ matemáticas {s}}

Considere un programa que implementa una enumeración eficiente de todas las pruebas formales en ${\ matemáticas {s}}$

función NthProof( int n )

que toma n como entrada y produce alguna prueba. Algunos de ellos prueban una fórmula como " ", donde s y n son constantes en el lenguaje . Hay un programa que comprueba si la enésima prueba prueba la fórmula " ": ${\ Displaystyle K (s) \ geqslant n}$ ${\ matemáticas {s}}$ ${\ Displaystyle K (s) \ geqslant L}$

función NthProofProvesComplexityFormula( int n )

Por el contrario, la cadena s y el número L pueden ser calculados por los programas

función PruebaNthCadena( int n ) función ComplejidadLowerBoundNthProof( int n )

Considere ahora el siguiente programa:

función GenerateProvablyComplexString( int n ) for i = 1 to infinity: if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n return StringNthProof( i )

Dado n como entrada , este programa verifica cada prueba hasta que encuentra alguna cadena s y una prueba de la fórmula K ( s ) ≥ L para alguna L ≥ n . Este programa se detiene en Guess (X) . Deje que este programa tenga una longitud U . Existe un número n 0 tal que U + log 2 n 0 + C < n 0 , donde C es la longitud adicional del programa

función GenerateProvablyParadoxicalString() return GenerateProvablyComplexString( n 0 )

Tenga en cuenta que el número n 0 también está codificado en este programa, lo que requiere información de registro 2 ( n 0 ). El programa GenerateProvablyParadoxicalString produce una cadena s para la que existe una L tal que se puede inferir K ( s ) ≥ L , donde L ≥ n 0 . En particular, K ( s ) ≥ n 0 es verdadero para ella . Sin embargo, s se puede describir mediante un programa de longitud U + log 2 n 0 + C , por lo que su complejidad es menor que n 0 . La contradicción resultante prueba la falsedad de la Suposición (X) . ${\ matemáticas {s}}$

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

Longitud mínima del mensaje

El principio de longitud mínima de mensaje en inferencia estadística e inductiva y aprendizaje automático fue desarrollado por Wallace ( inglés CS Wallace ) y Bolton ( inglés DM Boulton ) en 1968. El principio MDS es bayesiano (incluye probabilidades previas) y teórico de la información. Tiene las propiedades deseables de invariancia estadística (inferencia se transforma con reparametrización), conectividad estadística (incluso para un problema muy difícil, el principio convergerá al modelo subyacente) y eficiencia (un modelo basado en el principio MDS convergerá a cualquier problema válido). modelo subyacente tan pronto como sea posible). Wallace y Dowe ( ing. DL Dowe ) mostraron una relación formal entre el principio MDS y la teoría algorítmica de la información (o complejidad de Kolmogorov).

La oportunidad de Kolmogorov

De acuerdo con la definición de aleatoriedad de Kolmogorov (también aleatoriedad algorítmica), se dice que una cadena es aleatoria si y solo si es más corta que cualquier programa de computadora capaz de reproducirla. Para precisar esta definición, una computadora universal (o una máquina de Turing universal ) debe ser reparada, de modo que "programa de computadora" significaría el programa para esa máquina universal. Random en este sentido, la cadena será "incompresible". Usando el principio de Dirichlet, es fácil mostrar que para cualquier máquina universal hay cadenas algorítmicamente aleatorias de cualquier longitud, pero la propiedad de que una cadena sea algorítmicamente aleatoria depende de la elección de la máquina universal.

Esta definición se puede extender a secuencias infinitas de caracteres de un alfabeto finito. La definición puede enunciarse de tres formas equivalentes. La primera forma utiliza un análogo efectivo de la teoría de la medida; el otro utiliza una martingala eficiente . La tercera forma de definirla es esta: una secuencia infinita es aleatoria si la complejidad de Kolmogorov de su segmento inicial crece lo suficientemente rápido; existe una constante c tal que la complejidad de cualquier segmento inicial de longitud n es al menos n − c . Resulta que esta definición, a diferencia de la definición de aleatoriedad de cadenas finitas, no depende de la elección de la máquina universal.

Relación con la entropía

Según el teorema de Brudno, la entropía de un sistema dinámico y la complejidad algorítmica de las trayectorias en él están relacionadas por la relación para casi todo . [once] $K(x;T)=h(T)$ $X$

Se puede demostrar [12] que la complejidad de Kolmogorov del resultado del trabajo de una fuente de información de Markov está relacionada con su entropía . Más precisamente, la complejidad de Kolmogorov de la salida de una fuente de información de Markov, normalizada a las longitudes de la salida, converge casi siempre a la entropía de la fuente.

Notas

↑ Solomonoff, Ray Informe preliminar sobre una teoría general de la inferencia inductiva // Informe V-131: revista. - Cambridge, Ma.: Zator Co., 1960. - 4 de febrero. revisión Archivadoel 1 de agosto de 2020 enWayback Machine, noviembre de 1960.
↑ Solomonoff, Ray. Una teoría formal de la inferencia inductiva Parte I // Información y control : diario. - 1964. - Marzo ( vol. 7 , no. 1 ). - Pág. 1-22 . - doi : 10.1016/S0019-9958(64)90223-2 .
↑ Solomonoff, Ray. Una teoría formal de la inferencia inductiva Parte II // Información y control : diario. - 1964. - junio ( vol. 7 , no. 2 ). - pág. 224-254 . - doi : 10.1016/S0019-9958(64)90131-7 .
↑ Kolmogorov, A. N. Tres enfoques para la definición del concepto de "cantidad de información" // Problemas de transmisión de información: diario. - 1965. - T. 1 , N º 1 . - S. 3-11 . (Ruso)
↑ Chaitin, Gregory J. Sobre la simplicidad y la velocidad de los programas para calcular conjuntos infinitos de números naturales // Journal of the ACM : journal. - 1969. - Vol. 16 _ - Pág. 407 . -doi : 10.1145/ 321526.321530 . Archivado desde el original el 25 de agosto de 2011.
↑ Kolmogorov, A. Base lógica para la teoría de la información y la teoría de la probabilidad (inglés) // IEEE Transactions on Information Theory : diario. - 1968. - vol. 14 , núm. 5 . - Pág. 662-664 . -doi : 10.1109/ TIT.1968.1054210 .
↑ Li, Ming; Pablo Vitani. Una introducción a la complejidad de Kolmogorov y sus aplicaciones . — 2do. - Springer, 1997. - ISBN 0387948686 .
↑ Original: "Que sea el entero positivo más pequeño que no se pueda definir en menos de veinte palabras en inglés". $norte$
↑ Peter Bro Miltersen. Notas del curso de compresión de datos. 2. Complejidad de Kolmogorov (enlace inaccesible) . Consultado el 17 de febrero de 2011. Archivado desde el original el 9 de septiembre de 2009. (indefinido)
↑ Como hay cadenas de longitud , el número de cadenas de longitud es , que es una progresión geométrica finita con suma igual a . ${\ estilo de visualización n_{L}=2^{L}}$ $L$ $L=0,\ldots,(n-1)$ ${\displaystyle n_{0}+n_{1}+\ldots +n_{n-1}=2^{0}+2^{1}+\ldots +2^{n-1))$ $2^{0}+2^{1}+\ldots +2^{n-1}=2^{0}\times (1-2^{n})/(1-2)=2 ^{n}-1$
↑ Copia archivada . Consultado el 6 de junio de 2013. Archivado desde el original el 26 de diciembre de 2011. (indefinido)
↑ http://arxiv.org/pdf/cs.CC/0404039

Literatura

Vereshchagin N.K. El curso de la complejidad de Kolmogorov .
Vereshchagin N. K., Shen V. A. Kolmogorov complejidad y aleatoriedad algorítmica . —MTsNMO, 2013.
Vyugin VV Kolmogorov complejidad y aleatoriedad algorítmica .

diccionarios y enciclopedias	gran chino universalis