Las paradojas de la razón autorreferente (2/2): Gödel, Turing, Wittgenstein.

¿Es la aritmética consistente y completa?

En la primera parte de esta entrada vimos que el eminente matemático David Hilbert plantea a principios del siglo XX dos cuestiones fundamentales cuya respuesta era necesaria para cumplir su programa de fundamentar las matemáticas sobre una segura base formal.

El objetivo de la comunidad matemática era (y aún lo es) crear sistemas axiomático-deductivos con los que pudieran demostrarse en forma de teoremas todas las fórmulas o enunciados verdaderos expresables en el sistema (completitud) y además no pudieran generarse falsedades (consistencia). También, idealmente, debería haber un método mecánico o determinista para decidir si cualquier fórmula es verdadera o no (decibilidad).

• Hilbert plantea en 1900 que es necesario probar la consistencia de los axiomas de la Aritmética, es decir, que no se pueda deducir mediante reglas lógicas ninguna contradicción a partir de los axiomas referidos a los números naturales y las operaciones de suma y multiplicación.

• Posteriormente, en 1928, Hilbert y Wilhelm Ackermann añaden el llamado problema de la decisión: encontrar un proceso formal (un algoritmo) que de forma mecánica pueda decidir si una fórmula o enunciado es verdadero (demostrable) o no lo es. En realidad este problema tiene a su vez dos partes:
• Primero, habría que probar que el sistema axiomático es completo (que permite decidir si cualquier fórmula o enunciado con sentido es verdadero o falso)
• Segundo, habría que encontrar el algoritmo o proceso mecánico para tomar esta decisión. Como pasos hacia este objetivo, en 1936 Alonzo Church formalizó el concepto de algoritmo en forma funcional con su cálculo lambda y Alan Turing en forma computacional con la máquina de Turing.

Veremos que debido precisamente a la autorreferencia de los sistemas de razonamiento formal que vimos en la entrada anterior, la respuesta a estos problemas es negativa. La aritmética y todos los sistemas formales y computacionales que incluyen a la aritmética no son completos ni decidibles, y tampoco se puede probar que sean consistentes.

Gödel demuestra la incompletitud de la Aritmética y la indemostrabilidad de su consistencia

El primer paso para mostrar las limitaciones de la formalización de la matemática (y los programas de fundamentación lógica de Rusell y los positivistas lógicos) fueron los llamados Teoremas de Incompletitud que el joven matemático Kurt Gödel publicó en 1931 con el título "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados".

El primer teorema afirma que:

Cualquier teoría aritmética recursiva que sea consistente es incompleta

Es decir, una teoría que incluya a la aritmética, no puede ser a la vez consistente y completa.

La elegancia en la demostración de Gödel y su impacto rompiendo la estructura monolítica de la lógica clásica se ha comparado muchas veces a la de la Teoría de la Relatividad de Einstein. Por cierto que Einstein y Gödel se hicieron muy amigos cuando ambos se encontraron trabajando en la universidad de Princeton tras huir de una Europa amenazada por la Alemania nazi.

Vayamos a la maravillosa demostración de Gödel, que es en realidad sencilla de comprender a partir de la paradoja del mentiroso que vimos en la entrada anterior. La idea es sencilla de entender, pero los detalles requieren un poco de atención  :-)  Si os perdéis, al menos podéis ver este interesante vídeo:

Primero, Gödel muestra cómo las teorías formales de la aritmética son recursivas, es decir, autorreferentes. Veámoslo:

• Las variables utilizadas en las fórmulas o enunciados de la aritmética se refieren a números naturales (0, 1, 2...), por ejemplo, a, b y c representan números cualquiera en esta fórmula:

• Los símbolos que aparecen en las fórmulas, incluyendo las variables, operadores matemáticos (suma, multiplicación) y los símbolo lógicos (igualdad, implicaciones, cuantificadores), se pueden también representar como números, llamados códigos o números Gödel, y todos los códigos que aparecen en una fórmula se pueden combinar para representarla como un único número, utilizándolos como exponentes de los sucesivos números primos y luego multiplicándolos. Este proceso se llama numeración de Gödel o godelización y podéis comprobarlo en esta aplicación.

