Chaitin, Omega y otras curiosidades matemáticas

Biografía

Gregory J. Chaitin Nacido en 1947 en New York hijo de inmigrantes argentinos. Con sólo trece años, estando en bachillerato, se interesó por el teorema de incompletitud de Gödel. En 1965 regresó a Argentina donde empezó a estudiar matemáticas. Una vez concluidos sus estudios empezó a trabajar para IBM compaginándolo como profesor en la facultad de Matemáticas de Buenos Aires.

A principios de los años 60 desarrolló su Teoría de la información algorítmica que relaciona la computación con la información. Sus primeros trabajos están muy relacionados con los estudios de Kolmogorov y su tratamiento estadístico de la información. La aportación más importante de Chaitin es la La constante Omega constante de Chaitin Ω: un número real entre 0 y 1, de dígitos equidistribuidos que expresa la probabilidad de que un programa aleatorio realice alguna tarea (no se cuelgue) al ser ejecutado en una máquina de Turing. Chaitin también escribe sobre metafísica, filosofía matemática, metamatemática, neurología (el problema de la conciencia y el estudio de la mente), biología (definiendo formalmente el concepto de 'vida'), filosofía digital (El universo es un autómata celular Turing-completo).

En 1995 obtuvo el título de doctor honoris causa por la Universidad de Maine. Es profesor honorario de la Universidad de Buenos Aires desde 2002, profesor visitante del Departamento de Informática de la Universidad de Auckland y miembro del comité internacional del Instituto de Sistemas Complejos de Valparaíso. Hoy en día es investigador en el Watson Research Center de New York.

Teoría de la Información Algorítmica

La Teoría de la Información Algorítmica es un área situada entre la teoría de la información y la Informática que relaciona la computación con la información. La Teoría de la Información Algorítmica estudia principalmente la complejidad de Kolmogorov y las cadenas de información. Fue desarrollada a finales de los años 60 por Kolmogorov, Solomonoff y Chaitin de forma simultánea. Existen diferentes variantes de complejidad de Kolmogorov y de información algorítmica.

Complejidad de Kolmogorov-Chaitin

La complejidad de Kolmogorov-Chaitin, entropía algorítmica o complejidad "program-size" de una cadena de texto (entendiendo cadena de texto como secuencia finita de caracteres) es el tamaño de los recursos computacionales necesarios para describir la cadena. Recurso computacional indica código del programa más datos del programa. De esta forma, una "descripción" viene a significar: una forma de generar la cadena a través de un determinado programa. Consideremos las siguientes cadenas:

0101010101010101010101010101010101010101

1001011101001100100101100011001110100110

La primera cadena tiene una descripción simple "20 veces 01" pero la descripción de la segunda no es tan obvia. Existen cadenas cuya descripción es tan compleja como la propia cadena. En estos casos nunca puede darse para esas cadenas una descripción menor que la propia cadena, dado que en tal caso la cadena se describiría a sí misma y tendría el mismo tamaño.

Formalmente, la descripción de una cadena es la descripción existente más corta (en un determinado lenguaje de descripción). El número PI, por ejemplo, tiene una cantidad infinita de dígitos, pero su descripción puede ocupar unas pocas líneas de código.

Para definir la complejidad de Kolmogorov es necesario especificar un lenguaje de descripción, ese lenguaje puede estar basado en un lenguaje de programación como Lisp, Java, o C. Cualquier cadena S tiene al menos la descripción siguiente:

function GeneraCadena()
    return S;

Para algunos programas existirá otra forma de describir la cadena de forma que no sea la propia cadena la que se devuelve, como por ejemplo la primera cadena estudiada, "20 veces 01". Cada lenguaje de programación devuelve una complejidad distinta (aunque puede coincidir) para la misma cadena, pero existe una constante que relaciona las complejidades entre dos lenguajes de descripción distintos.

