El teorema de Gödel (2)

La forma de codificar de Gödel es muy interesante.. Escribir una fórmula lógica es permutar una serie de signos en una serie de espacios, de forma que Gödel atribuye un número a cada signo y un número a cada espacio que ocupa el signo. Para los espacios o lugares que ocupan los signos se utilizan los números primos. 2 para el primer lugar, 3 para el segundo, 5 para el tercero, etc. Para los signos números convencionales. Por ejemplo 59 para “f1”, 3 para”(“, 15 para “x1”, 5 para “)”. Así “f1” se codifica con el número 2^59. Que quiere decir “f1 en el primer lugar”. Tengamos por ejemplo

“f1(x1)”

f1 en el 1º lugar= 2^59
( enel 2º lugar= 3^3
x1 en el 3º lugar=5^15
) en el 4º lugar= 7^5

El número que surge de multiplicar (2^59 · 3^3 · 5^15 · 7^5) es el número de Gödel de la fórmula “f1(x1)”.

Hay otra manera menos complicada de poner los números de Gödel. Por ejemplo, supongamos que “a” se traduce como 123, e “=” como 111. Entonces, “a = a” se traduciría como:

123111123

Como se ve, ésta es una forma de reducir todas las fórmulas lógicas, y con ello todas las verdades de la aritmética a números. Pero las verdades de la aritmética tratan sobre números, y estas mismas verdades están codificadas por números. Supongamos que la fórmula 123 dice que “1=0”. (Obviamente, esto es una falsedad). Tengamos, ahora, la fórmula

“a no es un teorema en el sistema de Gödel”

Cuando en esta fórmula el signo a es sustituido por el número 123, tenemos una afirmación ambigua, ya que dice a la vez:

“123 no es un teorema en el sistema de Gödel” y “1=0 no es un teorema en el sistema de Gödel”.

Ahora se trata de construir una cadena que se refiera a sí misma[1]. Por ejemplo, tengamos la siguiente fórmula, donde S0 significa el sucesor de 0, o sea 1:

a = S0

Esta fórmula lleva el número 262,111,123,666. Bueno, pues sustituyamos a por el número 262,111,123,666.

La fórmula quedará así

SSSSSSSSS……SSSSS0= S0
262,111,123,666 eses

Esto demuestra que se puede introducir el número de Gödel de una fórmula dentro de la propia fórmula.

Esto lleva a Gödel a construir un extraña fórmula. Esa fórmula afirma (aproximadamente) lo siguiente:

“La fórmula que lleva el número 15215 no es demostrable”

Pero esa misma fórmula, en la demostración de Gödel, lleva el número 15215. Naturalmente es indiferente que lleve este número u otro, lo fundamental es que existe una fórmula que dice:

“Esta fórmula es indemostrable en el sistema”.

Veamos. Esta fórmula está diciendo una verdad, porque, efectivamente, la fórmula no es demostrable en el sistema. Pero, por mucho que sea verdad, no se puede demostrar, ya que si se demostrara sería mentira. Supongamos que se demuestra: en ese caso está diciendo mentira, ya que afirma su propia indemostrabilidad. Por tanto, es una afirmación verdadera que no es demostrable en el sistema.

Por artificioso que parezca, éste es el principal argumento que se utiliza para demostrar que la inteligencia no es mecanizable.

En la Biblioteca de Gödel hay cuatro tipos de cadenas de signos:

1) los teoremas (las verdades que vienen generadas por el programa)
2) las verdades
3) las cadenas bien formadas
4) el resto de las cadenas de signos
5) los números que no corresponden a números de Gödel

Los teoremas, la clase más restringida, son aquellas verdades que han sido demostradas en el sistema. Como hemos visto, hay proposiciones que son verdaderas pero que no son demostrables en el sistema. El conjunto de las verdades es más amplio que el de las verdades demostrables en el sistema, precisamente por el hecho de que hay verdades que no son demostrables como las paradojas del tipo de la de Gödel. Más amplio aún es el conjunto de las cadenas bien formadas. Pues puede haber una cadena lógica bien formada pero que exprese un significado no verdadero como “A y no A” o “3 + 2= 4”. De hecho, por ejemplo, la expresión “p & ¬p”, que significa, precisamente, “p y no p” es una cadena bien formada de la lógica proposicional, y por ello debe tener un lugar en la biblioteca de Gödel, pero no es un teorema, y ni siquiera una verdad no demostrable. Aún más amplio es el conjunto del resto de las cadenas de signos, es decir, todas aquellas cadenas que están mal construidas, tales como “(((((((((((((“, por ejemplo.

Resumiendo, tendríamos cadenas que expresan un teorema demostrable, lo que podríamos ejemplificar con una oración del tipo “2 + 2 = 4”, tendríamos verdades no demostrables como “Esta afirmación no es demostrable en el sistema”. Tendríamos cadenas bien formadas pero que no son verdades y, por último, cadenas que no están bien formadas. Esta última distinción podríamos ejemplificarla, en el lenguaje natural, con la diferencia entre las frases “Llueve y no llueve” y “lluevxsdfghhjklñ”. La primera es falsa, pero la segunda, simplemente, está mal formada. Tenemos, pues, el conjunto de todas las cadenas, y dentro de él un conjunto más restringido, el de las cadenas bien formadas. Dentro del conjunto de las cadenas bien formadas tenemos el conjunto más restringido de las verdades, y dentro de éste el conjunto aún más restringido de las verdades demostrables en el sistema.

Por último hay números que no son números de Gödel.

La biblioteca de Gödel puede tener un programa para discriminar cuáles son las cadenas bien formadas. Obviamente, tiene un programa para discriminar cuáles son los teoremas, porque un sistema formal que produce teoremas es lo mismo que un programa informático. Pero lo que no tiene es un programa para generar las y sólo las que son verdaderas. El conjunto de las fórmulas bien formadas es recursivamente enumerable, y también lo es el conjunto de los teoremas. Pero el conjunto de las verdades no es recursivamente enumerable.

El teorema de Gödel sufre una autorreflexión del tipo del mapa de Iglaterra que estaba sobre el suelo de Iglaterra, ya que para codificar las verdades acerca de los números naturales utiliza los números naturales. Pero esto genera una autorreflexión que acaba por producir verdades que son indemostrables en el sistema. Es como esa porción del mapa que es irreproducible en el mapa (porque contiene el propio mapa).

[1]Sigo el ejemplo y la demostión de Douglas Hofstadter en "Gödel, Escher, Bach"