Una pregunta sobre la verdad

Bien las matemáticas son demasiado grandes para el cerebro humano, o bien la mente del hombre es algo más que una simple máquina.

La historia de este trabajo mezcla dos campos de la filosofía y las matemáticas: la lógica y las ciencias de la computación.

La lógica es una de las ramas más antiguas de la filosofía, desarrollada en China, India, Grecia y en el mundo islámico. Las teorías de Aristóteles fueron influyentes durante milenios, mientras que estoicos como Crisipo de Solos comenzaron el desarrollo de la lógica proposicional. En la Europa de los siglos XVII y XVIII, Leibniz y Lambert intentaron formalizar las operaciones de la lógica, aunque sus trabajos permanecieron aislados y poco conocidos².

Las ciencias de la computación no surgirán hasta más tarde. Aunque una aproximación a la noción de algoritmo ya había sido estudiada durante milenios, no fue hasta mediados del siglo XIX cuando se diseñaron las primeras formas de dispositivos de computación, con los trabajos de Charles Babbage y Ada Lovelace³.

Paralelamente, George Boole y Augustus De Morgan presentan tratados sistemáticos de lógica, extendiendo la doctrina lógica aristotélica para formar un nuevo campo de estudio de las matemáticas.

Poco más tarde, se descubren fallos en los axiomas de la geometría euclidiana. Además de la independencia del postulado de las paralelas, establecido por Nikolai Lobachevsky en 1826⁴, se descubre que algunos de los teoremas considerados demostrados por Euclides no eran, de hecho, demostrables a partir de los axiomas. Entre estos teoremas encontramos resultados como que una línea contiene al menos dos puntos, o que dos círculos del mismo radio cuyos centros están a esa distancia deben intersecarse. A finales de siglo, Hilbert² publica Grundlagen der Geometrie («Los fundamentos de la geometría»), un conjunto de axiomas completos para la geometría, basados en el trabajo previo de Moritz Pasch.

Es en estos momentos cuando Giuseppe Peano publica un conjunto de axiomas para la aritmética (que veremos en el Capítulo 4).

El éxito de Hilbert le motiva a buscar axiomatizaciones completas de otras áreas de las matemáticas, como la teoría de números. Este será el germen de una de las áreas de investigación más populares a principios del siglo XX.

En 1900, este mismo matemático publica su famosa lista de 23 problemas para el nuevo siglo (conocidos en la actualidad como los problemas de Hilbert) en el II Congreso Internacional de Matemáticas de París. El segundo de éstos se pregunta sobre la consistencia de los axiomas de la aritmética⁵.

En 1910, Bertrand Russell y Alfred Whitehead publican el primer volumen de Principia Mathematica⁶, considerado uno de los trabajos más influyentes del siglo XX.

En 1928, Hilbert reformula su segundo problema en el Congreso Internacional de Bolonia, planteando tres preguntas:

1. ¿Son completas las matemáticas? Esto es, ¿puede demostrarse cada sentencia matemática o su negación?
2. ¿Son consistentes las matemáticas? Esto es, ¿no es posible probar simultáneamente una afirmación y su negación?
3. ¿Son decidibles las matemáticas? Esto es, ¿existe un método automático que pueda aplicarse a cualquier afirmación matemática y determine si es cierta? Este problema se conoce como el Entscheidungsproblem.

Exploramos los conceptos de completitud, consistencia y decidibilidad en el Capítulo 4. El objetivo de Hilbert era encontrar un sistema matemático completo y consistente en el que las afirmaciones puedan plantearse con precisión y puedan ser demostradas de forma automática.

En 1931, Kurt Gödel destruye los sueños de Hilbert publicando Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I («Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados»)⁷. En este artículo, Gödel prueba la incompletitud de unos ciertos sistemas. Este resultado establece severas limitaciones en los fundamentos axiomáticos de las matemáticas. Hilbert, sin embargo, no reconoce la importancia de este resultado hasta pasado un tiempo. Poco más tarde, Gödel introduce una de las primeras nociones de definiciones recursivas (las hoy llamadas funciones $\mu$-recursivas).

La primera prueba de la no decidibilidad del Entscheidungsproblem la da Alonzo Church en 1936⁸, usando la noción de funciones $\lambda$-calculables. En él, Church demuestra la equivalencia con las funciones $\mu$-recursivas de Gödel, y aventura que estas funciones serán las únicas calculables mediante un algoritmo, una tesis que lleva su nombre: la tesis de Church.

Un año más tarde, Alan Turing aborda la misma cuestión desde un ángulo distinto. En On Computable Numbers, with an Application to the Entscheidungsproblem⁹ define una máquina de Turing: un dispositivo ideal con un número finito de estados internos, una cinta unidimensional y un cabezal que lee y escribe un símbolo cada vez. Un cálculo no es más que seguir una tabla finita de instrucciones —exactamente el tipo de «método automático» que la tercera pregunta de Hilbert pedía, hecho preciso.

Turing usó este modelo para mostrar que varios problemas no pueden ser decididos por ninguna máquina de este tipo. Su argumento es constructivo: una vez que el cálculo se identifica con ejecuciones de máquinas, se puede probar que ninguna máquina puede resolver ciertas preguntas sobre otras máquinas —entre ellas, el Entscheidungsproblem. También propuso lo que hoy se llama la tesis de Turing: que toda función calculable «a mano», o mediante un algoritmo en el sentido intuitivo, es calculable por una máquina de Turing. Aunque la tesis no puede demostrarse, Turing dio en el mismo artículo numerosos argumentos independientes a su favor.

La definición abstracta resulta mucho más fácil de asimilar cuando se puede ver una máquina en funcionamiento. El simulador siguiente no está tomado del artículo de Turing —es una codificación moderna de una máquina que analizamos en el Capítulo 2—, pero muestra los mismos ingredientes que él tenía en mente: un grafo finito de estados y transiciones, y una cinta cuyo contenido cambia paso a paso. Ejecútalo con abbaa para seguir un cálculo aceptante, o prueba otra palabra sobre {a,b} para ver cómo un único programa fijo acepta algunas entradas y rechaza otras. Esa interacción entre un programa finito y una entrada ilimitada es el corazón del modelo de Turing.

Más adelante, Church, Turing y Stephen Kleene¹⁰ prueban que los tres modelos de computación introducidos (funciones $\mu$-recursivas, funciones $\lambda$-calculables y máquinas de Turing) son equivalentes, reforzando las tesis ya mencionadas e introduciendo la tesis de Church-Turing.

El siglo XX vio un desarrollo excepcional de las ciencias de la computación y el nacimiento de la informática, llegando a la revolución de los ordenadores personales y de los dispositivos móviles actuales. Todo esto fue posible gracias al trabajo de, entre otros, los matemáticos que mencionamos en esta breve reseña.