Hace ya varios días leí una artículo sobre el número Omega, el número descubierto en los 80 por Gregory Chaitin a partir del problema de la parada de Turing y que parece introducir el azar en las matemáticas. Leí el artículo por encima, pero se me quedó un trozo dando vueltas por la cabeza: a partir de una cierta interpretación del número Omega se podía seguir que los problemas matemáticos que se pueden resolver (es decir, buena parte de las mátemáticas que conocemos) serían solo una pequeña parte dentro de un mar de proposiciones irresolubles que pertenecerían igualmente al conjunto de las mátematicas. Es una idea fuerte, pero se me quedó sobre todo porque enlaza con otra idea que me da vueltas desde que leí a Luhmann: como un sistema se define frente a su entorno reduciendo su complejidad. Realmente no se si estas dos cosas tienen algo que ver, pero a mi se me pegaron.

Bueno, el caso es que hoy (mientras estaba tendiendo la ropa) me he vuelto a acordar del número Omega y, ya que hoy es domingo y tengo tiempo, he decidido investigar más sobre el asunto. He tenido suerte y, además del artículo de New Scientist que había leido, he encontrado un resumen del propio Chaitin que lo explica bastante  bien para mi nivel de matemáticas (que es escolar) y que, sobre todo, pone su investigación en contexto. La historia es bonita, empieza en Leibnitz (en el siglo XVII), pasa por Hilbert, Gödel y Turing, y acaba explicando porqué un ordenador puede entrar de repente en un bucle infinito (ante la mirada desesperada del administrador de sistemas)y, más allá, cómo la calculada arquitectura que le suponemos a las matemáticas puede ser en realidad el resultado de conexiones determinadas encontradas casi al azar sobre un fondo de infinitos.

Que conste que voy a explicar ésto tal como lo he entendido, y que no soy ningún experto, pero bueno, vamos para allá (sigo + o – el resumen de Chaitin). Chaitin coloca a Leibnitz al inicio de la historia. En dos secciones (la V y VI) del “Discours de métaphysique”, se pregunta como podemos distinguir un mundo que puede ser explicado por la ciencia de uno que no, como determinar si algo de lo que vemos alrededor se puede ajustar a una ley científica o es puramente aleatorio (una pregunta sensata para un filósofo/científico en los inicios del racionalismo). Pone el ejemplo de alguien que deja caer varias manchas de tinta sobre una página de papel: si luego es posible trazar una curva matemática entre esos diversos puntos, la distinción que busca se establece por la proximidad o distancia que esa curva mantenga con el salpicado original. Cuanto más próxima, más compleja resulta y menos interés científico tiene (pues será solo válida en ese caso), y cuanto más distante (y esquemática) supondrá que las manchas siguen en realidad un pattern que puede utilizarse científicamente en otros casos.

A partir de esta idea, que se puede considerar algo aleatorio cuando su explicación es inútilmente compleja, Chaitin propuso un criterio para medir la complejidad que pasaba por el volcado de toda la cuestión a términos binarios. por una parte se medía la complejidad en bits de información (0 y 1) y por otra se substituían las equaciones matemáticas por programas informáticos. Esto permitía reducir a un común denominador y compara la complejidad de la teoría, en este caso el programa informático, con la complejidad de los datos que explica, o sea, el output del programa = la localización de las manchas de tinta.

As Leibniz observed, for any data there is always a complicated theory, which is a computer program that is the same size as the data. But that doesn’t count. It is only a real theory if there is compression, if the program is much smaller than its output, both measured in 0/1 bits. And if there can be no proper theory, then the bit string is called algorithmically random  or irreducible. That’s how you define a random string in algorithmic information theory.

Con todo esto, lo que Chaitin parece tener es un criterio para medir la complejidad, en términos de reducción de tamaño del programa que la gestiona, y un nombre para las cadenas que no de dejan reducir. Ahora pasamos a Hilbert, Gödel y Turing (sobre todo Turing). En 1920 Hilbert, uno de los matemáticos más famosos de su tiempo, lanzó un desafío urbi et orbe para intentar demostrar que toda la matemática se sigue de un sistema finito de axiomas escogidos correctamente y que tal sistema axiomático se puede probar consistente (wikipedia dixit), es decir, que la arquitectura de las matemáticas que sustentaba a si misma como los arcos de una catedral, un propósito que veo en paralelo con las pretensiones del positivismo por aquella época, que primero asumió y luego superó Wittgenstein.

