Gödel y Turing (Parte 1)

(A la parte 2)

“El lógico matemático Kurt Gödel fue uno de los gigantes intelectuales del siglo XX y, en el supuesto de que la especie se conserve, una de las pocas figuras contemporáneas que serán recordadas dentro de 1.000 años. [...] A pesar de que en todas las disciplinas es corriente alentar una cierta miopía profesional, lo cierto es que esta opinión no es fruto de un caso de autocomplacencia por parte de los matemáticos. Simplemente es la verdad.” (John Allen Paulos, 1991).

En el año 1931 Kurt Gödel, por entonces un joven matemático checo casi desconocido (1), publicó un artículo titulado Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados I (2). En él, Gödel presentó dos teoremas que marcaron un antes y un después en la historia de la Lógica Matemática.

Hablando informalmente, el primero de esos teoremas dice que todo sistema axiomático (sujeto a ciertas restricciones formales que, hasta donde se sabe, garantizan la consistencia de la lógica subyacente) que sea suficientemente amplio como para expresar la aritmética elemental contendrá necesariamente proposiciones indecidibles, es decir, afirmaciones con significado que el sistema es incapaz de decidir si son verdaderas o falsas.

El segundo teorema (3) dice esencialmente que un sistema axiomático (sujeto a las mismas restricciones formales antes enunciadas) es incapaz de demostrar su propia consistencia (4).

Mi intención es exponer, en una serie de entradas, un esbozo de demostración de los dos teoremas mencionados. No será la demostración dada por el mismo Gödel en su famoso artículo, sino que estará basada en ideas concebidas posteriormente a la demostración de Gödel.

Para comenzar a comprender estas ideas debemos hablar de otro de los hombres más brillantes del siglo XX: el inglés Alan Mathison Turing, pero eso quedará para la próxima entrada.

Notas:

(1) Gödel había nacido en Brno (hoy República Checa) en 1906, es decir tenía por entonces menos de 25 años de edad.

(2) El artículo original llevaba por título: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, y fue publicado en el Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173 – 198.

(3) Éste segundo teorema iba a ser expuesto en una segunda parte del artículo, pero posteriormente Gödel no consideró necesario publicarla.

(4) Un sistema axiomático es consistente si está libre de contradicciones, es decir, si no hay en él ninguna proposición P tal que tanto P como su negación sean demostrables a partir de los axiomas.

(A la parte 2)