Algunos vínculos entre los teoremas de Gödel y Turing
A
finales del siglo XIX y en la primera mitad del XX, hubo diversos intentos de
formalizar y sistematizar las denominadas ‘ciencias puras’. Con respecto a las
matemáticas, en su obra de 1899, Grundlagen
der Geometrie, David Hilbert (1862-1943) plantea ya algunas de las ideas de lo que, desde entonces, irá
consolidándose como su formalismo o teoría de la demostración. Ciertas
partes ‘esenciales’ de la matemática —geometría, aritmética, topología, etc.—
deben tratarse en un lenguaje formal a partir de unos axiomas ‘ad hoc’ que son los que configuran los objetos
de la teoría y las interrelaciones que coexisten entre ellos. De hecho, los
‘objetos semánticos’ que se amagan detrás de los ‘objetos formales’ carecen de
importancia: “No importa si se trata de puntos, rectas, planos o de mesas,
sillas o jarras de cerveza”. Aparece aquí, agazapada, la distinción entre
‘teoría formal’ y ‘matemática formalizada’.
Este
planteamiento lleva ínsito que el sistema axiomático formal responda a algunas
características importantes, cuales son: la independencia
de los axiomas (que le dan un carácter minimal que, sin ser esencial, es
importante en este contexto por lo que tiene de clarificador), su completitud (los axiomas se eligen de
manera que recojan toda la potencialidad de la ‘matemática’ que se formaliza:
“todo lo que, en dicha matemática es cierto, la axiomática debe permitirnos
demostrarlo”), y su consistencia (la ‘característica esencial’ y que dota de
‘existencia’ a los objetos de la teoría)[1].
En
el texto de lógica
que publicara junto con Wilhelm Ackermann (1896 -1962),
Grundzüge der theoretischen Logik (1928),
se plantea una nueva cuestión que, en cualquier caso, debe ‘cuestionarse’: el
“Entscheidungsproblem” o “problema de la decisión”: ¿Cabe un ‘algoritmo’ que ‘decida’
si una fórmula bien formada del lenguaje formal es un teorema de una teoría
formal concreta?; y, en concreto, “¿el cálculo de predicados de primer orden es
decidible o indecidible?”. Lo plantean, como ya lo hiciera Hilbert en 1900 en
el enunciado del problema 10 o ‘problema diofántico’ en su lección señera del
“Congreso Internacional de Matemáticas de París”, antes de que nadie hubiese
elaborado una definición matemática precisa del concepto de ‘algoritmo’.
En
1930, Kurt Gödel (1906-1978) demostraría la ‘completitud’ del cálculo de
predicados de primer orden: “Todo lo que se puede demostrar es verdadero y todo
lo que es verdadero se puede demostrar”.[2]
Este teorema hace referencia a la ‘lógica’ pero carece de lo que podríamos llamar
‘contenido matemático’. El resultado, análogo en el cálculo de proposiciones,
establecido por Emil Post [1897-1954] en 1921, podía hacer pensar que quizás
aquel cálculo, como lo era éste, sería decidible.
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[3],
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 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:
- El cálculo de predicados de primer orden no es decidible: “ninguna máquina puede decidir si una fórmula es o no un teorema del cálculo de predicados”.
- 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 mM de 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”.[4]
Josep Pla i Carrera es profesor emérito de la Universitat de Barcelona.
Josep Pla acaba de publicar el libro: “El teorema de Gödel, Un análisis de la verdad matemática” dentro de la serie de libros de autor de la Real Sociedad Matemática Española y con edición conjunta entre la RSME y SCIE como actividad del Año Turing / Año de la Informática. El libro se puede encontrar aquí.
El libro está dividido en tres partes. En la primera Josep Pla da una aproximación a la epistemología de la matemática, centrándose en el problema de la verdad en las matemáticas. En la segunda parte, más técnica, aborda la demostración de los teoremas de incompletitud de Gödel. Finalmente, en la tercera parte se analizan algunas consecuencias de los teoremas de Gödel. El libro admite dos lecturas: el lector que busque un texto divulgativo sobre la obra de Gödel verá satisfechas sus expectativas; para el especialista que busque una aproximación rigurosa a los teoremas de Gödel, este texto de Pla es una muy buena opción.
También se destaca que el trabajo sobre computabilidad de Alan Turing se inspiró en el de Kurt Gödel sobre lógica, resultando consecuentemente impregnado de verdad matemática. Así sucede con el conocido problema de la parada para la máquina de Turing cuyo propio enunciado constituye a su vez el paradigma de existencia de funciones no computables.
[1]
El lector interesado puede ampliar esta presentación en Pla i Carrera, J. (2013), capítulo 7, págs.145-161.
[2]
Para
disponer, sin embargo, de la ‘definición’ precisa de ‘verdad’ o ‘validez’
habría que esperar al genial artículo de Alfred Tarski [1902-1983] de 1936.
Véase Pla i Carrera, J. (2013),
págs.185-191.
[3] El lector interesado puede
recurrir al capítulo 11 de Pla i Carrera,
J. (2013).
[4] El
lector interesado puede recurrir a Cutland
[1980], capítulo 8, págs. 143-156.Referencias
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 Funktionenkalkü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.
Hilbert, David (1900). “Mathematische Probleme”, Archiv für Mathematik und Physik, 1, págs. 44-63; 213-237. Traducción castellana de Javier García, en Gray, Jeremy (2000), El reto de Hilbert. Drakontos. Crítica, Madrid: 2003.
Hilbert, David y Ackermann, Wilhelm (1928). Grundzüge der theorestischen Logik. Springer. Berlin. Traducción castellana de Víctor Sánchez de Zavala, Elementos de Lógica Teórica. Editorial Tecnos: Madrid, 1962.
Pla i Carrera, Josep (2013), El Teorema de Gödel. Un análisis de la verdad matemática. Real Sociedad Matemática Española. Madrid: 2012.
Post, Emile (1921). “Introduction to a general theory of elementary propositions”. 43, págs. 163-185.
Tarski, Alfred (1936). “Der Wahrheitsbegriff in den formalisierten Sprachen”. Studia Philosophica, 1, págs 261-405.
Turing, Alan Mathison (1936). “On computable numbers, with an application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society, 42, págs. 230-265.Véase http://www.abelard.org/turpap2/tp2-ie.asp.
Referencia
No hay comentarios:
Publicar un comentario
Se agradece sólo aportes constructivos.
Nota: solo los miembros de este blog pueden publicar comentarios.