Gödel, Turing, Chaitin y la informática
Gregory Chaitin publica el artículo Los límites de la razón en el Investigación y Ciencia de este mes (mayo).
Este hombre, basándose en el teorema de Gödel que dice que la matemática es incompleta –es decir, que siempre habrá algo pendiente por demostrar y que ciertos axiomas no lo serán nunca-, se saca de la manga una nueva teoría informática que, a mi modo de ver, resulta tonta y carente de sentido.
Tras un breve rollo introductorio de autoglorificación y la presentación de su nuevo libro, afirma que él, igual que en su momento Turing, ha conseguido demostrar la incompletitud de la informática y la matemática o, lo que es lo mismo, otra forma de tratar el teorema de Gödel.
Básicamente nos dice que la teoría algorítmica de la información mide la complejidad de un número o un teorema como el tamaño del programa que es capaz de generar dicho número o teorema. Y nos pone ejemplos. Un programa para generar una secuencia infinita de cuadrados es, evidentemente, más corto que la propia secuencia (otra cosa es el tiempo de ejecución). Lo mismo que para el número PI.
Luego nos dice que el programa capaz de generar un número aleatorio específico es el propio programa más el número guardado en él. Decimos, pues, que dicho número es incomprensible. Hasta aquí vamos bien.
Luego nos introduce omega, que es un número probabilístico generado al indicar con 1 o 0 si el programa n se detendrá o no, tomando como base la máquina de Turing, y nos dice que ese número es, de nuevo, incomprensible. Vale. Hasta aquí todo es correcto y no nos hemos salido de Gödel ni de Turing.
A partir de ahí el artículo dice que eso demuestra de una nueva forma la incompletitud de la matemática y, por extensión, de la física; a partir de ese momento, el autor vuelve a irse por los cerros de Úbeda o más allá.
Pero yo tengo mis dudas, unas dudas muy serias.
Tomemos el citado número omega para el primer millón de programas y metámoslo en un archivo de texto. Este fichero ocupará 1 MByte. Pasémosle un compresor de los buenos, un bzip o similar. Casi me atrevería a decir que de los 100K de tamaño no pasa. Ahora tomemos el código de descompresión y el citado fichero comprimido y creemos un programa que en ejecución expanda nuestro número.
¿Qué ocuparía? ¿150K? Aunque ocupara 950K, hemos conseguido demostrar que el número omega sí es comprensible, no mediante un método matemático, sino mediante y gracias a la representación tomada (una secuencia de códigos ascii que difiere en gran medida del propio número).
Imagino que representando el número bit a bit en el archivo de texto como si fuera binario también podría comprimirse, aunque fuera un poco. Si se comprime un sólo bit, estamos tirando por tierra las teorías del señor Chaitin.
¿Qué quiere decir esto? Desde mi punto de vista dos cosas bien diferenciadas, aunque la segunda podría no ser cierta.
La primera consiste en que la informática no sirve para medir estas cosas, pues dependiendo de la representación que le demos puede tener una conclusión u otra, y principalmente que este tío se equivoca de medio a medio y ha perdido una buena parte de su vida y del dinero de su universidad investigando tonterías.
La segunda, más racional y cercana a Turing y Gödel: si tenemos en cuenta que realmente el teorema de Gödel es cierto –yo al menos no lo pongo en duda-, la matemática es incompleta, pero quizás, y sólo quizás, podría haber una metamatemática que no lo fuera; bajando un poco el registro, diremos que ciertos problemas podrían ser resolubles si se cambiara el marco, la forma o la dimensión al tratarlos. El programa que genera el número omega es al menos tan largo como el propio omega, pero resulta que si lo cogemos y le aplicamos un punto de vista lateral, podemos comprimirlo y hacer que ocupe menos.
A eso me refería.
Estrictamente hablando, el Teorema de Gödel (”el teorema de Incompletitud”) hace referencia únicamente a sistemas cerrados (aquellos cuyas operaciones empiezan y acaban en el mismo dominio). La formulación es, más o menos, que “un sistema cerrado no puede ser completo”. Para demostrarlo se venía a probar que la propia demostración de completitud de un sistema cerrado que se tenía que probar era, por sí misma, un nuevo principio que no estaba incluído en el sistema y, por lo tanto, terminaba por demostrar que el sistema inicial no estaba completo. Si se añadía la demostración de completitud al sistema para crear un metasistema, se volvía a aplicar la misma demostración recursivamente, demostrando que no hay matemática (ni metamatemática
en la que un sistema cerrado sea completo.
Me parece que en este artículo se ha sacado el principio de incompletitud de contexto. Resulta absurdo hablar de “completitud” en física, donde el “Principio de Incertidumbre” hace incompleto todo sistema físico que se quiera formular.
Me parece que el artículo hace una mala interpretación de “número incompresible”. No puede llamarse como tal a un número que puedes acotar y predecir sus valores. Es tan sólo un “número indefinido” que, a falta de fijar algunos parámetros, se puede calcular con toda precisión.
Comment by Chema Cortés — May 22, 2006 @ 11:54 am
Gracias, Chema. Ahora está más claro el asunto de Gödel y lo que mi intuición me decía.
Y desde luego el menda ese tiene unas pintas de trepa del quince, hasta ha conseguido publicar en una revista como Scientific American.
Comment by rfog — May 22, 2006 @ 1:09 pm
Lamentablemente, se vende mejor el lado esotérico de las matemáticas que su método estricto.
Encantado de haberte aclarado algo. Ahora que he releído mi comentario de nuevo, me resulta extraño que se haya entendido algo de él.
La conclusión a la que quería llegar es que la Teoría de la Información necesita de la “codificación” para establecer un canal, y que muchas veces es esa “codificación” la que complica el hecho de comunicarse; que la representación binaria de un número real sólo llega a ser una buena aproximación; que el programa que da números aleatorios ¡no da ninguna información!; que el valor que retorna una función probabilística es hipotético y no tiene por qué ser un valor real del sistema (¡no es un sistema cerrado!)…. en fin, tantas cosas se podrían criticar que daría para muchos comentarios más.
Pasa de estos iluminados.
Comment by Chema Cortés — May 23, 2006 @ 4:45 pm
Pues yo lo entendí a la primera, la verdad. Quizás porque no soy matemático y me manejo por intuiciones y mi propia lógica interna, aunque en tu segundo comentario lo pones más claro todavía: el canal y la codificación es lo que mata definitivamente las chorradas de ese tío, se nota que controlas el tema. Yo tuve bastante con “La nueva mente del emperador” y el tema de Turing
Comment by rfog — May 23, 2006 @ 6:03 pm
Hola:
La verdad que no entiendo mucho de todo esto, e igual estoy diciendo una tontería, pero hay una cosa que me choca.
Comentas que el programa que genera omega es tan grande como omega y algo más. Luego dices que se puede comprimir para que sea más pequeño que omega. ¿No es eso hacer trampas?. La forma correcta de comparar ambos tamaños sería usando el mismo “formato” para los dos. En ese caso, siempre será más grande el programa.
Se bueno.
Comment by chuidiang — May 25, 2006 @ 7:34 am
Claro. Es que ahí está el problema. Como ha dicho Chema, es una cuestión de dominio. Dentro del dominio de la teoría de la información se demuestra que lo que el tío dice no es cierto; esa es mi forma intuitiva de demostrarlo, usando elementos de la mismta teoría, evidentemente los comentarios de Chema son más rigurosos que los míos.
El concepto equivalente sería demostrar una cuestión geométrica mediante elementos algebraicos. Uno convierte el problema en ecuaciones, las resuelve, y vuelve a convertirlo a geometría. Yo hago lo mimso, tomo el problema, lo transformo en otra cosa que ocupa menos espacio, y esa cosa que ocupa menos espacio se resuelve en la solución, que en este caso es el propio problema original.
Aparte del hecho, claro está, del tema de la codificación, que Chema explica en su segundo post.
Comment by rfog — May 25, 2006 @ 8:07 am
EL numero Omega de Chaitin es infinitamente largo (es una caracteristica de los numeros aleatorios!), con lo cual un programa que lo contuviera sería infinitamente largo también, - es decir no existe. Comprimir los primeros bytes (conocidos) no reduciría la dimension del programa, que quedaría infinito.
Comment by carlo — June 20, 2007 @ 8:06 pm
Lo que dice el teorema de Godel es que “ningún sistema consistente se puede usar para demostrarse a sí mismo”. No es un sistema “cerrado” como podría pensarse de algún sistema “cerrado” en física, sino que ningún sistema puede ser a la vez consistente y completo.
Comment by Marcelo — July 17, 2007 @ 4:03 pm
me parece que cometes un error de bulto. tu sabes que la comprension de un zip depende de los datos que tenga, de manera que si tienen una determinada secuencia el compresor los sustiura por su algoritmo y ocuparan menos. pero es precisamente eso lo que no tenemos por que omega esta formado por nº aleatorios (que no mantiene ninguna relacion), con lo cual suguiriamos con un mega.
Comment by fran reglero — July 18, 2007 @ 4:38 pm