El teorema de Gödel (I)

Hofstadter compara el teorema de Gödel a una curiosa idea. Supone un gramófono de alta fidelidad que pueda producir todos los sonidos posibles. El gramófono se llama X y hay un disco que se llama “No puedo ser escuchado por el gramófono X”. Resulta que si se pone ese disco en el gramófono, éste produce unos sonidos que destruyen el propio gramófono. Es posible usar un gramófono de baja fidelidad, que no producirá esos sonidos y no se autodestruirá. Pero entonces ya no será un gramófono que produzca todos los sonidos posibles.

El sistema de Gödel es una parte de la teoría de la computación. Uno de los conceptos fundamentales para entender el tema de la teoría de la computación es lo que los matemáticos llaman conjunto recursivamente enumerable.

¿Qué es un conjunto recursivamente enumerable? Un conjunto A es recursivamente enumerable si la función f(x) :

f(x) = 1 ( si x pertenece a A)
f(x) = indefinido (si x no pertenece a A)

es computable

Que un conjunto sea recursivamente enumerable es equivalente a que el conjunto sea generable por computador. Un conjunto es recursivo, si tanto él como su complemento son recursivamente enumerables.

En muchos casos el concepto de recursivamente enumerable se usa solo para subconjuntos de N (el conjunto de los números naturales). Por ejemplo, los primos son un conjunto recursivo en N. Consideremos otro conjunto, como los números que forman la sucesión de Fibonacci.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

Los números de Fibonacci consisten en una serie en la que todo número excepto los dos primeros es la suma de los dos precedentes.

1+1=2
1+2=3
2+3=5
3+5= 8

Yo mismo he ideado un programa en Q-Basic que genera la serie de Fibonacci. La serie de Fibonacci es un típico ejemplo de programa sencillo y también un ejemplo de conjunto recursivamente enumerable. De hecho, un conjunto es recursivamente enumerable si puede ser generado por algún programa. En su libro, Hofstadter produce la serie de Fibonacci por lo que él llama una red de transición recursiva. De hecho, la serie de Fibonacci es un programa muy sencillo, que es usado en los lenguajes de programación para aprendices. Consideremos otro programa de Q-Basic . Un programa que produzca la serie de los números primos hasta un número dado, que el usuario debe introducir en el ordenador. Por ejemplo, el conjunto de los números primos es recursivamente enumerable. Pero ¿el conjunto de los números no primos es recursivamente enumerable? Sí, basta con generar un programa que nos dé todo número m, tal que exista un número n (mayor que 1 y menor que m) para el que se cumpla que el resto de m dividido entre n da 0. Cuando sucede a un conjunto que tanto sus elementos como los elementos que no pertenecen a ese conjunto (los primos como los no primos) son generados mediante sus respectivos programas de ordenador, se dice que ese conjunto es recursivo. Se dice también que tanto el conjunto (los primos) como su complementario (los no primos) son recursivamente enumerables. Es decir, que si el conjunto P es recursivamente enumerable y el conjunto complementario de P es, también, recursivamente enumerable, P es recursivo.

Se plantea la interrogante de si todos los conjuntos recursivamente enumerables son, a su vez recursivos. Lo cierto es que no. Existen conjuntos cuyos elementos son generables mediante un programa, pero no tenemos un programa para generar todos y cada uno de los elementos que no pertenecen al conjunto.

Hofstadter supone que tenemos un conjunto I (por ejemplo los primos) y un conjunto O (Por ejemplo, los números compuestos). Juntos I y O abarcan todos los números naturales. El problema es que hay conjuntos en que podemos generar todos los números del conjunto I, pero no hay programa para generar todos los números del conjunto O.

“Es importante fijarse en que, si los miembros del conjunto I fueran generados siempre en orden creciente, podríamos en todo momento caracterizar a O. El problema es que muchos conjuntos r.e. [recursivamente enumerables] son generados a través de métodos
que diseminan los elementos en un orden arbitrario, así que nunca se sabe si un número omitido largo tiempo obtendrá, esperando un poco más, su inclusión”

Si alguien, al tropezar con estas reflexiones, se asombra de que sea posible que tengamos programa para generar un conjunto pero no para generar su complementario, no debe preocuparse, ya que el mismo Hoftadster confiesa su asombro al ver que no todos los complementos de conjuntos recursivamente enumerables eran recursivamente enumerables. Lo compara a una figura, tal que su borde se pudiera discernir, pero no pudiera verse el borde del fondo que hay entorno a la figura.

“Resultó que yo estaba acertado acerca de los primos, pero equivocado en general, lo cual me asombró, y continúa asombrándome todavía hoy”

Por ejemplo, para todo programa, el conjunto de los inputs para los cuales el programa se para es recursivamente enumerable. Pero no es necesariamente recursivo. Por ejemplo, hay muchos programas, que para determinados inputs, se pierden en un bucle infinito.

Gödel supuso que el conjunto de las verdades matemáticas era recursivamente enumerable. y se dispuso a fabricar un sistema lógico (el equivalente de un programa informático) para generar todas las verdades y sólo las verdades de la matemática. Este programa, además, decidiría, dada una proposición matemática, si ésta era verdaera o no.

La idea de Gödel puede parecer, en principio, muy alejada de la de la Biblioteca de Babel, pero, como veremos, tiene algunas semejanzas. (en realidad algo análogo a lo que lo que Gödel se planteaba parece incompatible con la idea que tenemos de la Biblioteca de Babel: se trataría de buscar un procedimiento para discriminar todos los volúmenes de la Biblioteca que dicen verdad). La Biblioteca de Babel no existía en la realidad, pero era un objeto que podíamos imaginar. Del mismo modo, la Biblioteca de Gödel, es decir aquella Biblioteca que contiene todas las verdades de la aritmética es un objeto concebible, ya que Gödel dio las reglas de su codificación. De hecho, para ser más exactos habría que decir que el procedimiento para discriminar cuáles son las verdades en el mundo de la Biblioteca de Gödel es la demostración lógica, que viene a ser una forma restringida y más técnica de la demostración filosófica. La forma de codificar la Biblioteca de Gödel puede parecer alambicada. En primer lugar hay que reducir todas las verdades de la aritmética (en principio, restrinjámoslas a las afirmaciones acerca de números naturales) a fórmulas lógicas. Esto es esencial, ya que si queremos que las verdades de la aritmética sean demostradas hay que reducirlas inevitablemente a fórmulas lógicas. En segundo lugar, Gödel inventa un código por el cual reduce las fórmulas lógicas a números naturales. Tenemos pues tres niveles:

1) En primer lugar todas las verdades aritméticas sobre los números naturales
2) En segundo lugar las fórmulas lógicas que expresan cada una de esas verdades
3) En tercer lugar los números naturales que codifican esas fórmulas lógicas

Aquí encontramos una suerte de autorreflexión, ya que los números naturales sirven para codificar verdades sobre los números naturales. Como veremos, esto dará lugar a una paradoja que será el resultado fundamental de Gödel.