Bueno, pues el llamamiento de Hilbert tuvo efectos inesperados. En 1931, Gödel publicó en Viena sus célebres teoremas que demostraban exactamente lo contrario: que que para todo sistema axiomático computable, si el sistema es consistente no puede ser completo, y la consistencia de los axiomas no puede demostrarse en el interior del sistema (wiki, wiki). En resumen, que la pretensión de que las matemáticas se demostraran como un sistema cerrado autosustentado era inviable. Los vieneses por aquella época (Wittgenstein también lo era, y Freud) acabaron por desmontar las pretensiones más tradicionales de la cultura europea.

Lo que no sabía es que el problema de la parada de Turing también era una respuesta a la propuesta de Hilbert. Mientras que la respuesta de Gödel es un loop teórico interno, la respuesta de Turing (que era inglés, y por lo tanto el empirismo se le supone) se sitúa en un contexto práctico. El problema es el siguiente: en 1936 Turing presentó el primer modelo de un computador digital, lo que se conoce como la “máquina de Turing” (que es el modelo lógico original de los ordenadores actuales). El diseño del modelo incluía una pregunta muy básica, ¿era posible predecir con antelación si un programa introducido en el ordenador iba a finalizar, proporcionando el output solicitado, y cuando? El caso es que Turing demostró que ésto no era posible. Los programas suelen terminar en un tiempo aceptable, pero a veces no.

Bueno, pues después de esta laaarga introducción, el descubrimiento del numero Omega por Chaitin tiene su origen en el problema de la parada de Turing. Copio la explicación de Chaitin en versión original:

Now, instead of looking at individual instances of Turing’s famous halting problem, you just put all possible computer programs into a bag, shake it well, pick out a program, and ask: “what is the probability that it will eventually halt?”. This probability is the number Omega.

An example will make this clearer: suppose that in the whole wide world there are only two programs that eventually halt, and that these programs, when translated into bit strings, are 11001 and 101. Picking one of these at random is the same as randomly generating these two bit strings. You can do this by tossing a coin and writing down a 1 if heads comes up, and a 0 if tails comes up, so the probability of getting a particular bit is 1/2. This means that the probability of getting 101 is 1/2 x 1/2 x 1/2 x 1/2 x 1/2 = 1/2^5. So the probability of randomly choosing one of these two programs is 1/2^3+ 1/2^5 = 0.15625.

Of course, in reality there are a lot more programs that halt, and Omega is the sum of lots of terms of the form 1/2^ N. Also, when defining Omega, you have to make certain restrictions on which types of programs are valid, to avoid counting things twice, and to make sure that Omega does not become infinitely large.

Anyway, once you do things properly you can define a halting probability Omega between zero and one. Omega is a perfectly decent number, defined in a mathematically rigorous way. The particular value of Omega that you get depends on your choice of computer programming language, but its surprising properties don’t depend on that choice.

And what is the most surprising property of Omega? It’s the fact that it is irreducible, or algorithmically random, and that it is infinitely complex.

A ver, que ahora entramos en la parte dura (si hay alguien entre el público que lo entienda mejor, se ruega un comentario), en principio Omega es un número que pretende concretar una probabilidad. Como en términos binarios las probabilidades son al cincuenta por ciento, el resultado es 1/2 elevado a lo que sea (es curioso el recurso a la moneda). El resultado ha de ser un número decimal entre el 0 y el 1, en el ejemplo es el 0.15625, un número de lo más normal y simpático. Vale, es un ejemplo, en realidad no es 1/2^5, sino 1/2^N (siendo N un comodín para cualquier número), y aquí es donde parece que la cosa se complica y aparece un Omega irreductible, aleatorio e infinitamente complejo, es decir, el tipo de resultado en el que el programa y el output tienen el mismo tamaño y que, según lo establecido por Leibnitz, pertenece a lo que no vale la pena explicar a través de la ciencia porque es un caso particular.

