Sobre las paradojas (II)

El sueño de un lenguaje infalible

Recordemos que, a comienzos del siglo XX, el matemático alemán David Hilbert expuso ante la comunidad científica una ambición extraordinaria: dotar a las matemáticas de una base absolutamente firme, libre de cualquier falla lógica. En el Congreso Internacional de Matemáticos celebrado en París en 1900, presentó una lista de veintitrés problemas fundamentales cuya resolución, a sus ojos, guiaría el rumbo de las matemáticas durante el nuevo siglo. Razón no le faltaba, aunque no como él imaginaba. Tres de estos problemas destacaban por su alcance filosófico:

1. Es la matemática completa, y, por tanto, ¿existe una manera de probar todo enunciado que sea verdadero?
2. Es la matemática consistente, y, ¿por tanto, libre de contradicciones?
3. ¿Existe un proceso (hoy diríamos algoritmo) capaz de determinar si un enunciado se sigue directamente de los enunciados básicos (axiomas) existentes?

Pero como vimos, en 1931 Kurt Gödel, con sus teoremas sobre incompletitud, demostró que ningún sistema formal lo suficientemente expresivo para albergar la aritmética podía ser simultáneamente completo y consistente. Existían verdades matemáticas indemostrables, y todo sistema que aspirase a la completitud debía, por fuerza, renunciar a garantizar su propia consistencia. Las dos primeras aspiraciones de Hilbert quedaban así descartadas de forma irremediable. Turing haría caer la tercera, conocida por el muy atractivo nombre de Entscheidungsproblem.

Máquina que (casi) piensan

Turing prosiguió su formación académica en el King’s College de Cambridge, tras haber obtenido una beca gracias a sus destacadas aptitudes matemáticas. Poco después, sabemos por su correspondencia con su madre que fue aceptado como miembro de la Cambridge Philosophical Society, una institución que, habiendo sido fundada en 1819, había contado entre sus filas con figuras tan notables como Charles Babbage, Niels Bohr, George Boole y Charles Darwin, entre otros. Para Turing, significaba no sólo un reconocimiento, sino también el acceso a una de las mejores bibliotecas científicas del país, que comenzó a frecuentar con asiduidad [4].

Fue en ese ambiente de estímulo intelectual donde empezó a madurar una inquietud profunda por los fundamentos de las matemáticas. Bajo la influencia del filósofo Richard Braithwaite y el lógico Max Newman, Turing se volcó en el estudio de la lógica formal y los problemas aún abiertos que había dejado al descubierto la obra de Kurt Gödel pocos años antes. Pronto, con apenas veintitrés años, Turing presentaría un trabajo revolucionario titulado On Computable Numbers, with an Application to the Entscheidungsproblem. En él formuló lo que más adelante se conocería como el problema de la detención, o Halting Problem, y propuso un modelo mental completamente nuevo para formalizar el concepto de cálculo mecánico: la máquina de Turing.

¿Pero qué es una máquina de Turing? Imaginemos una cinta infinita dividida en celdas, como un papel cuadriculado interminable, y un cabezal que se mueve sobre ella, leyendo y escribiendo símbolos de acuerdo con una serie de instrucciones. Esa cinta es la memoria, y el cabezal, junto con su conjunto de reglas, actúa como el cerebro del sistema. Aunque suena simple, este modelo abstracto tiene un poder inmenso: puede simular cualquier procedimiento computacional, cualquier algoritmo, cualquier programa. De hecho, todo ordenador moderno es, en esencia, una implementación práctica de esa idea. Incluso al escribir estas líneas, o al leerlas usted. Lo que Turing había concebido como una idea abstracta se convirtió, con el tiempo, en la piedra fundacional de la informática.

El enigma de saber si sabremos

Pero Turing amaba los desafíos (no sólo intelectuales, corrió varias maratones de forma competitiva durante su vida), de modo que el siguiente paso razonable en su discurrir acerca de los sistemas lógicos consistiría en llevar su modelo abstracto al límite: dado cualquier programa de ordenador y una entrada concreta, ¿era posible saber, de antemano y con total certeza, si ese programa terminaría alguna vez o se estaría ejecutándose por siempre jamás?

Supongamos, dijo, que existe una máquina o programa H capaz de analizar cualquier programa P y decirnos con seguridad si P se detendrá o no. Imaginemos también un nuevo programa, al que llamaremos D, que utiliza a H como subrutina. Es decir, usar H como procedimiento a ejecutar durante el propio desarrollo de D. Este programa D toma como entrada otro programa cualquiera, lo analiza usando H, y luego hace exactamente lo contrario de lo que H predice. Si H dice que el programa se detendrá, entonces D entra en un bucle infinito. Si H dice que el programa no se detendrá, entonces D se detiene de inmediato. Pero ¡ah! ¡Es en este punto que nos encontramos de nuevo con Epiménides y las paradojas! Porque, ¿qué pasaría si ejecutáramos D sobre sí mismo? Es decir, si H y D fueran la misma máquina. ¿Debería éste detenerse o no detenerse? Si H dice que sí, entonces D, por diseño, no se detiene. Si H dice que no, entonces D se detiene. En ambos casos, llegamos a una contradicción. En lenguaje matemático, D sólo se detendría si, y sólo si, D no se detiene.

En resumen, no existe ningún procedimiento (y la palabra clave aquí es universal, ya que los matemáticos gustan de trabajar con proposiciones siempre válidas, generales de forma absoluta) capaz de decidir, en todos los casos, si un programa terminará. El problema de la detención es, por tanto, indecidible. La ambición de Hilbert, Russell, Whitehead y tantos otros por una matemática perfecta, capaz de expresar cualquier fenómeno natural con absoluta definición se desvanecía.

Es cierto, ese sueño moría. Pero Turing no solo mostró lo que no podía alcanzarse: también definió con notable precisión qué significa computar, qué puede y no puede hacer una máquina. La paradoja se convirtió en cimiento. En cierto sentido, al señalar el abismo, nos mostró el camino. No era la primera vez que alguien soñaba con ello. Gottfried Wilhelm Leibniz, en el siglo XVII, había imaginado un lenguaje lógico universal, un calculus ratiocinator, con el que cualquier disputa racional pudiera resolverse como si se tratara de una suma [5]. Pero fue Turing quien primero se daría cuenta que lo que se atisbaba en el horizonte ya no era simplemente matemática: era la posibilidad de construir razonamientos en base a reglas y símbolos, de encontrar procesos de cálculo para responder preguntas generales de forma automática, de… De una Inteligencia Artificial.

Referencias

[1]: Hodges, Andrew. Alan Turing: The Enigma. Princeton University Press, 2014.

[2]: Cawthorne, Nigel (2014). Alan Turing : the enigma man. London: Arcturus Publishing. p. 18. ISBN 978-1-78404-535-7.

[3]: O’Connell H, Fitzgerald M. Did Alan Turing have Asperger’s syndrome? Irish Journal of Psychological Medicine. 2003;20(1):28-31. doi:10.1017/S0790966700007503

[4]: Copeland, B.J., Fan, Z. Did Turing Stand on Gödel’s Shoulders?. Math Intelligencer 44, 308–319 (2022). https://doi.org/10.1007/s00283-022-10177-y

[5]: Peckhaus, V. (2004). Calculus ratiocinator versus characteristica universalis? The two traditions in logic, revisited. History and Philosophy of Logic, 25(1), 3–14. https://doi.org/10.1080/01445340310001609315