De paradojas y cosas no computables

Recientemente me encontré con el trabajo de un grupo de científicos que descubrieron algunas relaciones entre la compresión de texto (generar archivos comprimidos como los .zip), la interpretación de lenguaje natural (que las máquinas hablen y entiendan nuestro lenguaje) y problemas de inteligencia artificial en general.

La primera vez que escuché esto me pareció un completo disparate pero, después de estarlo leyendo con un poco más de calma, he visto que la idea es realmente muy interesante y parece tener bastante sentido. Incluso, además de tener unos tintes medio filosóficos geniales, todo está fundamentado en resultados matemáticos formales. También me he dado cuenta de que las ideas, aunque no son nada triviales, tampoco parecen imposibles de entender para nosotros los simples mortales.

Éste es entonces el primero de una serie de posts donde trataré de ir explicando varios de los componentes involucrados en esta teoría. El tema de este post es la llamada complejidad de Kolmogorov que, si no dejamos que nos espante mucho el nombre y leyendo con un poquito de atención, veremos que finalmente no es algo tan complejo como aparenta. ;-)

Empezamos con una simple cadena de texto. La dichosa complejidad es un numerito que trata de medir que tan ‘complicado’ es generar esa cadena con un programa en la computadora. Por ejemplo, la cadena de texto

  “hola hola hola hola hola hola hola hola ”

la podríamos escribir en la pantalla usando el siguiente programita

  repite 8 veces escribe "hola "

Algo interesante es que este programa se puede ver, además, como una cadena de texto

  “repite 8 veces escribe "hola "”

que, en este caso, está formada por 30 caracteres (contando todas las letras, símbolos y espacios). Observa como la cadena original, la de muchos hola’s, tenía 40 caracteres y la hemos podido generar con un programa que ocupa sólo 30.

Pero no todas las cadenas de texto son tan simples como repetir “hola” un montón de veces. Por ejemplo, para la cadena de 40 caracteres

  “u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m”

quizá el programa más corto que la escriba en pantalla es

  escribe "u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m"

que ocupa en total 50 caracteres.

Entonces, la complejidad de una cadena de texto, como la definió este señor Kolmogorov, es el tamaño (en no. de caracteres) del programa más pequeño que escriba dicha cadena en la pantalla.

En el último de los ejemplos vimos cómo, para cualquier cadena de texto, es muy fácil conseguir un programa que la escriba; basta con agregarle unos 10 caracteres extras: “escribe "..."”. Esto quiere decir que la complejidad de una cadena no puede ser mucho más grande que el tamaño de la cadena misma. En el peor de los casos el programa tendrá 10 caracteres extra pero, en muchos otros casos, es posible encontrar programas más pequeños.

Imagínate en mi primer ejemplo que la cadena dice “hola ” pero, en lugar de 8, unas 5000 veces. La cadena de texto tendría ahora unos 25000 caracteres, mientras que el programa para escribirla en pantalla sigue siendo pequeñito

  repite 5000 veces escribe "hola "

y ocupa, después de cambiar el “8” por “5000”, ¡tan sólo 33 caracteres! Observa como aquí comienzan a aparecer algunas relaciones con compresión, una cadena de 25000 caracteres la pudimos comprimir en una de 33.

Espero que hasta aquí vaya todo más o menos claro, porque vamos a comenzar ahora con cosas más divertidas. Y es que vamos a mostrar que calcular la complejidad de una cadena es una tarea, digamos, muy difícil.

Supongamos que un amigo muy inteligente nos ha hecho el favor de escribir un programita al que le damos una cadena de texto y nos regresa la complejidad de esa cadena. El programa se vería más o menos así:

  Complejidad(Cadena S) regresa Número
  inicio
    /* Un código súper inteligente va aquí */
  fin

Ya que tenemos este programa, vamos a escribir nosotros este otro

  EncuentraCadena(Número N) regresa Cadena
  inicio
    por cada Cadena S
      si Complejidad(S) > N entonces regresa S
  fin

¡No se espanten! Voy a explicar ahora de qué se trata todo esto. Nuestro nuevo programa recibe de entrada un número, N, y va a dar como salida una cadena de texto. La cadena que obtenemos en la salida tiene la única peculiaridad de que su complejidad es más grande que N, el número que le demos de entrada.

Y el funcionamiento de este programita tampoco es nada complicado. Lo único que hace es ir generando una por una todas las posibles cadenas de texto (esto es lo que indica el ‘por cada Cadena’) y llamando a la rutina Complejidad para ver si hemos encontrado o no una cadena con complejidad mayor a N. En cuanto encontremos la primera cadena con complejidad mayor a N el programa termina y regresa como resultado esa cadena.

Recapitulando, este es el código que llevamos escrito hasta ahora.

  Complejidad(Cadena S) regresa Número
  inicio
    /* Un código súper inteligente va aquí */
  fin

  EncuentraCadena(Número N) regresa Cadena
  inicio
    por cada Cadena S
      si Complejidad(S) > N entonces regresa S
  fin

Recordemos que la linea donde dice ‘Un código súper inteligente va aquí’, efectivamente, tenemos reemplazarla por el código que nos haya dado nuestro amigo. Ya que hayamos escrito ese código podemos entonces contar el total de caracteres que ahora ocupa todo el programa completo hasta este punto. Digamos que los contamos y resulta que en total hay unos 5000 caracteres.

Podemos agregar entonces el siguiente pedacito de código al final de nuestro programa.

  escribe EncuentraCadena(8000)

Veamos que es lo que hace este programa. En realidad es muy sencillo, simplemente busca una cadena que tenga complejidad mayor a 8000 y la escribe en pantalla.

¿Puedes ver algún problema? Veámoslo de nuevo. Hemos construido un programa que, en total, ocupa unos 5030 caracteres e imprime una cadena de complejidad mayor a 8000. ¿Recuerdas la definición de complejidad? Es el tamaño del programa más pequeño que escribe la cadena. Según el código súper inteligente de nuestro amigo, el programa más pequeño necesita unos 8000 caracteres, pero nosotros hemos logrado escribir esa cadena ¡con sólo 5030!

¿Qué significa todo esto? Pues lo primero es que nuestro amigo súper inteligente nos mintió y el código que nos dio para calcular la complejidad de una cadena no funciona. De hecho no funciona porque, no se puede escribir ningún programa para calcularla. Lo que hemos demostrado es que, no importa qué tan inteligente sea nuestro amigo, nunca podrá escribir el dichoso programita porque eso genera contradicciones. En otras palabras hemos probado que la complejidad de Kolmogorov no es computable.

¿Y, qué significa eso? En palabras más sencillas, una de las implicaciones de este resultado es que nunca podremos programar el compresor de archivos perfecto. Y ojo que eso no quiere decir que no podamos comprimir archivos, eso sí que lo podemos hacer y es lo que hacemos cuando generamos archivos .zip. Lo que no podemos tener es la garantía de haber podido comprimir los archivos lo más posible.

Ya para terminar sólo quiero mencionar que, para hacer la explicación más sencilla, tuve que sacrificar un poco la formalidad de la demostración. Pero espero que me puedan creer que esto se puede hacer formalmente sin ninguna ambigüedad, usando por ejemplo un lenguaje de programación real apropiado. En particular el ‘por cada Cadena’ se puede implementar fácilmente generando las cadenas en orden, primero las más chicas y luego las más grandes; y las del mismo tamaño ordenadas alfabéticamente.

También para los curiosos, o si alguien se perdió entre tanta explicación y cosa rara, una versión más informal del mismo argumento es la Paradoja de Berry.