Pero, ¿cómo aparece todo ésto?¿cual es la diferencia entre 5 y N que “emborrona” el resultado y hace aparece Omega en todo su esplendor? La verdad es que no me queda claro (por mi insufi en matemáticas, desde luego), y la explicación que añade Chaitin me deja medio medio. Chaitin compara luego la resistencia del numero Omega a dejarse comprimir con la posibilidad de comprimir algoritmicamente la raiz cuadrada de 2. Lo que entiendo es que la raiz cuadrada de 2 es, asimismo un número irracional, con infinitas cifras decimales que no siguen un periodo definido, pero que puede comprimirse a partir de sus primeros decimales, que siempre serán los mismos, mientras que los primeros decimales de un número Omega son tan aleatorios como el resto y no sirven para esa faena.

Bueno, hasta aquí llego en el tema matemático y lo dejo aquí, pero conviene echar un vistazo a las consecuencias de todo esto, y esto supone pasar de los hechos demostrables a su interpretación, que puede ser discutible . Voy a ir rápido porque ya estoy cansado y ésto se ha hecho muy largo. Cortar y pegar. La primera consecuencia, y la que menciona Chaitin, es que las matemáticas no pueden sostener una teoría del todo (TOE) desde el momento en que incluyen el número Omega (y esto es grave, teniendo en cuenta que es uno de los objetivos de la física, de la teoría de las cuerdas, por ejemplo):

A mathematical theory consists of a set of “axioms” — basic facts which we perceive to be self-evident and which need no further justification — and a set of rules about how to draw logical conclusions.

So a Theory of Everything would be a set of axioms from which we can deduce all mathematical truths and derive all mathematical objects. It would also have to have finite complexity, otherwise it wouldn’t be a theory. Since it’s a TOE it would have to be able to compute Omega, a perfectly decent mathematical object. The theory would have to provide us with a finite program which contains enough information to compute any one of the bits in Omega’s binary expansion. But this is impossible because Omega, as we’ve just seen, is infinitely complex — no finite program can compute it. There is no theory of finite complexity that can deduce Omega.

So this is an area in which mathematical truth has absolutely no structure, no structure that we will ever be able to appreciate in detail, only statistically. The best way of thinking about the bits of Omega is to say that each bit has probability 1/2 of being zero and probability 1/2 of being one, even though each bit is mathematically determined.

That’s where Turing’s halting problem has led us, to the discovery of pure randomness in a part of mathematics. I think that Turing and Leibniz would be delighted at this remarkable turn of events. Gödel’s incompleteness theorem tells us that within mathematics there are statements that are unknowable, or undecidable. Omega tells us that there are in fact infinitely many such statements: whether any one of the infinitely many bits of Omega is a 0 or a 1 is something we cannot deduce from any mathematical theory. More precisely, any maths theory enables us to determine at most finitely many bits of Omega.

Esto conduce a la idea de que las matemáticas dejen de considerarse deductivas para pasar a ser experimentales, empíricas, pues se trataría de “encontrar” los segmentos que entran en juego equalizando o de cualquier otra manera. Ésto es lo que opina John Casti:

The fact that randomness is everywhere has deep consequences, says John Casti, a mathematician at the Santa Fe Institute in New Mexico and the Vienna University of Technology. It means that a few bits of maths may follow from each other, but for most mathematical situations those connections won’t exist. And if you can’t make connections, you can’t solve or prove things. All a mathematician can do is aim to find the little bits of maths that do tie together. “Chaitin’s work shows that solvable problems are like a small island in a vast sea of undecidable propositions,” Casti says.

Y a partir de aquí, lo que decía al principio, que el sistema de las matemáticas se mantenga reduciendo su complejidad con respecto a su entorno, un entorno en el que parece que las operaciones tienen una alta probabilidad estadística de dar infinito.

Anuncios