Lo importante es que a cada posible fórmula de la aritmética le corresponde un número único que representa unívocamente esa fórmula.

• Como conclusión de los anteriores puntos, los números referidos por las variables que aparecen en una fórmula (a,b, x, y...) pueden ser los códigos de otras fórmulas, y por tanto, las fórmulas de la aritmética pueden expresar enunciados sobre sí mismas: tienen la capacidad de ser autorreferentes.

En el segundo paso, Gödel construye un enunciado que representa el hecho de que una fórmula x es derivable (demostrable) en el sistema axiomático. Es posible construir este enunciado porque cada operación de derivación en el sistema formal de la aritmética se puede ver como una combinación de operaciones aritméticas sobre los códigos Gödel de las fórmulas.

D(x)   :   la fórmula x es demostrable

Por otra parte, supongamos que una fórmula f usa una variable y, e imaginemos el proceso de sustituir y en la fórmula f por el número Gödel de f. Podemos definir una fórmula o función que representa esta operación, que llamaremos AutoGodelización:

x = AutoGodel(f)  :  x es la fórmula que resulta al sustituir en la fórmula f la variable y por el propio código de f

En el último paso, utilizaremos estos enunciados aritméticos para construir una fórmula que afirma de sí misma que no es demostrable (fórmula G). Es un claro paralelismo con la paradoja del mentiroso, pues G utiliza una combinación de autorreferencia y negación. Vemos cómo se hace. Primero construimos esta fórmula:

Fórmula g   :   no es cierto que (D(x) y además x = AutoGodel(y))
(no es cierto que x sea demostrable y al mismo tiempo sea la AutoGodelizacion de y)

Ahora creamos la AutoGodelización de la fórmula g, sustituyendo y por el código numérico que corresponde a la fórmula (llamamos g a este número, para abreviar) y llamaremos G a la fórmula resultante de la sustitución:  G = AutoGodel(g). Por tanto, al cambiar y por g resulta:

Fórmula G = AutoGodel(g)  ==>   no es cierto que (D(x) y además x = AutoGodel(g))

Como hemos definido G = AutoGodel(g), es obvio que x es igual a G en la parte derecha de la fórmula, y es por esta razón por la cual la fórmula G habla de sí misma:

Fórmula G   :   no es cierto que (D(G) y además G = AutoGodel(g))

Como la segunda parte es obviamente cierta por la definición de G, lo que la fórmula G dice en realidad es:

Fórmula G    :    no es cierto que D(G)

Dicho de otra manera:

Fórmula G:  "La fórmula G no es demostrable"

Ahora pensemos, ¿es la fórmula G verdadera o falsa?

• Si la suponemos verdadera entonces, según ella afirma, no es demostrable. Como consecuencia, el sistema de la aritmética sería incompleto, incapaz de demostrar una fórmula que es verdadera.
• Si la suponemos falsa entonces lo contrario sería cierto: la formula G sería demostrable. Pero esto implicaría que el sistema de la aritmética es inconsistente, pues permite demostrar una fórmula falsa.

De donde se sigue que o bien el sistema de la aritmética es incompleto (si G se considera verdadera) o bien inconsistente (si G se considera falsa). 

Lo cierto es que Gödel consigue demostrar que G es verdadera. Por la forma en que se ha construido como negación de todas las posibles derivaciones, Gödel y cualquier humano que siga la demostración sabe que G no se deriva de los axiomas de la aritmética, pero ella misma afirma que no es demostrable dentro del sistema. Esto tiene la profunda implicación de que existen verdades expresables en las teorías que incluyen a la aritmética (enunciados que podemos ver que son verdaderos) que las mismas teorías no pueden demostrar.

