El cierre se puede comprar

1. Dos números pares

Verano de 1954, Instituto de Estudios Avanzados de Princeton. Allí había una computadora de válvulas, una de las primeras que se habían construido en el mundo. Toda su memoria sumaba mil veinticuatro palabras de máquina. En ese espacio tenían que caber el programa, las fórmulas que debía tratar y cuanto fuera apareciendo durante el cálculo.

Un lógico de veintiséis años escribió un programa para ella. Se llamaba Martin Davis.

Por entonces, casi todas las computadoras hacían cuentas. Este programa juzgaba enunciados. Se le entregaba una frase sobre los números enteros y avanzaba paso a paso, conforme a unas reglas inamovibles. El algoritmo de decisión en que se apoyaba garantizaba que, en una máquina ideal sin límites de memoria, acabaría deteniéndose y daría la respuesta correcta. La computadora real podía quedarse sin memoria antes de llegar hasta allí. Todavía no se había acuñado la expresión «inteligencia artificial».

Muchos años después, Davis escribió que la mayor hazaña de aquel programa había sido demostrar que la suma de dos números pares es par.

Había ironía en sus palabras, pero ninguna exageración. Una máquina que ocupaba una habitación entera había logrado, en su mejor momento, demostrar algo que sabe cualquier escolar.

De ahí salen dos preguntas. Entre todas las matemáticas, ¿por qué precisamente ese pequeño rincón podía confiarse a una máquina, con la certeza de que cuanto declarara verdadero lo sería? Y, si podía decidir, ¿por qué su mejor resultado era tan poca cosa? La propia máquina no tardó en responder a la segunda pregunta, con algo bastante más grave que aquella ironía de Davis. La respuesta a la primera estaba en Varsovia, veinticinco años antes.

Martes 24 de septiembre de 1929, a las diez y media de la mañana. El Primer Congreso de Matemáticos de los Países Eslavos celebraba su segunda jornada en Varsovia. El primer turno de la primera sección se había reservado a un estudiante que aún no había obtenido el título de máster. Se apellidaba Presburger, estudiaba matemáticas en la Universidad de Varsovia y tenía veinticuatro años.

Vale la pena detenerse un momento en aquel congreso. En la apertura, Fraenkel habló de Cantor; Tarski dio dos conferencias. La mayoría de los asistentes eran polacos, pero algunos habían llegado de Japón y otros de Texas. Las actas admitían trabajos en cinco lenguas europeas, con predominio del alemán y el francés. Terminadas las sesiones, un grupo tomó un tren con coches cama hacia Poznań, donde Kuratowski continuó hablando de topología.

La intervención de Presburger se publicó después en las actas: diez páginas de texto y una de añadidos, sin numerar. El título venía a decir: «Sobre la completitud de un sistema de aritmética de los enteros en el que la suma es la única operación». Al principio, una nota al pie casi inadvertida precisaba dos cosas: el resultado se había obtenido en mayo de 1928 y el problema lo había propuesto Tarski.

No era una pregunta caída del cielo. En aquellos años, Hilbert y los suyos perseguían algo mucho mayor: un procedimiento mecánico único que permitiera decidir si una fórmula dada de lógica de primer orden era válida en todas las interpretaciones. Lo llamaban el problema de decisión. Aún no había computadoras. Un procedimiento mecánico era una serie de reglas escritas sobre el papel, tan estrictas que hasta alguien que no entendiera nada de matemáticas pudiera seguirlas y obtener la respuesta correcta. La aspiración de la escuela de Hilbert era disponer de semejantes reglas para todas las matemáticas.

Tarski recortó una porción muy pequeña de ese problema y se la dio a un estudiante. Presburger volvió con esta respuesta: para esa porción, sí. Había un fragmento de la aritmética de los enteros en el que podía resolverse la verdad o falsedad de cualquier enunciado; además, un mismo procedimiento, aplicado a cualquiera de ellos, entregaba la respuesta tras un número finito de pasos. Eso fue lo que Davis llevó a las válvulas veinticinco años después. Antes de que pudiera construirse la máquina, ya estaba construida sobre el papel.

Los episodios anteriores contaban casi siempre la historia contraria. La teoría de conjuntos había producido contradicciones; la disputa por los fundamentos llevaba veinte años; un teorema afirmaba que una aritmética cuyos axiomas pudieran enumerarse mediante un programa, si era suficientemente potente, no podía ser a la vez consistente y completa. Y aquí había un estudiante que, ante un aula llena, presentaba en diez páginas una aritmética a salvo de ese problema. Había obtenido el resultado en 1928 y lo había expuesto en el congreso de 1929: tres y dos años, respectivamente, antes de la publicación de aquel teorema en 1931.

La pregunta, entonces, merece formularse así: ¿hasta qué punto tiene que ser débil una aritmética para ser completa y venir, además, con una misma máquina capaz de resolver todas sus preguntas? La respuesta es mucho más complicada que quitar la multiplicación. Y mucho más interesante.

2. Lo que no se puede decir

Si solo tenemos monedas de tres y de cinco, ¿podemos reunir una cantidad exacta? Once, sí. Siete, no. ¿Habrá una cantidad a partir de la cual podamos formar todas las demás? La hay: desde ocho en adelante, ninguna se nos escapa.

El lenguaje de Presburger permite formular todas esas preguntas. Y permite decidirlas todas.

Su objeto era una aritmética de los enteros cuya única operación era la suma. Su lenguaje contenía el signo de sumar, el cero y el uno, la igualdad y las relaciones de orden, palabras como «existe» y «para todo». También podía hablar del triple de un número: bastaba con sumar ese número consigo mismo y una vez más. Al enunciar sus axiomas, Presburger ya advertía que, al no haber signo de multiplicación, una escritura de ese tipo debía entenderse como una suma repetida un número fijo de veces. Que varios números sumen otro; cuánto mayor es un número que otro; que un número deje resto tres al dividirlo entre siete; que varios enteros satisfagan a la vez una serie de condiciones semejantes: todo eso podía expresarse y decidirse. No eran los restos de una aritmética desmantelada. Era un mundo pequeño, pero entero.

Lo que faltaba era el producto de dos variables. Por eso, ciertas cosas ni siquiera podían decirse en aquel lenguaje: que un número es el producto de otros dos; que un número es un cuadrado; que es primo; que un número divide a otro cuando ambos son variables.

Aquí pesa todo el sentido de «no se puede decir». No significa que resulte difícil demostrarlo, sino que no existe una fórmula capaz de expresarlo de manera uniforme. Los conjuntos de números que ese lenguaje puede delimitar tienen una forma muy regular: a partir de cierto punto, repiten una pauta periódica. Los cuadrados y los números primos no se distribuyen así. En aquel mundo no había siquiera una manera de nombrarlos como tales. «¿Es primo este número?», una de las preguntas más antiguas de la teoría de números, no podía formularse en el mundo de Presburger.

Se había perdido capacidad de expresión, no capacidad de demostración. Son cosas distintas.

Conviene separar tres palabras que, a partir de aquí, seguirán caminos diferentes. Completitud significa que la teoría puede pronunciarse a favor o en contra de cada enunciado de su lenguaje: no habrá frases como las del episodio diecisiete, imposibles tanto de demostrar como de refutar. Decidibilidad significa otra cosa: existe un procedimiento mecánico único al que podemos entregar cualquier enunciado de ese lenguaje, con la garantía de que se detendrá después de un número finito de pasos y responderá correctamente.

Entre ambas hay un puente muy corto. Supongamos que una teoría es completa y que sus axiomas pueden enumerarse uno tras otro. También podrán enumerarse, una tras otra, todas sus demostraciones. Ante un enunciado, basta con empezar esa enumeración y esperar a que aparezca una demostración de él o de su negación. La completitud garantiza que una de las dos aparecerá, de modo que el procedimiento acabará deteniéndose. Presburger lo señalaba ya al comienzo de su artículo: por su carácter efectivo, la prueba de completitud proporcionaba también un método para determinar si un enunciado era verdadero. Una demostración entregaba, de paso, una máquina.

La palabra «completo» exige todavía otra precisión. No significa que la teoría lo sepa todo. Significa que puede resolver cualquier cosa que su lenguaje permita decir. Lo que ese lenguaje no puede expresar queda fuera incluso de las preguntas. Cuanto menos pueda decir un sistema, más fácil le será ser completo. Parece un elogio. Es la primera línea de la factura.

La tercera palabra es viabilidad. Que exista un procedimiento y que ese procedimiento pueda ejecutarse con el tiempo, la memoria y las máquinas de que disponemos los seres humanos son cosas diferentes. Las dos primeras palabras nombran propiedades lógicas; la tercera pregunta, además, por la complejidad y por los recursos reales. Una computadora con mil veinticuatro palabras de memoria iba a poner muy pronto esa diferencia sobre la mesa.

3. Eliminar una palabra

El método central de aquella máquina se llama eliminación de cuantificadores. En la aritmética de Presburger suele empezarse por ampliar el lenguaje con predicados de congruencia con módulos fijos o de divisibilidad por números fijos; los cuantificadores se eliminan después en esa ampliación equivalente.

