El teorema de Gödel, una aproximación a la verdad matemática (II)

Algunos vínculos

entre el teorema de Gödel de 1931

y el resultado de Turing de 1936 [II]

 

En 1931, el eminente matemático y lógico alemán cerraría —de una forma inesperada para Hilbert— las cuestiones de la completitud y de la consistencia de ciertas teorías matemáticas. En definitiva —y de forma breve— [primer teorema de incompletitud de Gödel] “cualquier teoría que contenga la aritmética de Peano convenientemente axiomatizada, y sea consistente, es incompleta”. Además [segundo teorema de incompletitud de Gödel] “es imposible dar una demostración de la consistencia de la teoría ‘dentro’ de la teoría”.

Para lograr establecer estos resultados —en particular, el primero—, Gödel recurre a una especie de “piedra de Rosetta”. Es decir, recurre a tres lenguajes distintos —el lenguaje ordinario, el lenguaje formal y el lenguaje matemático de la aritmética— para los que establece como se traduce de uno a otro[1], uno de los cuales es el lenguaje de la aritmética de los números naturales entendidos como objetos matemáticos y no como objetos formales.

Precisa cuales son los ‘diccionarios’. Los conjuntos, relaciones y funciones aritméticas ‘traducibles’ al lenguaje formal son los ‘primitivos recursivos’, un concepto que en ulteriores trabajos el propio Gödel ampliará ‘recursivo’. Resulta que las expresiones ‘metamatemáticas’ relativas al lenguaje formal por ejemplo,j(v1) es una fórmula con la única variable llibre v1”, “la sentencia s admite una demostración en la teoría formal”, etc.— se pueden transformar en conjuntos o relaciones primitivos recursivos por medio de la gödelización.

Sin embargo, quedaba todavía en el tintero la cuestión de la decidibilidad de la teoría, la cual como ya hemos indicado depende de disponer de un concepto “fino” de algoritmo. Este problema sería resuelto en 1936, simultáneamente, por Alonzo Church [1903-1995], y Alan M. Turing [1912-1954].

La presentación de Turing es por su simplicidad y naturalidad la más comprensible y la que más proyección ha tenido en la teoría de la computación, y más si cabe porque, en el trabajo de 1936, establece la “existencia de la máquina universal”; esto es, una máquina U que, frente a unos datos, se puede comportar como cualquiera de las máquinas de computación M: puede sumarlos, multiplicarlos, etc. Basta con que indiquemos cómo queremos que se comporte en cada caso. Formalmente,

U(mM, n1,…,nk):=M(n1,…,nk),

en donde mM dice a la máquina U que debe actuar como la máquina M; de hecho, cada máquina M admite un código numérico mM.

Además, Turing, en general, usa el mismo lenguaje para dar la “máquina” —el programa computacional— como para realizar la computación, un avance realmente notable con respecto de quienes, antes que él, habían intentado ofrecer máquinas de cálculo. La suya, claro está, es una máquina teórica o formal antes que una máquina mecánica.

Con este concepto de ‘computabilidad’ Turing puede establecer dos resultados importantes:

(1) El cálculo de predicados de primer orden no es deicible: “ninguna     máquina puede decidir si una fórmula es o no un teorema del      cálculo de predicados.

(2) Hay problemas que ‘no’ son computables: así aparece el “problema de la parada”: ‘no’ es posible construir una máquina que, si le damos como entrada, el código mde una máquina M y unos ciertos       datos numéricos n1,…,nk, nos diga si M(n1,…,nk) se parará o continuará procesando indefindamente.

Hemos relacionado, pues, Turing con Hilbert.

Pero, ¿qué lo vincula con Gödel? La respuesta nos las dan las ‘funciones recursivas [parciales]’. Una máquina de Turing calcula las funciones recursivas y sólo éstas. Este es un vínculo muy estrecho entre algunos de los conceptos introducidos por Gödel y algunos de los conceptos introducidos por Turing que justifican, creo, que en 1963 Gödel añadiera un apéndice al artículo de su teorema de 1931 afirmando que las aportaciones de Turing permitían “una definición precisa e indudablemente adecuada de la noción general de sistema formal de los teoremas vi y xi”.[2]

 

Josep Pla i Carrera

profesor emérito de la ub

jpla@ub.edu

Referencias biblográficas

Church, Alonzo (1936). “A note on the Entscheidungsproblem”. Journal of    Symbolic Logic, pàgs. 40–41.

Cutland, Nigel (1980). Computability. An introduction to recursive function theory. Cambridge University Press. Cambridge.

Gödel, Kurt (1930).“Die Vollständigkeit der Axiome des logischen Funktio- nenkalküls”. Monatshefte für Mathematik und Physik, 37, págs. 349-360. Traducción castellana en Gödel, K. (1981), págs. 20-    34.

Gödel, Kurt (1931).“Ûber formal unentscheidbare Sâtze der Principia      Mathematica und verwandter System”. Monatshefte für Mathematik und Physik, 38, págs. 173-198. Traducción castellana en        Gödel, K. (1981), págs. 45-89.

Hilbert, David (1899). Grundlagen der Geometrie. Teubner: Sttugart.


[1] El lector interesado puede recurrir al capítulo 11 de Pla i Carrera, J. (2013).

[2] El lector interesado puede recurrir a Cutland [1980], capítulo 8, págs. 143-156.

Did you like this? Share it:
This entry was posted in Actualidad, Libros, Personajes and tagged , , . Bookmark the permalink.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *