Los límites de las matemáticas

Kurt Gödel

The same post in English

A finales del siglo XIX, Friedrich Ludwig Gottlob Frege, profesor de la universidad de Viena, emprendió un programa ambicioso: formalizar la aritmética mediante unos pocos axiomas y unas pocas reglas de deducción, de modo que todo teorema verdadero pudiese deducirse de los axiomas mediante cierto número de aplicaciones de las reglas de deducción. El resultado fue un libro monumental, Grundgesetze der Arithmetike (1893-1903), que entre otras cosas formalizó la teoría de conjuntos con una notación engorrosa, que pronto fue sustituida por la de Peano, que es la que usamos ahora.

Desgraciadamente para Frege, cuando estaba a punto de publicarse el segundo tomo de su libro, Bertrand Russell le envió una carta en la que demostraba que su formulación de la teoría de conjuntos daba pie a una inconsistencia. En la teoría de Frege, un conjunto puede pertenecer a otro conjunto. En particular, algunos conjuntos no pertenecen a sí mismos (como el conjunto de los números enteros, que no es un número entero), mientras otros sí pertenecen a sí mismos (como el conjunto de todos los conjuntos infinitos, que es infinito). Russell señaló que es posible definir el conjunto de todos los conjuntos que no pertenecen a sí mismos. Este conjunto lleva a una paradoja: si pertenece a sí mismo, no pertenece, y viceversa. La paradoja de Russell acabó con la obra de Frege, que tuvo que añadir apresuradamente un apéndice a su libro y abandonó la investigación sobre los fundamentos de las matemáticas.

Bertrand Russell y Alfred North Whitehead trataron de completar la obra de Frege en su libro Principia mathematica (1910-13), que estaba destinado a sufrir el mismo fin que el de Frege. En 1931, Kurt Gödel demostró su famoso primer teorema de incompletitud (Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme), que intuitivamente puede resumirse así: todo sistema formal consistente, con potencia similar a la aritmética, no es completo (contiene proposiciones verdaderas indecidibles). O sea: si partimos de un conjunto de axiomas y reglas de deducción, o bien acabaremos con un resultado inconsistente (como la paradoja de Russell), o habrá algún teorema verdadero que no podremos demostrar.

Informalmente, la demostración del teorema de Gödel se reduce a formular con notación matemática el siguiente teorema G: este teorema no se puede demostrar partiendo de los axiomas y reglas del sistema S. Si el teorema G fuese falso (o sea, sí se puede demostrar a partir de S) entonces S demuestra teoremas falsos, luego no es consistente. Por lo tanto, si S es consistente, el teorema debe ser verdadero, o sea, no se puede demostrar en S (eso es, precisamente, lo que afirma el teorema).

Alan Turing

El teorema de Gödel fue el primero de una serie de teoremas más o menos equivalentes. Uno de ellos es el problema de la parada, formulado y demostrado por Alan Turing, que se aplica a una familia de máquinas abstractas, que en su honor se llaman máquinas de Turing. Con estas máquinas se puede resolver cualquier problema abordable mediante un computador digital. De hecho, las máquinas de Turing son más potentes que los ordenadores, pues se supone que tienen memoria infinita, aunque con los tamaños de memoria actuales esta restricción casi siempre puede ignorarse.

Turing formuló así el problema de la parada: supongamos que conocemos la descripción de una máquina de Turing, que consta de dos partes: el programa que va a ejecutar la máquina y los datos de entrada que recibe. Antes de ponerla en marcha, ¿es siempre posible predecir si llegará a pararse, o si se meterá en un bucle cerrado que nunca termine?

Parece un problema sencillo, pero Turing demostró que no siempre es posible hacer esa predicción. Por supuesto, para máquinas poco complejas sí se puede. Pero el problema de la parada pregunta si la predicción puede hacerse siempre. Turing lo demostró por reducción al absurdo: supuso que el problema de la parada tiene solución y llegó a una contradicción. Por lo tanto, la hipótesis es falsa.

El hecho de que existan problemas no computables conmocionó a los informáticos, pues es una limitación teórica de la tecnología informática, muy diferente de los límites prácticos que hacen que algunos problemas intrínsecamente difíciles sean imposibles de resolver. Estos problemas se pueden resolver en teoría, pero haría falta un ordenador tan grande como el universo, funcionando durante toda la vida del universo. Uno de los problemas de este grupo tiene por objeto calcular la solución perfecta de una partida de ajedrez. En teoría, ese programa podría escribirse, pero su tiempo de ejecución sería inaceptable.

Roger Penrose

Durante los años sesenta, el matemático Gregory Chaitin demostró otro teorema parecido: la aleatoriedad de un conjunto de números enteros es indecidible. Esto se puede ilustrar con los dígitos de π, que cumplen las pruebas de aleatoriedad, pero no son aleatorios.

En 1989, Roger Penrose (en The emperor’s new mind) propuso la siguiente cuestión, inspirada en el teorema de Gödel: ¿cómo es que podemos demostrar que un teorema es verdadero, si no se puede demostrar matemáticamente a partir de un conjunto razonable de axiomas? Según él, esto podría indicar que la inteligencia humana es cualitativamente distinta de la de las máquinas computadoras.

Hilo Temático sobre Matemáticas: Anterior Siguiente

Manuel Alfonseca