Un enunciado puede contener expresiones como «existe algún número» o «para todo número». Eliminar un cuantificador no consiste en adivinar cuál es ese número. Consiste en sustituir el enunciado entero por otro exactamente equivalente que ya no hable de él.

Un ejemplo mínimo. ¿Existe un entero que, sumado consigo mismo, dé cierto número que nos han dado? Ahí aparece «existe un entero». Al eliminarlo, queda una condición que solo se refiere al número dado: que sea par.

Nada más. «Existe un entero que, sumado consigo mismo, da ese número» se convierte en «ese número es par». La segunda frase ya no menciona el entero que buscábamos y puede comprobarse directamente. El artículo de Presburger contiene ejemplos de esa clase: una ecuación aditiva con un «existe» se transforma en una condición sobre los restos y los demás números que intervienen. También trataba de números pares el mayor éxito de la computadora de Davis. Dentro de sus válvulas se sucedían, paso a paso, sustituciones como esas.

Probemos ahora en otro mundo. ¿Existe un número real cuyo producto consigo mismo sea igual a un número dado? Después de eliminar el cuantificador, queda esta condición: el número dado debe ser mayor o igual que cero. El número que buscábamos ha desaparecido; solo queda una afirmación sobre el que ya teníamos.

Repitiendo la operación, un enunciado sin variables libres acaba convertido en una condición cuya verdad o falsedad puede comprobarse directamente. Así se obtiene el procedimiento de decisión. El avance de Tarski consistió en llevar esa misma idea al mundo de las igualdades y desigualdades polinómicas sobre los números reales. Allí había suma, multiplicación, relaciones de orden y cuantificadores. Y los cuantificadores seguían pudiendo eliminarse.

Con ese paso entró también una disciplina: la geometría. Por geometría elemental, Tarski entendía los problemas que, una vez introducidas coordenadas, podían traducirse a expresiones algebraicas sobre los reales. Fijado un sistema de coordenadas cartesianas, los puntos se representan mediante coordenadas reales; las distancias, la alineación de puntos, la perpendicularidad y las circunferencias pueden describirse mediante un número finito de igualdades o desigualdades polinómicas. Las proposiciones geométricas correspondientes entran entonces en la máquina. Quedan fuera los enunciados generales sobre conjuntos arbitrarios de puntos o funciones arbitrarias. El alcance lo decide el lenguaje elegido, no el nombre «geometría».

A primera vista, nada obligaba a que esto funcionara. La palabra «existe» parece ordenar una búsqueda en un dominio infinito. Una máquina no puede ir probando uno a uno infinitos números: si no encuentra lo que busca, no se detendrá jamás. Eliminar esa palabra significa poder sustituir la búsqueda interminable por un enunciado finito que se comprueba directamente. Ahí está la mitad de la respuesta a por qué precisamente ese pequeño mundo podía confiarse a una máquina: cada uno de sus «existe» podía eliminarse. Que la sustitución sea posible depende de cuánta regularidad tenga la forma de ese mundo. Donde la hay, se puede hacer. Donde falta, no.

Lo que entrega es una respuesta, no una comprensión. El resultado de las sustituciones puede ser descomunal y no tener el aspecto de una demostración que a un ser humano le parezca elegante. Pero el método ofrece algo de mucho mayor alcance que responder sí o no: permite saber qué conjunto de cosas delimita, en ese mundo, una afirmación construida con «existe» y «para todo». La teoría de modelos posterior encontraría en esa información estructural el valor principal de la eliminación de cuantificadores.

4. Dónde está la frontera

Si quitar la multiplicación permite obtener una máquina, la siguiente pregunta parece inevitable: ¿está la frontera en el signo de multiplicar?

No. Dos ejemplos deshacen esa conjetura desde lados distintos. El primero es la aritmética de Skolem: se toma la aritmética de los naturales, se conserva solo la multiplicación y se retira la suma. Sigue siendo decidible. El segundo es todavía más contundente: los reales de Tarski. Allí están la suma, la multiplicación y las relaciones de orden, y la teoría también es decidible.

La suma por su lado se deja dominar. La multiplicación por el suyo, también. El cambio de naturaleza ocurre cuando las dos se reúnen sobre los enteros.

