La complejidad de Kolmogórov de un domingo
Los programas escritos en cualquier lenguaje de programación son secuencias finitas de caracteres (conocidos como string), algunos, gracias a su sintaxis, nos permiten crear programas más compactos y flexibles, en otros casos, tendremos que añadir muchos más caracteres para llegar a una misma solución (no lo diré, bueno si, como en Java). ¿Cómo se mide la complejidad de la información en un string?
La complejidad de Kolmogórov nos da la posibilidad de medir la cantidad de información de un string; aunque esto nada tiene que ver si luego esa información es útil o inútil. Eso sería un tema semántico que se escapa de esto. Así como una imagen generada por DALL·E no asumimos inmediatamente que el resultado sea apreciable, quizá, gracioso o surrealista. O que al entrar por primera vez a un sitio web el navegador nos alertará que el sitio web que acabas de visitar es «inútil» (aunque debo reconocer que sería un experimento divertido).
A veces a la complejidad de Kolmogórov se la llama complejidad descriptiva (pues es una descripción de una representación posible de un string, quedará más claro con los ejemplos del siguiente párrafo), y pertenece al área de la teoría algorítmica de la información. Un área que fue desarrollada por Gregory Chaitin, Ray Solomonoff y el que lleva el nombre de esta complejidad: Andréi Kolmogórov. Desarrollada al comienzo de la segunda parte del siglo XX, que busca una relación entre la computación y la información en cuanto al programa que genera una salida, esto en contraposición, por ejemplo, a la generación estocástica de elementos (en donde cada elemento generado se basa en probabilidades).
Considere tres secuencias de string binarias (descripciones):
11111111110000000000
111000111000111000111
001010011011011011101
¿Cuál le parece más aleatoria? Creo que si las observa con atención podría —sin dificultad— llegar a decir la tercera. Pues la primera está claro que hay un patrón: diez 1 a la izquierda y diez 0 a la derecha; en la segunda, se va cambiando de bloques de 1 a 0, en bloques de dígitos, hasta llegar a tener 7 bloques; y, ¿la última? Aquí se vuelve difícil saber cuál es el patrón existente (si es que existe).
Un individuo tiende a absorber el espíritu que le rodea y a irradiar el estilo de vida y la visión del mundo adquiridos a cualquier persona de su entorno, no solo a un amigo selecto.
Andréi Kolmogórov
La complejidad de Kolmogórov se define como el programa de menor tamaño que genere esta secuencia sin ningún argumento de entrada en un lenguaje de programación X.
Si reemplazamos la X por Python, la primera secuencia se podría generar con el programa: «"1"*10+"0"*10», que tiene 13 caracteres. Para el segundo caso: «"111000"*3+"111"», 16 caracteres. (Si observa, ambos programas, no tienen ningún argumento externo.)(¿Se le ocurre un algoritmo en Python más pequeño para algunos de los dos primeros casos?)
De todas formas, debe tener presente que para calcular la complejidad de Kolmogórov, es decir, el programa más pequeño para generar un string, depende del intérprete (lenguaje de programación) que se use. En el ejemplo anterior decimos que «la tercera es la que tiene mayor complejidad» simplemente porque no reconocemos —a simple vista— un «algoritmo» que produzca esa salida.
Pero se podría tener un intérprete en donde sea totalmente válida dicha salida y, en ningún caso, sea una secuencia aleatoria y sin un algoritmo.
Algo antes de terminar cabe hacer una pequeña aclaración: la complejidad de Kolmogórov se diferencia de la complejidad computacional, en que la segunda se preocupa por los recursos que puede ocupar un algoritmo (tiempo y espacio) para computar una función. En cambio puede existir un programa que tenga una pequeña complejidad de Kolmogórov, pero que, no obstante, necesite mucho tiempo para terminar o una enorme cantidad de memoria.
(Mi domingo tuvo una pequeña complejidad Kolmogórov, según dicen.)
Floridi, L. (Ed.). (2016). The Routledge Handbook of Philosophy of Information (1st ed.). Routledge. https://doi.org/10.4324/9781315757544. Capítulo: Algorithmic information theory de Alexander Shen.
Lo puede escribir en comentarios.
En un eventual lenguaje en el que cualquier número en base decimal puede convertirse a binario de forma "natural"
1047552.toB <-- 11 caracteres
1864135.toB <-- 11 caracteres
341725.toB <-- 10 caracteres
Y en un lenguaje en el que lo normal fuese expresar los números en hexadecimal
FFC00.toB <- 9 caracteres
1C71C7.toB <-9 caracteres
536DD.toB <- 9 caracteres
Casualmente, el más aleatorio resulta ser el más corto :-/
En realidad, empaquetar como número decimal o hexadecimales es una forma de expresar con menos caracteres la misma información incrementando el número de símbolos y aunque el cambio de base no es la forma más eficiente de elegir símbolos, supone una mejora (a primera vista)
Encontrar un conjunto de símbolos S eficiente con el que representar una secuencia de "1" y "0" mediante el algoritmo de Huffman, supongo, que tiene una relación directa con la complejidad de Kolmogórov (cuanto menos aleatorio, menos símbolos son necesarios).
Como siempre, Camilo, complicándo la vida un ratito a tus lectores
Curioso tema. Cuando estuve estudiando la historia de FORTRAN me llamó la atención que la mayoría de matemáticos hechos programadores, no confiaban en programación automática porque decían que no optimizaban el código generado. Eso fue cierto para la mayoría de compiladores hasta la llegada de FORTRAN.
Quizás la complejidad no debería medir el código escrito en el lenguaje a alto nivel, sino el código a ejecutar por la máquina. En ese caso, dependería no solo de la habilidad del programador para expresar un código de forma escueta sino también del compilador por optimizar ese código a su forma más breve.
Sobre el último código, no me pude resistir a ver que era una secuencia octal representando 1, 2, 3, 3, 3, 4 y 5. Así que escribí este código:
>>> '{0:021b}'.format(0o1233345)
'001010011011011100101'
No obstante, es un código peor que escribir tan solo la cadena de caracteres.
Por otro lado, no debemos perder el foco de que el código escrito no se hace para la máquina, sino para las personas. Cuando medimos la complejidad computacional no se tiene en cuenta la extensión del código sino solo el procesamiento que de ese código deberá hacer la máquina, mientras que esta complejidad mide de forma específica la cantidad de código a leer. Sin tener en cuenta de que hay lenguajes como C, donde se puede escribir:
for (i=0; s[i]!=\0; i++);
Siendo "s" una cadena de texto, la variable "i" un entero que se inicia al valor 0 y se incrementa en cada vuelta de "for" hasta encontrar el valor nulo o fin de cadena y obtenemos en "i" el tamaño de la cadena. Es breve, pero no claro. ¿Es útil? Sin duda, pero sigue siendo tan ofuscado como mucho código escrito en C++ y Perl.
Por eso hay que poner el foco en escribir para las personas, por eso el énfasis en poner comentarios y por eso lenguajes como Java, Ada o COBOL son tan "verbose" y burocráticos.