En su segundo teorema, Gödel demuestra que la fórmula G es verdadera si y solo si la fórmula A: "El sistema de la aritmética es consistente" es verdadera. Como consecuencia, tampoco esta fórmula A es demostrable, y por tanto la consistencia de la aritmética no es demostrable, aunque sea verdadera.

La conclusión es que desde dentro de un sistema de razonamiento formal podemos hacer muchas cosas, pero no podemos ni demostrar todas las verdades posibles (aunque sean expresables en nuestro sistema), ni tampoco demostrar que nuestro sistema no va a generar falsedades, aunque es posible que desde fuera del sistema podamos demostrarlo.

Esta conclusión ha sido utilizada por Roger Penrose y otros autores para argumentar que la mente humana es superior a cualquier ordenador o sistema computacional que pudiera construirse. Sin embargo, otros autores como Douglas Hofstadter han mostrado la falacia de esta interpretación (ver el libro "Gödel, Escher, Bach" más abajo): tanto la mente humana como los 'sistemas algorítmicos' pueden razonar sin estar limitados a trabajar dentro de un sistema formal.

El problema de la decisión: Church y Turing

Tras los teoremas de Gödel en 1931, el mundo de la lógica y la matemática se quedaron en choque. Los objetivos de Hilbert de demostrar la consistencia y la completitud de la aritmética (la más simple de las teorías matemáticas) se revelaron imposibles y se puso en cuestión la firmeza de los sistemas formales como sustento del conocimiento, un factor decisivo en el abandono del programa del positivismo lógico, y el impulso para que nacieran otras concepciones del lenguaje y la epistemología (como veremos más abajo, con el segundo Wittgenstein).

Mientras tanto, aún quedaba por resolver otra de las preguntas de Hilbert, el problema de la decisión. ¿Sería posible desarrollar un método mecánico o algoritmo para saber si una fórmula de la aritmética es demostrable o no? ¿Qué pasaría si existiera un sistema de decisión así y se le pidiera determinar la demostrabilidad de la fórmula de Gödel?

Para resolver el problema de la decisión había primero que desarrollar un modelo formal de un 'método mecánico o algoritmo'. El primero en hacerlo fue Alonzo Church con su cálculo lambda, basado en la definición de funciones recursivas. Los que seáis programadores ya sabéis lo que son, y los que no... pues tendrías que estudiarlo, y esta es la razón de que los trabajos de Church no sean hoy muy conocidos comparados con los de Turing.

La prueba de indecibilidad de Church es muy similar a la de Gödel. Church construye una función recursiva que al aceptar como entrada un código numérico que la representa a ella misma genera una contradicción.

Poco después, el matemático inglés Alan Turing crea en su tesis doctoral otro modelo formal de computabilidad, la máquina de Turing, y demuestra que el problema de decisión es equivalente al problema de si existe o no una máquina de Turing capaz de determinar si una máquina cualquiera se detendrá o no al presentársele una entrada de datos: es el llamado problema de la parada.

Nadie mejor que el propio Turing para explicarlo (en realidad se trata del personaje de Turing en el docudrama de la BBC Breaking the code):

El video que sigue explica perfectamente (y de manera divertida) como Turing demuestra que el problema de la parada no es resoluble. NO OS LO PERDAIS. Si los subtítulos no se activan solos, pulsad el botón CC y seleccionar la opción de traducción al español:

Poco después de las demostraciones de indecibilidad de Church y Turing, se hizo evidente que sus dos modelos de computabilidad eran equivalentes. Ambos pueden representar cualquier algoritmo. Esta afirmación, la llamada Tesis de Church-Turing, es indemostrable, pero nadie ha encontrado un contraejemplo: un proceso que sea calculable pero que no pueda realizar una máquina de Turing o una función lambda.

Por tanto, vemos que la capacidad de estos instrumentos formales para trabajar con representaciones de sí mismos les lleva a la imposibilidad de decidir la verdad o falsedad de ciertas cuestiones.

El lenguaje y lo que hay más allá: Wittgenstein