La explicación no está en la lista de símbolos. Unidas, la suma y la multiplicación de enteros permiten construir codificaciones de enorme riqueza: sucesiones finitas, demostraciones, cálculos paso a paso, todo puede reescribirse como relaciones entre enteros. Esa es precisamente la capacidad que necesitaba la codificación del episodio diecisiete. La aritmética de Presburger no puede hacerse cargo de ese trabajo, porque ni siquiera permite definir el producto de dos variables. Por eso se queda por debajo del umbral en la tercera de las tres condiciones de aquel episodio. No queda al margen del teorema por ser inconsistente ni por carecer de una axiomatización efectiva. Lo que no alcanza es la potencia expresiva necesaria.

Tarski formuló el contraste sin rodeos en su libro: una teoría lo bastante potente como para abarcar todos los enunciados pertinentes de la aritmética ordinaria de los enteros, con suma y multiplicación, no admite un procedimiento uniforme de decisión como ese.

También hizo un experimento de frontera especialmente limpio. En el lenguaje de los reales no se puede definir de manera uniforme «este número es entero». Pero si se permite restringir directamente las variables a los enteros, entran preguntas de esta clase: ¿hay soluciones enteras para una ecuación en la que el cubo de un número más el cubo de otro es igual al cubo de un tercero? Con ellas se cuela la aritmética de los enteros y desaparece la posibilidad de una decisión uniforme. La expresión es la misma; basta con que las variables recorran los enteros en lugar de los reales para que cambie por completo su destino lógico.

Lo fácil y lo difícil no están en los símbolos. Están en el terreno por el que dejamos moverse a las variables.

Lo que ocurría al otro lado del umbral quedó fijado más tarde de manera definitiva. Y entre quienes lo fijaron había alguien a quien ya conocemos. El décimo problema de la lista que Hilbert presentó en 1900 pedía decidir, dada cualquier ecuación polinómica con coeficientes enteros, si tenía soluciones enteras. Era justamente ese tipo de problema: variables que se multiplican y toman valores enteros. Desde sus años de posgrado, Martin Davis no dejó de perseguirlo durante toda su vida. En el verano de 1954, mientras instalaba en las válvulas de Princeton una máquina para este lado del umbral, ya llevaba años buscando al otro lado.

Durante más de una década, Davis fue abriendo ese camino junto con Putnam y Julia Robinson. La última pieza la puso Matiyasévich. Él mismo recordaba con precisión el momento: el 29 de enero de 1970 expuso públicamente la solución por primera vez, en Leningrado, con Tseitin entre los asistentes. La respuesta era que no existía ningún procedimiento general. Un mismo hombre había construido una máquina con un pie a este lado del umbral y, con el otro pie al otro lado, había ayudado a demostrar que la máquina no podía construirse.

Así que el umbral no dibuja una línea limpia. En 1936, Church y Turing demostraron que no existe un procedimiento uniforme de decisión para la lógica de primer orden en general. Con eso se frustró la aspiración de Hilbert para el conjunto de las matemáticas. Pero por debajo del umbral se encuentran territorios de procedencias muy distintas: la aritmética lineal, el álgebra de los reales, los cuerpos algebraicamente cerrados y, más adelante, muchas estructuras surgidas del estudio de los autómatas. Tampoco son iguales las razones de su decidibilidad: unas se apoyan en el orden; otras, en la clausura algebraica, en los autómatas o en la eliminación de cuantificadores. En 1950, Trakhtenbrot demostró además que restringirse a las estructuras finitas no resuelve el problema general de decisión. Lo que queda en la historia de la lógica no es, por tanto, una recta que vaya de lo decidible a lo indecidible. Es un mapa: se buscan, a un lado, los fragmentos decidibles más grandes y, al otro, las extensiones indecidibles más pequeñas.

5. Varsovia y un libro que no llegaba a la imprenta

Presburger no era un estudiante aislado en la periferia que hubiera escrito por casualidad un artículo. Varsovia era entonces uno de los lugares de Europa que concentraban más actividad en lógica. Formaba parte de una tradición más amplia, la escuela de Leópolis-Varsovia, fundada por Twardowski. Entre sus figuras de entreguerras estaban Ajdukiewicz, Kotarbiński, Leśniewski, Łukasiewicz y Tarski. Su florecimiento coincidió con los veintiún años que separaron la recuperación de la independencia polaca del estallido de la guerra; durante ese tiempo, la lógica fue convirtiéndose en su rama más visible. Si acercamos la mirada al círculo de lógicos de Varsovia, en el centro encontramos a Łukasiewicz, Leśniewski y Tarski. A su alrededor, Lindenbaum, Presburger y muchos estudiantes.

Presburger no se limitaba a frecuentar aquel círculo. Trabajaba en él. Fue él quien preparó, a partir de las clases orales, los apuntes del curso de lógica matemática de Łukasiewicz.

