Complejidad de Kolmogorov - Enciclopedia España

En el de informática, la complejidad de Kolmogorov del (también conocido como la complejidad descriptiva, la complejidad de Kolmogorov-Chaitin del, la complejidad estocástica, la entropía algorítmica, o complejidad del programa-tamaño del ) de un objeto tal como un pedazo de texto es una medida de los recursos de cómputo necesarios para especificar el objeto. Por ejemplo considerar las dos secuencias siguientes de la longitud 64

0101010101010101010101010101010101010101010101010101010101010101

1100100001100001110111101110110011111010010000100101011110010110

La primera secuencia admite una breve descripción de la lengua inglesa, a saber " 32 repeticiones del " '01 ';, que consiste en 20 carácteres. Segundo no tiene ninguna descripción simple obvia con excepción de anotar la secuencia sí mismo, que tiene 64 carácteres.

Más formalmente, la complejidad de una secuencia es la longitud de la descripción más breve de la secuencia de un cierto idioma descriptivo fijo . La sensibilidad de la complejidad concerniente a la opción del idioma descriptivo se discute abajo. Puede ser demostrado que la complejidad de Kolmogorov de ninguna secuencia no puede ser demasiado más grande que la longitud de la secuencia sí mismo. Las secuencias cuya complejidad de Kolmogorov es pequeña concerniente al tamaño de la secuencia no se consideran ser complejas. La noción de la complejidad de Kolmogorov es asombrosamente profunda y se puede utilizar para indicar y para probar los resultados de la imposibilidad relacionados con el teorema del estado incompleto de Gödel y el problema que para de Turing.

Definición

Para definir la complejidad de Kolmogorov, debemos primero especificar un idioma descriptivo para las secuencias. Tal idioma descriptivo se puede basar en un lenguaje de programación tal como balbucea, Pascal, o bytecode de la máquina virtual de Java. Si el P es un programa que hace salir un x de la secuencia, después el P es una descripción del x . La longitud de la descripción es apenas la longitud del P como serie de caracteres. En la determinación de la longitud del P, las longitudes de cualquier subrutina usada en el P deben ser explicadas. La longitud de cualquier n de la constante entera que ocurra en el P del programa es el número de pedacitos requeridos para representar el n, de que es (áspero) el n de log₂.

Podríamos elegir alternativo una codificación para las máquinas de Turing donde está una función una codificación del que asocia a cada M de la máquina de Turing un < bitstring M >. Si el M es una máquina de Turing que en el w de la entrada hace salir el x de la secuencia, después el concatenado w de la secuencia < M > es una descripción del x . Para el análisis teórico, este acercamiento se adapta más para construir pruebas formales detalladas y es generalmente preferred en la literatura de la investigación. En este artículo utilizaremos un acercamiento informal.

Cualquier s de la secuencia tiene por lo menos una descripción, a saber el programa

función GenerateFixedString del () de vuelta s del

Entre todas las descripciones del s, hay uno con el denotado la longitud más corta d ( s ). En caso de que haya más de un programa de la misma longitud mínima, elegir uno arbitrariamente, por ejemplo seleccionando lexicográfico la primera entre él. el d ( s ) es la descripción mínima del s . La complejidad de Kolmogorov del del s, escrita el K ( s ), es el |d|. \ patio En las otras palabras, el K ( s ) es la longitud de la descripción mínima del s .

Ahora consideramos cómo la opción del idioma descriptivo afecta al valor del K y demostramos que el efecto de cambiar el idioma descriptivo está limitado. Si son el K ₁ y el K ₂ la complejidad funciona el en relación con L ₁ de los idiomas descriptivos y el L ₂, después hay un constante c (que depende solamente del L ₁ de las idiomas y del L ₂) tales que $del \ el forall s \ |K_1 - K_2| \, \ patio$ del leq c

Prueba . Por simetría, es suficiente probar que hay un cierto constante c tales que para todo el s, $K_1 \ leq de los bitstrings del K_2 + C.$

Para ver porqué esto está así pues, hay un programa en el L ₁ de la lengua que actúa como intérprete para el L ₂:

función InterpretLanguage ( p del de la secuencia )

donde está un programa el p en el L ₂. La característica siguiente caracteriza al intérprete: el

l que funciona InterpretLanguage en el p de la entrada vuelve el resultado de funcionar el p .