Existe otra forma de describir una determinada cadena: comprimiéndola. Simplemente se elije la cadena, se comprime con un determinado algoritmo de compresión y se crea el algoritmo de descompresión, si el tamaño del algoritmo de descompresión más el tamaño de la descripción es menor que la cadena descrita se obtiene una descripción de menor tamaño que la propia cadena. Sin embargo no todas las cadenas son comprimibles dado que existen 2ⁿ cadenas de longitud n pero sólo hay 2ⁿ−1 cadenas menores que n. Según el principio del palomar de Dirichlet si existen n palomas y m nidos de paloma y n>m debe de haber un nido en el que existan al menos dos palomas. Por lo tanto deben existir al menos dos cadenas de tamaño n cuya representación comprimida sea común y el algoritmo de descompresión extraiga la misma cadena, existiendo por tanto al menos una cadena incompresible.

Por esa misma razón, la mayoría de las cadenas no serán comprimidas de forma significativa. Se puede calcular, sin embargo, la probabilidad mínima para que una cadena de tamaño n sea comprimible.

Teorema de incompletitud de Chaitin

El trabajo de Chaitin extiende la aproximación de Gödel sobre la incompletitud y la hace más accesible enfocándola a la computabilidad. Sabemos que la mayoría de las cadenas son complejas en el sentido de que no se pueden representar de una forma comprimida. Sin embargo, no se puede demostrar que una determinada cadena sea compleja, al menos hasta cierto umbral. Formalicémoslo:

En primer lugar se elige un sistema axiomático S para los números naturales. El sistema axiomático tiene que ser suficientemente potente como para que a ciertas aserciones A sobre complejidad de cadenas se les pueda asociar la fórmula F_A en S. Esta asociación debe de cumplir la siguiente propiedad: si se puede demostrar F_A a partir de los axiomas de S, entonces la aserción A es verdadera. Esta formalización puede ser obtenida a través de un sistema de codificación artificial como por ejemplo la numeración de Gödel.

Teorema: Existe una constante L (dependiente sólo del sistema axiomático y del lenguaje de descripción) tal que no existe una cadena cuya complejidad sea mayor que L.

La demostración del resultado se modela con una construcción autoreferencial basada en la paradoja de Berry.

Suposición: para cualquier entero n existe una cadena s tal que existe una demostración de que la complejidad de s es mayor que n.

Aleatoriedad de Chaitin-Kolmogorov

La aleatoriedad de Chaitin-Kolmogorov (también llamada aleatoriedad algorítmica) define una cadena como aleatoria si no puede generarse con un algoritmo más pequeño que ella. Sería fácil ver que la mayoría de las cadenas de una determinada longitud están cercanas a la aleatoriedad en este aspecto.

La constante Omega Ω

El número Ω representa la probabilidad de que un programa aleatorio se detenga para una arquitectura determinada.

Los principios de la constante de Chaitin se encuentran en una edición de la Sociedad de Matemáticas Londinense (Proceedings of the London Mathematical Society, 1936) en la que un desconocido hasta entonces Alan M. Turing presentó un modelo de una computadora digital programable de propósito general (Máquina de Turing). Después planteó su conocido problema de la parada, en el que pregunta si se puede determinar si un programa concreto se detiene al ser ejecutado en su máquina.

Se puede comprobar si un programa se para ejecutándolo, pero el problema es determinar, tras un tiempo de ejecución, si el programa se ha colgado o es que es un algoritmo “muy largo”. Turing demostró que no se puede encontrar una solución general a este problema.

Para poder comprender Ω, es necesario considerar el conjunto de todos los programas posibles. La probabilidad de que un programa elegido al azar se detenga es representada por el número Ω. El valor concreto de Ω depende de la computadora y del lenguaje de programación elegido, pero esta elección no modificaría sus sorprendentes propiedades. Al ser una probabilidad, el número Ω es un número real comprendido entre 0 y 1.

Cálculo de Ω

