Lo imposible

FERNANDO OREJAS

En su famoso artículo de 1936, del que ya se ha hablado en otras entradas de este blog, Turing hacía varias cosas notables. Primero, definía un modelo de máquina (la máquina de Turing) que permitía dar una definición matemática, y  cercana a la intuición, de qué es lo computable. Segundo, demostraba que había una "maquina universal" que podía tomar otras máquinas como datos y comportarse como ellas. Finalmente, demostraba que hay problemas (matématicos) que ninguna máquina podría resolver, que son no computables o indecidibles. Estas aportaciones se consideran muy importantes desde un punto de vista matemático y filosófico. Pero, dejando aparte la relación entre la máquina universal y los computadores actuales, ¿tienen estos resultados algún interés práctico en informática? Si consideramos que, en la última reforma de planes de estudio en Ingeniería Informática, las asignaturas que estudian estas cuestiones han pasado a ser optativas en un buen número de centros españoles, quizá la respuesta sería no. Claro que, si consideramos que estos temas son obligatorios en los estudios de informática de prácticamente todos los centros de prestigio del mundo, tendríamos que dudar de la anterior respuesta y, quizá, preguntarnos por qué algunos de nuestros centros son diferentes.

Informática y creatividad

MACARIO POLO USAOLA

En ocasiones, la investigación y la generación de nuevo conocimiento dan lugar al nacimiento de nuevas disciplinas cuyos primeros expertos son, precisamente, aquellos que hicieron evolucionar lo viejo para dar lugar a lo nuevo: el matemático Pitágoras procedía de la Filosofía; Platón, además de filósofo, escribió sobre Política, Ética y Moral; Aristóteles, discípulo de Platón, escribió cerca de doscientas obras sobre temas tan variados como la Lógica, la Estética, la Ética o la Retórica; el médico Paracelso, que buscó en el siglo XVI el elixir de la vida eterna, se dedicó también a la Astrología; Pascal, uno de los físicos más relevantes del siglo XVII, fue también matemático y teólogo, además de filósofo; Newton, aparte de físico, fue teólogo y alquimista y buscó la Piedra Filosofal.

A propósito de Turing: Ciencia básica frente a ciencia aplicada

HECTOR GEFFNER

Pocos problemas tienen un carácter más teórico que determinar si hay más conjuntos de números naturales que números naturales, si una axiomatización de la lógica de predicados captura todas inferencias que son deductivamente válidas, o  si puede existir un procedimiento que demuestre que una inferencia es válida o no. Estos problemas no parecen tener mucho que ver con temas más profanos como envíar mensajes de texto, comprar entradas para un concierto por internet, o jugar al World of Warcraft (WoW). Sin embargo, estos y otros desarrollos prácticos que influyen de foma profunda en nuestra vida cotidiana están íntimamente vinculados a esos problemas teóricos mencionados inicialmente.

El vínculo se encuentra en los computadores desarrollados a partir de la década de los años 40, siguiendo un diseño que –en sus líneas fundamentales– había sido esbozado años atrás por el lógico matemático Alan Turing. Se trata de la famosa "máquina de Turing", que no fue diseñada para hacer nada práctico, aunque posteriormente Turing viera las posibilidades que tal "máquina" abría para el estudio del comportamiento inteligente. La "máquina de Turing", en papel, fue desarrollada para resolver un problema eminentemente teórico: el problema de encontrar un procedimiento para determinar la validez de una inferencia en lógica de predicados.  El problema había sido planteado por un famoso matemático, David Hilbert, en 1928. Tanto la formulación del problema por Hilbert, como su resolución por Turing, se apoyan en ideas desarrolladas por Hilbert y otros lógicos y matemáticos, entre los que cabe destacar a Boole, Cantor, Frege, Russell, y Godel; el "dream team" de la lógica moderna. La historia de este desarrollo está magníficamente contada en el libro "The Universal Computer: The Road from Leibniz to Turing", Martin Davis [1].

Turing demuestra rigurosamente que el procedimiento buscado por Hilbert no existe. Turing inventa "su" máquina como formalización de lo que es un procedimiento (un método de cómputo), y demuestra entonces que no puede haber tal máquina para el problema de Hilbert (el llamado "Entscheidungsproblem"[2], para diferenciarlo de otros problemas fundamentales también formulados por Hilbert). Para la prueba utiliza la idea de codificar máquinas con números, siguiendo el ejemplo de Godel quien introduce una idea similar para demostrar la incompletitud de la aritmética formal (otro problema planteado por Hilbert), y la  técnica de diagonalización, introducida antes por Cantor para demostrar que hay más conjuntos de naturales que números naturales, usada tambien por Godel en su prueba.

Turing no se queda en ese resultado sin embargo y construye una "máquina de Turing" (todavía en papel) que es "universal" en el sentido que este "hardware" particular puede ejecutar cualquier procedimiento. Más precisamente, esta máquina universal de Turing es programable: acepta la descripción de una máquina particular que resuelve un problema dado sobre una entrada, y emula el comportamiento de esa máquina sobre esa entrada.  La máquina universal de Turing es la madre del computador programable moderno. Que algo así era incluso posible no era obvio en los años 40 cuando los "computadores" se desarrollaban para resolver un conjunto específico de cáculos. El límite de la  máquina universal de Turing, por otro lado, es el límite de ordenadores actuales, el límite de lo computable.

Sorprende ver como un desarrollo que no estuvo motivado en modo alguno por aplicaciones "prácticas", ha tenido un impacto que quizás algun día se compare al desarrollo de la agricultura. La historia, sin embargo, no es inusual en el desarrollo de la ciencia, donde uno sabe donde empieza pero no donde termina. Esa es la promesa de la ciencia desde el punto de vista social, y la aventura del  científico desde el punto de vista personal.

Hector Geffner es investigador senior ICREA y profesor de la Universitat Pompeu Fabra.

---

[1] Martin Davis es un matemático estadounidense, bien conocido por el algoritmo de Davis-Putnam para resolver el problema de satisfactibilidad booleana. Su libro “The Universal Computer” fue editado por Norton el el año 2000, y ha sido reeditado por Taylor & Francis en 2011.

Una excelente conferencia de Martin Davis sobre la naturaleza de la computación y los trabajos de Church y Turing se puede ver aquí. .

[2]  El "Entscheidungsproblem" fue resuelto de forma independiente por Alonzo Church y Alan Turing, en sendos artículos publicados en 1936 con pocos meses de diferencia. El artículo de Turing contenía la descripción de su “máquina”, lo que tuvo una inmensa repercusión posterior. Como curiosidad, cuando Turing escribió su artículo había terminado sus estudios de matemáticas en Cambridge (Reino Unido) pero no había comenzado sus estudios de doctorado. Alonzo Church fue el director de su tesis doctoral en Princeton (Estados Unidos).

Algunos vínculos entre los teoremas de Gödel y Turing

JOSEP PLA I CARRERA

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(v₁) es una fórmula con la única variable llibre v₁”, “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(m_M, n₁,...,n_k):=M(n₁,...,n_k),

 en donde m_M 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 m_M.

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 decidible: “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 m_M de una máquina M y unos ciertos datos numéricos n₁,...,n_k, nos diga si M(n₁,...,n_k) 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.

---