También la red de publicaciones era densa. Los matemáticos polacos contaban con revistas especializadas como Fundamenta Mathematicae, y había otras dos en Leópolis y Cracovia. Tampoco Varsovia y Viena eran dos islas sin contacto. Tarski viajó a Viena en 1930; Carnap visitó Varsovia ese mismo año; Tarski volvió a Viena en 1935. Los nombres vieneses de los episodios quince y diecisiete y los nombres varsovianos de este episodio pertenecían, en aquellos años, a la misma red.

Las bases de datos de artículos que vendrían después borrarían por completo las circunstancias en que vivía Tarski. Había nacido con el apellido Teitelbaum. En 1923, él y su hermano lo cambiaron por Tarski y se convirtieron al catolicismo, aunque él no era creyente. Tenía más de un motivo: quería ser polaco y sabía lo difícil que resultaba para un judío conseguir un nombramiento universitario en la Polonia de entonces. Tras doctorarse en Varsovia en 1924, pasó muchos años enseñando matemáticas en un instituto de secundaria, mientras conservaba un puesto modesto en la universidad. En 1939 solicitó una cátedra en Leópolis y no la obtuvo. Algunos de los grandes resultados de la lógica mundial de aquellos años salieron de un hombre que, al mismo tiempo, daba clases en secundaria.

Encontró su procedimiento de decisión para el álgebra de los reales en 1930. Las notas históricas al final del libro retroceden aún más: parte de los resultados ya había aparecido en sus cursos de 1926 a 1928. Los estudiantes de Varsovia que se sentaban entonces en su aula habían oído una parte de aquella teoría. Fuera del aula, habría que esperar otros veinte años para leerla.

Después, el libro comenzó su propio recorrido. Una editorial parisina iba a publicarlo en 1939; la guerra lo impidió. Lo rescató una institución de investigación estadounidense. En 1948, el Proyecto RAND de las Fuerzas Aéreas de Estados Unidos se interesó por el problema de decisión. Se recuperó el manuscrito que llevaba nueve años guardado; McKinsey colaboró en su preparación y revisión, y acabó impreso como uno de los informes numerados de RAND. En mayo de 1951 apareció una nueva versión revisada, y desde entonces suele citarse con la fecha de 1951. Siete u ocho años después de aquella primera publicación en RAND, las computadoras de la misma institución ejecutarían otro tipo de programa para demostrar teoremas.

Entre el hallazgo del procedimiento y la aparición del libro en una forma que pudiera circular internacionalmente pasaron dieciocho años. La demora a partir de 1939 tiene una causa clara: la guerra. Para los nueve años anteriores, de 1930 a 1939, seguimos sin encontrar una explicación.

En este tramo de la historia se pueden documentar todos los años. Salvo uno.

Presburger nació en Varsovia el 27 de diciembre de 1904. Terminó la secundaria en 1923 y entró después en la Universidad de Varsovia. Solo existe un estudio dedicado específicamente a su vida: la biografía que Zygmunt publicó en 1991, basada sobre todo en los expedientes de estudiante conservados por la universidad. Más tarde, esos documentos se digitalizaron en alta resolución, se ordenaron y se hicieron públicos: formularios de matrícula, cursos realizados, papeles de graduación. Que obtuvo el título de máster en matemáticas en octubre de 1930 todavía puede comprobarse hoy, página por página.

Después, el rastro se corta. Era un judío polaco y murió en el Holocausto nazi, probablemente hacia 1943. Incluso en la biografía especializada, ese año lleva un signo de interrogación. La fecha exacta, el lugar y lo que vivió al final no están documentados con la certeza que ofrecen los papeles de sus años de estudiante.

Diez páginas que un hombre escribió cuando tenía veintitantos años llevan más de setenta años ejecutándose en una máquina tras otra. Cómo murió ese hombre, en cambio, no podemos escribirlo.

6. Otro camino

Volvamos a la computadora del verano de 1954.

Estaban el procedimiento de decisión y la máquina. Pero Davis no tardó en chocar contra un muro. Sobre el papel, el método constaba de unos pocos pasos. En la computadora había que empezar por llevar las fórmulas a cierta forma normal, y esa reescritura las hinchaba: las combinaciones de condiciones se acumulaban unas sobre otras; una línea breve podía multiplicar varias veces su longitud. Las mil veinticuatro palabras de memoria se quedaban pequeñas enseguida. Ahí empezó la poca fe que Davis tendría después en los procedimientos de decisión más complejos.

Aquella máquina permitió ver por primera vez la diferencia con los propios ojos: poder decidir no significa poder pagar la decisión.

