Los Teoremas de Göedel y de Türing

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

Por: Año Turing | 07 de febrero de 2013

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.


Referencia

Michel Foucault: Arqueología del saber

Marina. Acuarela personal

Georges Charbonnier recibe a Michel Foucault en la  micro Matinee Cultural de Francia, en presencia de Jean Duvignaud - Profesor del Collège de France y Jean Claude Pecker - Director del Observatorio de Niza, para discutir el significado dado por el autor de Arqueología del saber. Habla de epistemología, de las normas de producción y de la formación del discurso y de la práctica del discurso con, por ejemplo, el caso de la locura y la medicina. Foucault también habla, entre otras cosas, de su "positivismo" y de sus vínculos con el movimiento estructuralista.

Conferencia del 2 de mayo de 1969   


Posteo también un escrito que analiza el texto de Foucault.

LA ARQUEOLOGÍA DEL SABER
MICHEL FOUCAULT
México: Siglo Veintiuno, 1970. (Paris: Gallimard, 1969)
 Resumen y notas: Juan Magariños de Morentin

[JMdeM-1] La lectura y la comprensión de las propuestas foucaultianas son fundamentales para comprender los objetivos y las operaciones coherentes con tales objetivos, cuando se enfoca la realización de un estudio o investigación en el ámbito de la SEMIÓTICA SIMBÓLICA.

Recuérdese que entendemos por SEMIÓTICA SIMBÓLICA aquella metodología de investigación destinada a explicar el significado de determinados fenómenos sociales, CUANDO SU REPRESENTACIÓN/INTERPRETACIÓN HA SIDO SOCIALMENTE PRODUCIDA POR TEXTOS SIMBÓLICOS. En el sentido peirceano, "textos simbólicos" designa predominantemente al HABLA, pero también a cualquiera otra semiosis cuyos signos son convencionales (o sea su interpretación requiere del conocimiento de la convención social que les da vigencia) y, en consecuencia, constituyen un sistema virtual de fuerte o, al menos, relativa formalización (o sea, los signos se relacionan según reglas estables e identificables).

Por esto, el aporte de Foucault ha sido decisivo para la organización de los criterios y operaciones que constituyen el ANÁLISIS DE DISCURSO. Su aplicación a otras semiosis como la icónica y la indicial requiere transformaciones y ajustes para no desvirtuar la eficacia específica, y las reglas de producción de tal eficacia, correspondiente a esas otras semiosis.

A lo que apunta Foucault es a mostrar cuáles son las características de esa entidad a la que designa como "enunciado" (apartándose de su significado más difundido y redefiniéndolo a lo largo de toda esta obra) y que, de manera muy peculiar, construye el significado de aquello a lo que se refiere.

La arqueología del saber es un texto de reflexión epistemológica, en el que Foucault formula un PROGRAMA DE INVESTIGACIÓN, sin concretar específicas operaciones metodológicas, pero fijando las características y condiciones a las que tales operaciones deberán ajustarse. Es un documento crítico respecto de ciertas prácticas habituales en las tareas académicas de investigación de textos, en las que Foucault va señalando trampas cognitivas, ineficacia explicativa, desvíos implícitos, que dificultan o incluso impiden alcanzar la explicación del proceso de producción del significado, tal como se pretende que quede evidenciado mediante el análisis de los textos en estudio.

Ésta es, al menos, una de las lecturas posibles de esta obra; lo que digo con plena conciencia de no agotar su riqueza conceptual; y también con la plena conciencia de haber tomado cierta independencia que, en ocasiones, LLEGA A LA HETERODOXIA, siempre con el objetivo de recuperar la potencia metodológica de sus sugerencias. Es, por tanto, la lectura que propongo para fundamentar LAS CARACTERÍSTICAS DEL RIGOR METODOLÓGICO CON EL QUE CONSIDERO NECESARIO QUE TRABAJE LA SEMIÓTICA para responder a sus posibilidades analíticas y no caer en la fácil banalización que tanto la ha perjudicado.

Texto posteado   

Ver información sobre La Parresía  
 Texto de Foucault

Texto de Foucault en Berkley

Sobre la Parresía
De manera más precisa, la parresia es una actividad verbal en la cual un hablante expresa su relación personal a la verdad, y corre peligro porque reconoce que decir la verdad es un deber para mejorar o ayudar a otras personas (tanto como a sí mismo). En parresia, el hablante usa su libertad y elige la franqueza en vez de la persuasión, la verdad en vez de la falsedad o el silencio, el riesgo de muerte en vez de la vida y la seguridad, la crítica en vez de la adulación y el deber moral en vez del auto-interés y la apatía moral.

Clase de Foucault sobre la Parresía

La ingratitud: Alain Finkielkraut

Alain Finkielkraut: La Ingratitud

La ingratitud: Alain Finkielkraut

Traducción de Francisco Díez del Corral. Anagrama. Barcelona, 2001. 197 páginas.

Principio del formulario

Final del formulario

Bernabé SARABIA | Publicado el 09/05/2001 | Referencia El cultural.es

En la reivindicación que Alain Finkielkraut hace de la gratitud late la queja contra una modernidad que permite demasiadas libertades y que olvida con demasiada facilidad. Dicha postura ha dado pie a que el autor fuera acusado, en Francia, de conservadurismo