Ω puede ser definido como una suma infinita en la que cada programa de n bits que se detiene contribuye precisamente con 1/2ⁿ a la suma total. En otras palabras: cada uno de estos programas de 'n' bits añade un 1 al bit enésimo en la expansión binaria de Ω.

$\Omega =\sum _{p\in P}2^{-|p|}.$

p es el programa que se para.

|p| es el tamaño de dicho programa.

P es el conjunto de todos los programas que se paran.

Ω es un número perfectamente definido, aparentemente podría ser calculado, pero sabemos que no es cierto, dado que si realmente fuese así el problema de la parada de Turing estaría resuelto, y sabemos que este problema no tiene solución.

Ejemplo:

Si sabemos que los programas “1”, “01” y “001” se detienen, deducimos que el valor de Omega empezará por 0.111.

Importancia de Omega

El número Omega nos proporciona una secuencia infinita de bits irreducibles (no definidos por ninguna ley). Dado un programa finito, existe un número infinito de bits que el programa no puede computar. Dado un conjunto finito de axiomas, existe un número de verdades infinitas que esos axiomas no pueden demostrar.

Como Omega es irreducible, podemos deducir que no puede existir una teoría “del todo” en matemáticas. Las matemáticas tienen una complejidad infinita, y una determinada teoría tendría solo complejidad finita y no podría capturar la riqueza de la verdad matemática.

El hecho de que existan acciones irreducibles no quiere decir que dejemos de razonar, los principios irreducibles (axiomas) han existido siempre en las matemáticas.

Programas elegantes

En Unknowable, Chaitin demuestra que no se puede demostrar que un programa sea elegante.

Definimos programa elegante como el programa más corto que produce una determinada salida, es decir que no existe un programa más pequeño que genere esa misma salida. El término programa se refiere a código más las entradas al programa. Cada programa elegante produce una única salida (puede ser infinita). Esta definición tiene varias consecuencias:

• La salida de un programa elegante es computable.
• Hay un número infinito de programas elegantes, uno para cada posible salida.

El Teorema de Chaitin asegura que no es posible determinar si un programa es elegante (en particular, no es posible determinar si un programa es elegante a partir de un determinado umbral).

Demostración por reducción al absurdo

Supongamos que existe un programa de demostración de programas elegantes, llamemoslo ET (elegance-testing). ET acepta un programa como entrada y devuelve verdadero si el programa es elegante y falso si no lo es.

Ahora construimos un programa que acepte como entrada un número n y enumere todos los programas P_k de tamaño mayor que n, llamémoslo B. El programa B ejecuta el programa probador de elegancia ET para cada programa enumerado, hasta que encuentre un programa que sea elegante. Una vez encontrado el programa elegante, B lo ejecuta, produciendo la salida que ese programa produciría.

Lema: B debe producir alguna salida

Demostración: Hay un número infinito de programas elegantes, así que si ET funciona como hemos dicho, B encontrará alguno de esos programas y producirá la salida de ese programa.

Ahora ejecuta B con el número n con valor “longitud de B +1” (tamaño umbral) ahora B producirá la misma salida que algún programa que ET dijo que era elegante, pero ese programa es de mayor tamaño que B, con lo cual, ese programa no puede ser elegante dado que B devuelve la misma salida con un menor tamaño, por lo tanto ET predijo mal que P_k era elegante.

Otras Aportaciones

Complejidad y simplicidad

En 1686, Gottfried Leibniz publicaba un ensayo filosófico (Discurso sobre metafísica) en el que trataba de distinguir los hechos que están regidos por leyes de aquellos que no lo están, en el capítulo VI de su ensayo esgrimía la idea de que una ley tiene que ser más simple que aquello que trata de explicar, de otro modo, sería inútil.

Hoy en día, los términos de complejidad y simplicidad son explicados cuantitativamente por la teoría de la información algorítmica. En la “teoría de información ordinaria” se cuantifica la información en función del número de bits que se necesitan para codificar la información (un sólo bit para una respuesta del tipo Si/No). En la “teoría de la información algorítmica” en cambio se cuantifica la información en función del tamaño del programa que genere el dato.