La vida y obra de Ludwig Wittgenstein merece seguramente varias películas y un blog dedicado a él solo. Confieso que se trata de mi filósofo favorito, tanto por lo dramático de su vida como por lo original y profundo de su pensamiento.

Wittgenstein abandonó a su rica familia vienesa (que le desheredó) y se marchó a estudiar aeronáutica a Inglaterra, donde le atrajo más el desarrollo de la lógica y los fundamentos de la matemática que Bertrand Russell (de quien hablamos en la entrada anterior) llevaba a cabo en Cambridge. Así que se convirtió en estudiante de Rusell, o más bien en un colega advenedizo que pasaba horas discutiendo con él y cuestionando las conclusiones y el programa de su supuesto mentor.

En un principio los objetivos de Wittgenstein parecían coincidir con los de Rusell y los positivistas lógicos del Círculo de Viena, incluso iban más allá de lo que éstos planteaban.

Wittgenstein no sólo quería fundamentar lógicamente las matemáticas, sino el lenguaje mismo, y dado que según pensaba el lenguaje determinaba la forma en que podemos pensar la realidad, estaría fundamentando así también la ontología y el conocimiento del propio mundo.

Sus ideas estaban relacionadas con las de Immanuel Kant (ver la primera parte de la entrada), solo que en lugar de ser las categorías kantianas de espacio, tiempo y causalidad las que determinan la realidad que podemos pensar con sentido, para Wittgenstein es la forma lógica del lenguaje la que define qué se puede comprender y expresar acerca de la realidad.

Wittgenstein desarrolla esta teoría en uno de los libros más fascinantes que existen, el Tractatus Logico-Philosophicus, donde en cortas sentencias numeradas, el filósofo mezcla los fundamentos de la Lógica (Wittgenstein desarrolló el método de las tablas de verdad y contribuyó la clarificar la lógica de predicados) con un intento de delimitar lo que se puede conocer con sentido. En apariencia, sería un programa similar al del positivismo lógico.

Pero aunque utiliza herramientas lógicas similares a Rusell y los positivistas, las intenciones de Wittgenstein son totalmente diferentes. Quiere mostrar que lo verdaderamente importante (la ética, la estética, la metafísica, el sentido del mundo, nuestros problemas vitales), lo que él denomina lo 'místico', es inalcanzable en el marco de la lógica, de la ciencia y del lenguaje. No puede 'decirse' con sentido, solo puede 'mostrarse'.

Vale la pena incluir aquí algunas de las proposiciones finales del Tractatus (podéis encontrar el texto completo aquí):

6.41 El sentido del mundo tiene que residir fuera de él. En el mundo todo es como es y todo sucede como sucede; en él no hay valor alguno, y si lo hubiera carecería de valor. 

 Si hay un valor que tenga valor ha de residir fuera de todo suceder y ser-así. Porque todo suceder y ser-así son causales. 

...

6.421 Está claro que la ética no resulta expresable. La ética es trascendental. (Etica y estética son una y la misma cosa.) 

...

6.521 La solución del problema de la vida se nota en la desaparición de ese problema. (¿No es ésta la razón por la que personas que tras largas dudas llegaron a ver claro el sentido de la vida, no pudieran decir, entonces, en qué consistía tal sentido?) 

...

6.522 Lo inexpresable, ciertamente, existe. Se muestra, es lo místico. 

Wittgenstein coincide con las tradiciones místicas y la filosofía oriental en la conclusión de que el enigma de las cuestiones últimas no puede resolverse ni explicarse con el lenguaje, y tiene que ver más con la liberación de las ataduras del propio lenguaje.

Wittgenstein también aborda desde esta perspectiva la duda de Kant sobre las ideas como el infinito, la eternidad, el Alma, el Mundo y Dios, y llega a una conclusión similar: estas ideas se sitúan más allá del lenguaje, están fuera del ámbito de lo que se puede decir con sentido.

