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 Solomonoff-Kolmogorov-Chaitin , complejidad del tamaño del programa , complejidad descriptiva o entropía algorítmica . lleva el nombre deAndrey Kolmogorov , quien publicó por primera vez sobre el tema en 1963. [1] [2]
La noción de complejidad de Kolmogorov se puede utilizar para enunciar y probar 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 (consulte la sección § Teorema de incompletitud de Chaitin ); por lo tanto, ningún programa único puede calcular la complejidad exacta de Kolmogorov para una cantidad infinita de textos.
La primera cadena tiene una breve descripción en inglés, a saber, " write ab 16 times", que consta de 17 caracteres. El segundo no tiene una descripción simple obvia (usando el mismo conjunto de caracteres) además 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 a continuación). 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 propia cadena. Las cadenas como el ejemplo de 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 por simplicidad, el alcance de este artículo se restringe a las cadenas. Primero debemos especificar un lenguaje de descripción para las cadenas. Dicho lenguaje de descripción puede basarse en cualquier lenguaje de programación de computadoras, 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 en un carácter (p. ej., 7 para ASCII ).
Podríamos, alternativamente, 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 demostraciones formales detalladas y, en general, se prefiere en la literatura de investigación. En este artículo, se discute un enfoque informal.
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 de 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 un límite fijo, que es independiente de la cadena de entrada s.