¿Qué tiene que ver esto con los hechos y las teorías científicas?

• En primer lugar, como Guillermo de Occam apuntó: dadas dos teorías que expliquen lo mismo, la teoría más simple es la preferida (navaja de Occam).
• En segundo lugar, la idea de Leibniz aplicada a la informática: si una teoría que tiene el mismo tamaño en bits que los datos que trata de explicar, dicha teoría es inútil porque incluso el dato más aleatorio tiene teoría.

Desde Platón a Chaitin

“La compresión es la comprensión”. Esta es una de las máximas que Chaitin defiende y con la que comienza algunos de sus artículos y conferencias. Para medir el tamaño real de algo debemos medir el tamaño de las hipótesis teóricas que lo definen (o del programa que lo calcule) y que comprimen por consiguiente los datos en una expresión algorítmica o teoría matemática.

De esta forma, y basándose en la teoría formal axiomática de Hilbert, en el teorema de incompletitud de Gödel y en base a la Teoría Algorítmica de la Información (AIT en inglés), Chaitin construye una serie de teorías filosóficas y demostraciones matemáticas enfocadas a la incapacidad de las matemáticas de obtener por si solas todas las verdades.

¿Si algo no puede comprimirse no puede comprenderse? ¿Y viceversa? Visto así, este hecho supone mucho más de lo que parece, implica entre otras cosas que el ser humano no podrá llegar nunca a descubrir una "Teoría del Todo" que defina el funcionamiento del universo y aún suponiendo que lo consiguiera, no podría demostrar que esta es la más concisa de todas las posibles.

La matemática ha sufrido un fuerte golpe desde que en 1931, Gödel descubrió que algunas de las más importantes ideas matemáticas podrían no ser nunca completas. "El mundo de las matemáticas tiene una complejidad infinita y por eso no es completamente comprensible".

Sin embargo Chaitin para demostrar la existencia de ciertas verdades matemáticas irreducibles comienza hablándonos de Platón, y de cómo este reconoce la simetría como base matemática para la descripción del universo. El mundo es racionalmente comprensible porque tiene una estructura. En Timaeus se postula que las formas geométricas son los bloques básicos de construcción para todo el universo.

A los griegos la belleza de las matemáticas, la regularidad en los movimientos de los astros y los eclipses, les convencieron de la comprensibilidad del mundo.

En el libro de Los Elementos, Euclides decía que una verdad matemática se establece reduciéndola a verdades simples hasta que son verdades “auto-evidentes” -axiomas o postulados (átomos de pensamiento)- y en base a esos axiomas construyó la Geometría Euclídea. Leibniz dijo: “God has chosen the most perfect world, that is, the one which is at the same time the simplest in hypotheses and the richest in phenomena”.

La navaja de Guillermo de Occam (o navaja de Ockham, o principio de economía o de parsimonia) dice que la mejor teoría para explicar un conjunto de datos es la más sencilla.

Otros como Barrow y Einstein antes que él, y según el principio antrópico cosmológico, declaran que no podríamos estar aquí para hacernos estas preguntas a menos que el universo tenga suficiente orden (estructura) como para que unas criaturas complejas como nosotros puedan entenderlo.

La ciencia reduccionista moderna se basa en romper las cosas hasta encontrar en ellas la simplicidad subyacente. Hoy en día aplicamos elementos tan básicos como la teoría de grupos y las simetrías, para entender por ejemplo las partículas sub-atómicas.

En todos estos casos y a lo largo de la historia se ve como grandes pensadores basan la complejidad de todo lo que nos rodea en la sencillez que bajo ello subyace. Todos estos pensadores también creen en la posibilidad del ser humano de comprender el universo.