Dos años después, alguien atacó el problema desde el otro extremo. Newell y Shaw, de RAND, junto con Simon, del Instituto Tecnológico Carnegie, construyeron un programa para demostrar teoremas lógicos. Trabajaba con las proposiciones iniciales de los Principia Mathematica de Whitehead y Russell. No seguía unas reglas que garantizaran llegar a un resultado. Elegía dónde buscar: primero, el camino que pareciera más cercano al objetivo; si había demasiadas ramas, cortaba algunas. Cuando encontraba una demostración, la entregaba. Cuando no la encontraba, solo podía decir eso: no la he encontrado. Entre «no la he encontrado» y «no existe» mediaba precisamente lo que tenía la máquina de Davis y le faltaba a esta: una garantía. La expresión «inteligencia artificial» no llevaba aún un año en circulación.

Un camino garantizaba una respuesta, pero enseguida reventaba la memoria. El otro renunciaba a garantizar que siempre encontraría una demostración, precisamente para no reventarla; las demostraciones que sí encontraba debían seguir respetando reglas de inferencia correctas. Ahí se bifurcaron los caminos.

En la bifurcación había un matemático chino. Wang Hao nació en Jinan en 1921, se graduó en la Universidad Nacional Asociada del Suroeste, en Kunming, y después se trasladó a Estados Unidos para trabajar en lógica matemática. En el verano de 1958 escribió varios programas en el laboratorio de investigación de IBM en Poughkeepsie, estado de Nueva York, con una de las grandes computadoras de la época. Uno de ellos demostró todos los teoremas de los cinco primeros capítulos de los Principia Mathematica, más de doscientos. Tardó unos treinta y siete minutos. Doce treceavas partes de ese tiempo se gastaron en leer los datos e imprimir los resultados; la demostración propiamente dicha ocupó menos de tres minutos.

Recogió los resultados en un artículo cuyo título, «Hacia unas matemáticas mecanizadas», parecía dar una nueva forma al viejo deseo de la escuela de Hilbert. En un pasaje no se anduvo con miramientos. Newell y sus colaboradores habían comparado las heurísticas con los algoritmos, pero el algoritmo elegido para la comparación era especialmente torpe. Pretender demostrar la superioridad de las heurísticas tomando como rival un algoritmo particularmente ineficiente, venía a decir Wang, difícilmente podía considerarse un juego limpio.

De aquellos resultados extrajo además una lección. Incluso en un campo bastante rico, la mayoría de los teoremas que de hecho se demuestran solo utiliza una fracción muy pequeña de toda su potencia. Decir poco es la condición para que una máquina pueda decidir. Y lo que las personas realmente quieren demostrar suele necesitar, de entrada, muy poco.

En 1983 recibió el primer premio a un hito en la demostración automática de teoremas, instituido por la Conferencia Internacional Conjunta de Inteligencia Artificial. Casi veinte años después, cuando Davis escribió la historia de aquellos comienzos, puso bajo el título una dedicatoria: «En memoria de Wang Hao».

7. El precio se calcula aparte

Tras la bifurcación, cada camino avanzó por su cuenta durante casi veinte años.

Por la vía de las heurísticas aparecían cada vez más programas y se hacían promesas cada vez mayores. En 1973, el Consejo de Investigación Científica del Reino Unido encargó al matemático aplicado Lighthill una evaluación general de la inteligencia artificial. En su informe reaparecía una expresión: explosión combinatoria. Los programas funcionaban bien con problemas pequeños y despejados. Al llevarlos a la escala del mundo real, las posibilidades que había que explorar se multiplicaban hasta hacer interminable la búsqueda.

Al año siguiente llegó desde el otro lado un resultado aún más frío. En 1974, Fischer y Rabin no preguntaron si el procedimiento de Presburger era rápido, sino si algún procedimiento podía llegar a ser, en lo fundamental, mucho más rápido. La respuesta fue no. Para ese fragmento de la aritmética, se diseñe el método general que se diseñe, siempre habrá fórmulas de este tipo: cada pequeño aumento de la entrada obliga a elevar al cuadrado el número de pasos necesarios. Es lo que se llama una cota inferior doblemente exponencial. En 1978, Oppen añadió una cota superior. El problema quedó encerrado entre dos paredes altísimas, una por arriba y otra por abajo.