Así si el P es un programa en el L ₂ que es una descripción mínima del s, después de InterpretLanguage ( P ) vuelve el s de la secuencia. La longitud de esta descripción del s es la suma de La longitud del programa InterpretLanguage, que podemos tomar para ser el constante c .

La longitud del P que por definición es el K ₂ ( s ).

Esto prueba el límite superior deseado.

Ver también el teorema de la invariación.

Historia y contexto

La teoría de información algorítmica es el área de informática que estudie la complejidad de Kolmogorov y otras medidas de la complejidad en secuencias (u otras estructuras de datos . El campo fue desarrollado por el Andrey Kolmogorov, el rayo Solomonoff y el Gregorio Chaitin que comenzaba en el finales de los sesenta. Hay varias variantes de la complejidad de Kolmogorov o de la información algorítmica. El más ampliamente utilizado se basa en programas de uno mismo-delimitación y es principalmente debido al Leonid Levin (1974).

Nombramiento de este " del concepto; Complexity" de Kolmogorov; es un ejemplo del efecto de Matthew.

Resultados básicos

En el siguiente, fijaremos una definición y escribiremos simplemente el K ( s ) para la complejidad del s de la secuencia.

No es duro ver que la descripción mínima de una secuencia no puede ser demasiado más grande que la secuencia sí mismo: el programa GenerateFixedString sobre ése hace salir el s es una cantidad fija más grande que el s . Hay un constante c tales que $del \ forall s \ K \ leq |s| +, \ patio$ de c

Uncomputability de la complejidad de Kolmogorov

El primer resultado asombrosamente es que no hay manera de computar con eficacia el K . El K no es una función computable .

Es decir no hay programa que toma un s de la secuencia como entrada y produce el K ( s ) del número entero como salida. Demostramos esto por la contradicción. Suponer que hay un programa

función KolmogorovComplexity ( s del de la secuencia )

ese toma como entrada un s de la secuencia y vuelve el K ( s ). Ahora considerar el programa

función GenerateComplexString ( n del del internacional ) para el de i = 1 al infinito de : para cada de la secuencia s de de la longitud de exactamente yo si n del >= de KolmogorovComplexity ( s ) de vuelta s del el paró

Este programa llama KolmogorovComplexity como subrutina. Este programa intenta cada secuencia, comenzando con el más corto, hasta que encuentre una secuencia con el n de la complejidad por lo menos, después las vueltas que encadenan. Por lo tanto, dado cualquier positivo n, del número entero produce una secuencia con la complejidad de Kolmogorov por lo menos tan grande como el n . El programa sí mismo tiene un U de la longitud fija. La entrada al programa GenerateComplexString es un n del número entero; aquí, el tamaño del n es medido por el número de pedacitos requeridos para representar el n que es log₂ ( n ). Ahora considerar el programa siguiente:

función GenerateParadoxicalString del () de vuelta GenerateComplexString ( n ₀)

Este programa llama GenerateComplexString como una subrutina y también tiene un parámetro libre n ₀. Este programa hace salir un s de la secuencia cuya complejidad sea por lo menos el n ₀. Por una opción propicia del n ₀ del parámetro llegaremos una contradicción. Para elegir este valor, el s de la nota es descrito por el programa GenerateParadoxicalString cuya longitud está a lo más + \ log_2 (n_0) del $del l U + C \ patio$

donde está el " el C ; overhead" agregado por el programa GenerateParadoxicalString. Puesto que el n crece más rápidamente que log₂ ( n ), existe un n ₀ del valor tales que + \ log_2 (n_0) del $del U + C < n_0. \ patio$ Pero esto contradice la definición del tener un n ₀ de la complejidad por lo menos. Así el programa nombrado " KolmogorovComplexity" no puede realmente computably encontrar la complejidad de secuencias arbitrarias.

Ésta es prueba por la contradicción donde está similar la contradicción a la paradoja de la baya: " Dejar el n ser el número entero positivo más pequeño que no se puede definir en menos de veinte words." ingleses; Es también posible demostrar el uncomputability de K por la reducción del uncomputability del problema que para H, puesto que K y H son el turing-equivalente.

Regla de cadena para la complejidad de Kolmogorov

La regla de cadena para la complejidad de Kolmogorov indica eso $K (X del l, Y) = K (X) + K (Y|X) + O (\ registro (K (X, Y))). \ quad$

Indica que el programa más corto que reproduce el X y el Y es no más de que un término logarítmico más grande que un programa para reproducir el X y un programa para reproducir el Y dado el X . Usar esta declaración uno puede definir el un análogo de la información mutua para la complejidad de Kolmogorov.

Compresión

Es sin embargo directo computar los límites superiores para el K ( s ): simplemente la compresa el s de la secuencia con un cierto método, ejecuta el descompresor correspondiente en la lengua elegida, concatena el descompresor a la secuencia comprimida, y mide la longitud de la secuencia resultante.

Un s de la secuencia es compresible por un c del número si tiene una descripción cuya longitud no se exceda | s | − c . Esto es equivalente a decir el style=" ≤ del K ( s ) | s | − c . Si no el s es incompresible por el c . Una secuencia incompresible por 1 reputa simplemente el incompresible; por el principio de casillero, las secuencias incompresibles deben existir, puesto que hay 2^{cadenas binarias del n} del n de la longitud pero solamente del style=" &minus de >2^{; 2 secuencias más cortas, de que son secuencias del del n de la longitud; − 1 o menos.}

Por la misma razón, " most" las secuencias son complejas en el sentido que no pueden ser perceptiblemente comprimidas: El K ( s ) no es mucho más pequeño que | s |, la longitud del s en pedacitos. Para hacer este exacto, fijar un valor del n . Hay 2^{bitstrings del n} del n de la longitud. La distribución de la probabilidad del uniforme en el espacio de estos bitstrings asigna a cada secuencia del peso igual 2^{&minus del n de la longitud exactamente; n}. Con la distribución de probabilidad uniforme en el espacio de bitstrings del n de la longitud, la probabilidad que una secuencia es incompresible por el c es por lo menos style=" 1; 2^{− c +1} + 2^{− n}.

Para probar el teorema, observar que el número de descripciones de la longitud que no exceden el style=" &minus del n ; el c es dado por la serie geométrica : $1 + 2 del l + 2^2 + \ cdots + 2^ {n-c} = 2^ {n-c+1} - 1. \ patio$

Permanecen por lo menos $2^n-2^ {n-c+1} +1 \ patio$ del

muchos bitstrings del n de la longitud que son incompresibles por el c . Para determinar la probabilidad dividir por 2^{el n}.

Este teorema es la justificación para los varios desafíos en el FAQ de la presión de comp. A pesar de este resultado, es demandado a veces por ciertos individuos (considerados pone ) que él ha producido los algoritmos que comprimen uniformemente datos sin pérdida. Ver la compresión de datos sin pérdidas .

Teorema del estado incompleto de Chaitin

Sabemos que la mayoría de las secuencias son complejas en el sentido que no pueden ser descritas en perceptiblemente " compressed" manera. Sin embargo, resulta que el hecho de que una secuencia específica sea compleja no puede ser probado formalmente, si la longitud de la secuencia está sobre cierto umbral. La formalización exacta está como sigue. Primero fijar un axiomático S del sistema particular para los números naturales que el sistema axiomático tiene que ser bastante de gran alcance de modo que a ciertas aserciones el A sobre la complejidad de las secuencias una pueda asociar un A del _{del F de la fórmula en el S . Esta asociación debe tener la característica siguiente: si el A} del _{del F es demostrable de los axiomas del S, después el correspondiente A de la aserción es verdad. Este " formalization" puede ser alcanzado por una codificación artificial tal como una enumeración de Gödel o por una formalización que respete más claramente la interpretación prevista del S . Existe un constante L (que dependa solamente del sistema axiomático particular y de la opción del idioma descriptivo) tales que no existe un s de la secuencia para el cual el $K \ geq L \ patio$ del de la declaración (según lo formalizado en el S ) puede ser probado dentro del axiomático S del sistema. Observar que por la abundancia de secuencias casi incompresibles, la gran mayoría de esas declaraciones debe ser verdad.
La prueba de este resultado se modela en una construcción self-referential usada en la paradoja de la baya. La prueba está por la contradicción. Si el teorema era falso, entonces asunción del del
l (x) : Para cualquier n del número entero existe un s de la secuencia para el cual haya una prueba en el S del " de la fórmula; " del n del ≥ del K ( s ); (que asumimos puede ser formalizado en el S ).
Podemos encontrar una enumeración eficaz de todas las pruebas formales en el S por un cierto procedimiento
función NthProof ( n del del internacional ) cuál toma como n de la entrada y hace salir una cierta prueba. Esta función enumera todas las pruebas. Algunos de éstos son pruebas para las fórmulas que no lo hacemos cuidado sobre aquí (los ejemplos de las pruebas que serán enumeradas por el procedimiento NthProof son las varias pruebas sabidas de la ley de la reciprocidad cuadrático, los teorema de Fermat de poco o la prueba del teorema pasado de Fermat tradujeron todo al lenguaje formal del S ). Están fórmulas algunos de éstos de la complejidad del n del ≥ del K ( s ) de la forma donde los constantes del s y del n en la lengua del S . Hay un programa
función NthProofProvesComplexityFormula ( n del del internacional )
cuál determina si la prueba del n ^th prueba realmente un L del ≥ del K ( s ) de la fórmula de la complejidad. El s de las secuencias y el L del número entero alternadamente es computable por programas: función StringNthProof ( n del del internacional )
función ComplexityLowerBoundNthProof ( n del del internacional )
Considerar el programa siguiente
función GenerateProvablyComplexString ( n del del internacional ) para i = 1 al infinito: si de NthProofProvesComplexityFormula (i) y n del >= de ComplexityLowerBoundNthProof (i) de vuelta StringNthProof ( i ) el paró
Dado un n, este programa intenta cada prueba hasta que encuentre una secuencia y una prueba en el formal S del sistema del n del ≥ del K ( s ) de la fórmula. El programa termina por nuestra asunción del (x) . Ahora este programa tiene un U de la longitud. Hay un n ₀ del número entero tales que el U + log₂ ( n ₀) + el C < el n ₀, de donde está los gastos generales el C
función GenerateProvablyParadoxicalString del () de vuelta GenerateProvablyComplexString ( n ₀) el paró
El programa GenerateProvablyParadoxicalString hace salir un s de la secuencia para el cual ≥ del K ( s ) el n ₀ se puede probar formalmente en el S . Particularmente ≥ del K ( s ) el n ₀ es verdad. Sin embargo, el s también es descrito por un programa de la longitud El U +log₂ ( n ₀) + el C así que su complejidad es menos que el n ₀. Esta contradicción prueba que la asunción del (x) no puede sostenerse.
Se utilizan las ideas similares de probar las características de constante de Chaitin.
El principio mínimo de la longitud de mensaje de inferencia estadística e inductiva y de aprendizaje de máquina fue desarrollado por C. MML es el Bayesian (incorpora creencia anterior) y información-teórico. Tiene las características deseables de estadístico invariación (la inferencia transforma con una re-parametrización, por ejemplo de coordenadas polares a los coordenadas cartesianos), consistencia estadística (incluso para los problemas muy duros, MML convergerá a cualquier modelo subyacente) y a la eficacia (el modelo de MML convergerá a cualquier modelo subyacente verdadero alrededor tan rápidamente como es posible). Dowe demostraron una conexión formal entre MML y la teoría de información algorítmica (o la complejidad de Kolmogorov) en 1999.

Aleatoriedad de Kolmogorov
La aleatoriedad de Kolmogorov del (también llamado el la aleatoriedad algorítmica ) define una secuencia (generalmente de los pedacitos como siendo el al azar si y solamente si es más corta que cualquie programa de computadora que puedan producir esa secuencia. Esta definición de la aleatoriedad es críticamente dependiente en la definición de la complejidad de Kolmogorov. Para hacer esta definición completa, una computadora tiene que ser especificada, generalmente una máquina de Turing. Según la definición antedicha de la aleatoriedad, una secuencia al azar es también un " incompressible" secuencia, en el sentido que es imposible dar una representación de la secuencia usar un programa cuya longitud sea más corta que la longitud de la secuencia sí mismo. Sin embargo, según esta definición, la mayoría encadena más corto que cierta longitud termina para arriba para ser (Chaitin-Kolmogorovically) al azar porque el mejor puede hacer con las secuencias muy pequeñas es escribir un programa que imprima simplemente estas secuencias.
Ver también
Algoritmo de Berlekamp-Massey
Aleatoriedad de Chaitin-Kolmogorov
Compresión de datos
Publicaciones importantes en la teoría de información algorítmica
Distancia de Levenshtein}

Zenithic

Image:BeachVolleyballAt2004SummerOlympics-1.jpg

Random links:

Bowser (Nintendo) | Condado del col, Missouri | Zapata Espinoza | Amanattō | Ono ninguÌn Imoko

="http://pagead2.googlesyndication.com/pagead/show_ads.js">