Pero es Bertrand Russell quien introduce una serie de paradojas ( Paradoja de Russell) que pone en cuestión la capacidad de razonamiento del ser humano, y expone situaciones que parece que la aplicación sistemática de la razón no puede resolver.

Una de las reacciones a esta crisis de la lógica fue la tentativa de David Hilbert quien cree que estas contradicciones pueden eludirse por medio de formalismo y quería llegar al mismísimo fin de la definición de la matemática. Cual fue su sorpresa cuando en 1931 Kurt Gödel publica su famoso teorema de la incompletitud en el que básicamente afirma que:

En cualquier formalización consistente de las matemáticas que es lo bastante fuerte para definir el concepto de números naturales, se puede construir una afirmación que ni se puede demostrar ni se puede refutar dentro de ese sistema.

Tras años de una creencia en la omnipotencia de las matemáticas, Gödel afirma que no todo es es demostrable o refutable.

Tras él, Alan Turíng construye su máquina y en base a ella plantea el problema de la parada: No podemos determinar si un programa parará dada una entrada concreta.

Tras aplicar la Teoría Algorítmica de la Información, para definir y concretar los conceptos de simplicidad y complejidad, Chaiting la aplica para obtener la definición de irreductibilidad. Siguiendo a Turing, hace uso de la noción de algoritmo para deducir límites del razonamiento formal. Para medir la complejidad de la teoría formal axiomática de Leibniz considera el tamaño en bits del algoritmo que genera sistemáticamente todos los teoremas, desarrollando todas las posibles pruebas, y obteniendo sistemáticamente todas las consecuencias de los axiomas.

Nos dice así, que no es posible calcular la complejidad medida por el tamaño de un programa,porque determinar dicha complejidad equivale a conocer el tamaño del más conciso de todos los programas que la calculan. Tal conocimiento no es posible si el programa es más extenso que los axiomas. Si tenemos n bits para definir los axiomas, se podrá determinar nunca la complejidad de nada que tenga más de n bits de complejidad, que es casi todo.

Chaitin nos lleva desde la irreductibilidad en la computación a la irreductibilidad en la lógica, definiendo para ello el concepto de elegancia en los programas de ordenador como ya hemos visto antes.

A pesar de todo lo demostrado, y estando de acuerdo con la posibilidad de descomponer lo complejo en elementos más simples, Chaitin se hace la siguiente pregunta:

¿Esa simplicidad da más información de la estructura del Universo o de nosotros mismos y nuestra forma de entenderlo?

Definiciones

• Número Normal: número real cuyos dígitos siguen una distribución aleatoria. Por ejemplo el número de Champernowne (la concatenación de todos los número naturales): 0.1234567891011121314151617... Cualquier cadena finita de números ocurre infinitas veces en los números PI y e con la misma frecuencia.
• Número trascendental: cualquier número complejo y no-algebraico, es decir, que no es solución a ningún polinomio de coeficientes racionales.

Publicaciones de Chaitin

• Algorithmic Information Theory, (Cambridge University Press, 1987),
• Information, Randomness & Incompleteness, (World Scientific, 1987),
• Information-Theoretic Incompleteness, (World Scientific, 1992),
• The Limits of Mathematics, (Springer-Verlag 1998),
• The Unknowable, (Springer-Verlag 1999),
• Exploring Randomness, (Springer-Verlag 2001),
• Conversations with a Mathematician, (Springer-Verlag 2002),
• From Philosophy to Program Size, (Tallinn Cybernetics Institute 2003),
• Meta Math!, (Pantheon 2005).

Enlaces externos

• Página personal de Chaitin
  • The Limits of Reason
• Chaitin en Wikipedia
• Omega en Wikipedia
• Complejidad de Kolmogorov
• Entrevista a Chaitin en Buenos Aires
• Imágenes de Chaitin

FIXME:

• corregir léxica, sintáctica y semánticamente el wikibook
• añadir links
• arreglar los links relativos
• añadir contenido:
  • definición formal de vida