Eso no significa que todas las fórmulas de esa longitud sean igual de difíciles. Significa que cualquier procedimiento general tendrá que enfrentarse a entradas así de malas. Tampoco se trata de un programa mal escrito: es una propiedad del problema. Fischer y Rabin estudiaron además la longitud de las demostraciones. Bajo las condiciones apropiadas, hay enunciados que pueden demostrarse, pero cuyas demostraciones tienen que ser extraordinariamente largas. Ser decidible, ser demostrable y permitir que alguien llegue a tener entre las manos una demostración que pueda terminar de leer resultaron ser, otra vez, tres cosas distintas.

Los dos caminos fueron a encontrarse ante el mismo muro. Lighthill describía el obstáculo con que tropezaba todo un campo al enfrentarse a la escala del mundo real. Fischer y Rabin decían algo más: aun si nos retiramos al fragmento de aritmética más pequeño, más limpio y mejor provisto de garantías, el muro sigue allí.

Con los reales volvió a ocurrir la misma historia. El método de Tarski demostraba que existía un procedimiento de decisión, pero no era un algoritmo que pudiera utilizarse en la práctica. El primer método completo que suele considerarse realmente ejecutable se atribuye a Collins, en 1975. Consistía en dividir el espacio real de varias dimensiones en un número finito de regiones, de modo que el signo de cada polinomio de entrada permaneciera constante dentro de cada región. Así, una pregunta sobre infinitos puntos pasaba a resolverse mediante comprobaciones representativas en un número finito de regiones. El método acabaría siendo una de las bases de los sistemas de álgebra computacional. Pero el número de regiones podía crecer de forma doblemente exponencial con el número de variables. En 1988, Davenport y Heintz demostraron que la culpa tampoco era enteramente del método: la eliminación general de cuantificadores sobre los reales tiene, por sí misma, dificultades de ese orden. En las décadas de mejoras que siguieron, la línea principal de trabajo no fue derribar esa cota inferior, sino evitar trabajo innecesario: mejorar las proyecciones y dividir solo las regiones que de verdad exige el problema concreto.

En geometría, alguien eligió comprar de otra manera. Entre 1976 y 1977, Wu Wenjun empezó en Pekín a llevar la demostración de teoremas geométricos a la computadora. Más tarde escribiría, en un prólogo, que el teorema de mecanización de Tarski abarcaba mucho de la geometría elemental, pero resultaba demasiado ineficiente. Su propio método convertía el problema geométrico en un sistema de ecuaciones polinómicas y dejaba de momento a un lado los enunciados que incluían relaciones de orden. Al estrechar un poco el campo de las preguntas, la máquina podía ponerse a trabajar. Así la máquina demostró una serie de teoremas geométricos nada triviales.

Lo llamó mecanización de las matemáticas y dijo haberse inspirado en la matemática china antigua. Para él, los Nueve capítulos sobre el arte matemático y el comentario que Liu Hui les añadió en el año 263 eran representantes clásicos de la tradición oriental de algoritmos para la mecanización matemática. El Liu Hui del episodio cinco aparecía aquí reconocido como precursor por un matemático del siglo XX. En ese mismo prólogo, Wu recordó también las más de doscientas proposiciones que la máquina de Wang Hao había demostrado en tres minutos.

Entre ser decidible y ser utilizable queda, pues, una grieta. La decidibilidad matemática pregunta si hay un procedimiento uniforme que garantice detenerse al final y responder correctamente. No promete unos segundos, ni cien años, ni siquiera que basten todos los recursos permitidos por este universo. La utilidad en ingeniería pregunta otra cosa: ante los problemas que realmente aparecen, con una máquina, un tiempo y una memoria determinados, ¿consigue el programa dar a menudo resultados útiles con rapidez? Una pregunta puede recibir un sí y la otra un no. De hecho, ocurre con frecuencia.

También es cierto a la inversa. Un peor caso desastroso no equivale a la inutilidad. Muchos procedimientos de decisión tienen un comportamiento teórico pésimo en el peor caso y, sin embargo, funcionan bastante bien con los problemas que deben resolver en la práctica. Reaparece la lección de Wang Hao: la mayoría de los problemas que nos encontramos no vive en el rincón del peor caso.

8. Una cuenta de tres columnas

Volvamos al título. ¿Se puede comprar el cierre? Sí. Se compró dos veces, y lo adquirido no fue lo mismo en ambas ocasiones.

Presburger obtuvo un fragmento completo y decidible de la aritmética de los enteros. El precio fue dejar sin expresión buena parte de la teoría de números. Tarski obtuvo un procedimiento uniforme de decisión para el álgebra de los reales y, con ella, para la geometría elemental; él no había quitado nada. Su precio estaba en otra parte: aquel lenguaje, por su propia naturaleza, no podía decir «este número es entero». Ninguno de los dos hizo una compra en un mercado. Ambos estudiaron un objeto matemático concreto y descubrieron que tenía una forma especialmente regular. La «compra» es la figura que reconocemos al mirar atrás. No había nadie pagando entonces.