6.45 La visión del mundo sub specie aeterni es su visión como-todo-limitado. El sentimiento del mundo como todo limitado es lo místico. 

Lo más fascinante para mí del Tractatus es que, aunque fue publicado en 1921, 10 años antes de la demostración de Gödel, el mismo libro se convierte en una gigantesca fórmula de Gödel que se niega a sí misma.

Wittgenstein se da cuenta de la que la filosofía no puede decir nada con sentido, pues trata de ideas que no tienen un significado dado por los hechos o la lógica.

Por tanto, el propio Tractatus se niega a sí mismo. Lo que el libro dice debe ser desechado después de leerlo, y lo único que queda a Wittgenstein es callarse, pues lo que hay más allá del lenguaje solo puede mostrarse. 

6.53 El método correcto de la filosofía sería propiamente éste: no decir nada más que lo que se puede decir, o sea, proposiciones de la ciencia natural - o sea, algo que nada tiene que ver con la filosofía ...

6.54 Mis proposiciones esclarecen porque quien me entiende las reconoce al final como absurdas, cuando a través de ellas -sobre ellas- ha salido fuera de ellas. (Tiene, por así decirlo, que arrojar la escalera después de haber subido por ella.) Tiene que superar estas proposiciones; entonces ve correctamente el mundo. 

7 De lo que no se puede hablar hay que callar. 

Debe ser el único caso de la historia en que un filósofo ha llegado a la conclusión de que debe callarse  :-)  Y la realidad es que Wittgenstein fue coherente con su diagnóstico y dejó la filosofía durante muchos años, hasta que se dio cuenta de que estaba equivocado (y muriéndose de hambre).

Obsérvese el paralelismo con los teoremas de Gödel, Church y Turing. El Tractatus es como la fórmula G: podemos reconocer que lo que dice es cierto, que realmente muestra que el lenguaje 'con sentido' tiene límites. Sin embargo, precisamente por estar construido con lenguaje (como la fórmula G está construida con un sistema formal), no tiene sentido él mismo. Otra paradoja de la razón autorreferente.

Si os interesa aprender algo más sobre Wittgenstein, os recomiendo este episodio de La Aventura del Pensamiento donde Fernando Savater explica la filosofía de este autor. Concretamente, a partir del minuto 9 habla del Tractatus, y en el minuto 11 de los ímites de lo decible:

En una fase posterior de su vida, Wittgenstein cambia su concepto del lenguaje, y lo basa no en la lógica formal, sino en las reglas que los mismos hablantes definen (implícitamente) y que pueden dar lugar a diferentes usos igualmente válidos. Como en diferentes 'juegos', no hay unos lenguajes más verdaderos que otros: cada uno es válido si sirve a los propósitos de los jugadores, si sigue sus reglas internas.

Aquí tenemos al mismo Wittgenstein explicándolo, en la película de Derek Jarman que lleva su nombre:

Para más diversión...

Varias ilustraciones de la primera y segunda parte de esta entrada están sacadas del maravilloso comic Logicomix, que relata de forma entretenida (con las pequeñas licencias dramáticas necesarias) la historia de Rusell, Gödel, Church, Turing y Wittgenstein en su implacable búsqueda de la verdad sobre los fundamentos de la lógica y las matemáticas.

También he utilizado ideas y adaptado la demostración del teorema de Gödel de uno de mis libros favoritos: Gödel, Escher, Bach: un Eterno y Grácil Bucle, con el que el matemático, filósofo y divulgador científico Douglas Hofstadter obtuvo el Premio Pulitzer. Se trata de uno de los libros que, a pesar de su volumen, se pueden disfrutar más por su humor, originalidad y profundidad.

Además, ¡averigüé hace poco que el mismo Philip K. Dick lo había leído y disfrutado él mismo!

La siguiente fotografía se parece bastante al estado de mi copia de esta joya, tras varias lecturas y mudanzas por el mundo:

Os dejo en buenas manos, hasta la próxima.

    Salvador