Este volumen deviene de la transcripción de una serie de entrevistas mantenidas entre Alain Finkielkraut y su amigo Antoine Robitaille, periodista en Quebec y miembro activo del grupo de presión francófono. Al tratarse de una conversación transformada en escritura nos encontramos con el inconveniente, habitual en estos casos, de cierto desorden textual en forma de repeticiones o de pérdida del orden lógico. Sin embargo, ésto queda compensado, en primer lugar, por la riqueza y variedad de las referencias, algo habitual en dos personas cultas que dialogan y, en segundo lugar, por los puntos de deriva, es decir, por las piezas de información que al hablar se escapan, en cierto modo, al férreo control que sobre lo que se manifiesta supone la escritura.

            De este modo La ingratitud, subtitulada de modo muy expresivo Conversaciones sobre nuestro tiempo, constituye una aguda reflexión en torno a los intereses de Robitaille que, al menos en la presente obra, giran en torno a la soberanía de Quebec respecto del Estado federal canadiense. Las preocupaciones de Finkielkraut son de un orden más complejo, en ocasiones opuesto, a las de Robitaille.

            Nacido en 1949 en el seno de una familia judía, Finkielkraut estudió filosofía en la Escuela Normal Superior de Saint-Cloud. Profesor en la Escuela Politécnica, dirige y coordina un programa de radio, "Repliques", los sábados por la mañana en la emisora France Culture, dedicado a discutir y comentar los acontecimientos de la vida cultural de actualidad en Francia. Desde 1985 publica una revista titulada Le Messager européen. Finkielkraut salta a la fama cuando en 1977, en colaboración con Pascal Bruckner, publica en la prestigiosa editorial Seuil Le nouveau désord amoreux (El nuevo desorden amoroso). Lo que llamó la atención de dicho libro no fue que bajo la influencia de Fourier los autores reclamasen la multiplicidad del mundo pasional, sino más bien la crítica a los postulados de la revolución sexual de la época efectuada desde la vivencia de la sexualidad que tienen el hombre y la mujer de la calle.

            Una vez que se abre para su lectura La ingratitud comienzan a verse las obsesiones de Finkielkraut. En el primer capítulo emerge la cuestión judía. No podía ser de otro modo en un discípulo de Emmanuel Levinas (1905-1995), autor de Le Juif imaginaire (El judío imaginario). Finkielkraut vuelve a preocupaciones vinculadas a la memoria de la Shoah y a referirse a obras de Primo Levi, Levinas o Jankélevitch. Emerge también el análisis del problemático, en tantos sentidos, Estado de Israel.

            Más adelante Finkielkraut entra en lo que él considera como la disposición afectiva que caracteriza nuestro tiempo: la ingratitud. La contempla en la falta de respeto a la pluralidad humana, en el desprecio a la lengua, en la reducción del papel del Estado a la de mero vehículo de intereses particulares y en el olvido de las obras trascendentes.
            En la reivindicación que Finkielkraut hace de la gratitud late la queja contra una modernidad que permite demasiadas libertades y que olvida con demasiada facilidad. Dicha postura ha dado pie a que fuera acusado, en Francia, de conservadurismo. En cierto modo el propio Finkielkraut ha dado pie a lo que hoy no se le permite a ningún intelectual -ser conservador- con su rechazo de las nuevas tecnologías o, mejor aún, de las biotecnologías, como por ejemplo su prédica en contra del uso del ordenador en clase cuando recoge la opinión, entre otras, de Allan Key. Dicho ingeniero de Apple ha señalado en distintas ocasiones que la escuela no podrá resolver por medio de los ordenadores ninguno de los problemas que ha sido incapaz de solucionar sin ellos.

            En cierto modo lo que trata de advertir Finkielkraut en La ingratitud es que el progreso no debe convertirse en algo que vaya más allá de una perspectiva de futuro, transformándose en una tradición que sobre impuesta a la cultura acabe por desplazar y arruinar la memoria histórica. Las páginas de este volumen tratan de prevenir al lector de los peligros que encierra la postmodernidad en tanto en cuanto borrachera de la metamorfosis permanente. A modo de resumen puede afirmarse que este libro constituye una excelente introducción a un autor cuyas obras son de una arquitectura compleja. Sus referencias temáticas, tanto si se refieren a la Europa danubiana como a la cuestión judía o el problema de los Balcanes, están llenas de un conocimiento y de una reflexión poco habitual en la cultura española.

La Ingatitud: Comentario

• Finkielkraut, Alain (2007). Nosotros, los modernos. Encuentro.
• __ (2005). En el nombre del otro: reflexiones sobre el antisemitismo que viene. Seix Barral.
• __ (2004). La derrota del pensamiento. Editorial Anagrama. Bruckner, Pascal; __(2001). El nuevo desorden amoroso. Editorial Anagrama.
•  __(2001). La ingratitud: conversaciones sobre nuestro tiempo. Editorial Anagrama.
•  __(1998). La humanidad perdida: ensayo sobre el siglo XX. Editorial Anagrama.
•  __(1990). La memoria vana: del crimen contra la humanidad. Editorial Anagrama.
•  __(1986). La sabiduría del amor. Editorial Gedisa.
•  __(1982). La nueva derecha norteamericana. Editorial Anagrama.
•  __ (1981). El judío imaginario. Editorial Anagrama. Bruckner, Pascal;
•  __(1980). La aventura a la vuelta de la esquina. Editorial Anagrama.
• __ (2008). Los latidos del mundo. Editorial Amorrortu.

·   L'imparfait du présent, 2002).

·  Reflexiones sobre el antisemitismo que viene, Seix Barral, Barcelona, 2005).

·  Nous autres modernes, 2005. (Nosotros, los modernos, Encuentro, Madrid, 2006)

·  Entretiens sur la laïcité. Avec Benny Lévy, 2006

Peter Sloterdijk:  Has de cambiar tu vida (Pre-Textos).

Tony Judt:  Pensar el siglo XX (Taurus).

Ética de urgencia: Fernando Savater

Ética Radical: Carlos Paris: Etica_radical_Los_abismos_de_la_actual_civilizacion