Esos dos resultados han perdurado sobre todo en dos disciplinas que vinieron después. La eliminación de cuantificadores de Tarski se convirtió en una técnica básica de la teoría de modelos; los reales y los cuerpos algebraicamente cerrados, en ejemplos elementales de sus manuales. La aritmética de Presburger entró, en cambio, en la verificación de programas. Que un programa sea correcto depende muchas veces de índices de arreglos, contadores de bucles y relaciones lineales entre enteros: precisamente la clase de cosas que ese lenguaje sabe decir. En 1972, Cooper transformó el método de Presburger en una versión práctica para computadoras. Su artículo, titulado «Demostrar teoremas en una aritmética sin multiplicación», apareció en la colección Machine Intelligence. Entre los programas que hoy ayudan a los matemáticos a comprobar demostraciones línea por línea, algunos incorporan un módulo llamado «Procedimiento de decisión para la aritmética de Presburger». Dentro está la versión de Cooper.

¿Qué nos llevamos de todo esto?

Que un sistema tenga respuesta para cada enunciado que puede formular suena a una proeza. También es un inventario de todo lo que no puede decir. Para juzgar una manera de hablar, contemos primero las preguntas que no puede responder y después las que sí. Cuando puede contestarlas todas, lo habitual es que se le esté preguntando demasiado poco.

Desde aquella computadora de 1954, todas las máquinas construidas para responder preguntas pueden anotarse en el mismo libro de cuentas. Tiene tres columnas. En una se apunta qué podemos preguntarles; en otra, si sus respuestas vienen con garantía; en la tercera, cuánto cuesta cada respuesta.

Las diez páginas de Presburger dicen que, si estrechamos lo suficiente la columna de las preguntas, podemos llenar la de las garantías. Aquella afirmación del libro de Tarski, junto con los resultados de Church y Turing de 1936, dice que, en cuanto abrimos las preguntas a la suma y la multiplicación de enteros, ya no es posible llenar la columna de las garantías. Fischer y Rabin dicen que incluso si dejamos las preguntas tan estrechas como Presburger y llenamos por completo las garantías, habrá ocasiones en que no podamos pagar lo que figure en la columna del coste.

La máquina de Davis llenó la columna de las garantías y se estrelló contra la del coste. El programa de 1956 dejó vacía la garantía para abaratar el precio. Wang Hao logró cubrir garantía y coste en aquel mismo terreno porque el terreno era lo bastante pequeño. Wu Wenjun recortó una esquina de lo que se podía preguntar en geometría y consiguió pagar la tercera columna. Desde entonces, las máquinas se mueven entre esas tres columnas. Algunas conservan las garantías y van ensanchando poco a poco lo que se puede preguntar. Davis, más tarde, elaboró con Putnam y otros un método para decidir si un conjunto de condiciones lógicas podía satisfacerse simultáneamente; sus descendientes acabarían utilizándose ampliamente para verificar circuitos integrados y programas. Otras dejan muy abierto el campo de las preguntas y vacía la columna de las garantías. Buena parte de lo que después se llamó inteligencia artificial lleva sus cuentas de esa manera.

Nadie ha escrito todavía la página con las tres columnas llenas a la vez. Que la de las preguntas y la de las garantías no pueden llenarse juntas lo dice un teorema.

En este episodio, la guerra dejó un libro a las puertas de la imprenta y cortó el hilo de una vida. El manuscrito acabó recuperándose. De los últimos días de Presburger, en cambio, solo queda un año con un signo de interrogación. En el próximo episodio retrocederemos a 1933, a una universidad.

Los cálculos siguen su curso. Qué cuenta como matemáticas es una cuenta que nunca se ha cerrado.

Fuentes históricas y lecturas complementarias

Las siguientes fuentes corresponden a los detalles históricos y a las diferencias de interpretación del texto. Los registros de archivo y de colecciones, la literatura antigua y las reconstrucciones modernas no constituyen la misma clase de prueba.

• Texto original de Presburger en traducción anotada
• Enciclopedia de Filosofía de Stanford: Tarski
• Informe de Tarski para RAND sobre el procedimiento de decisión
• Wang Hao: artículo original «Hacia unas matemáticas mecanizadas»
• La cota superior de complejidad de Oppen de 1978
• Brown y Davenport sobre la complejidad de la eliminación de cuantificadores
• Prólogo de Wu Wenjun a la colección sobre mecanización de las matemáticas