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 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 las computacional recursos necesarios para especificar el objeto, y también se conoce como la complejidad algorítmica , la complejidad Solomonoff-Kolmogorov-Chaitin , la complejidad del programa de tamaño , 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 puede usarse 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 (ver sección § Teorema de incompletitud de Chaitin ); por tanto, ningún programa puede calcular la complejidad exacta de Kolmogorov para un número infinito 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) aparte de escribir la cadena en sí, es decir, " write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" que tiene 38 caracteres. Por 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 más grande que la longitud de la cadena en sí. 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 está restringido 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 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 solo la longitud de P como una 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.
prog1(s), prog2(s). El eje horizontal ( escala logarítmica ) enumera todos cuerdas s , ordenados por longitud; el eje vertical ( escala lineal ) mide la complejidad de Kolmogorov en bits . La mayoría de las cadenas 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 algún límite fijo, que es independiente de la cadena de entrada s.