Gödel y Turing (Parte 9)

(A la parte 8 - A la parte 10)

Conjuntos recursivos y recursivamente numerables

Tomemos un conjunto finito de símbolos, que pueden ser letras, números, garabatos o símbolos de cualquier otra naturaleza. Estos símbolos formarán nuestro alfabeto. Digamos, para poner un ejemplo, que el alfabeto esté formado por tres símbolos: a, b, c.

Una vez fijado el alfabeto, podemos usarlo para construir palabras. Una palabra es simplemente una sucesión finita de símbolos (1). Por ejemplo, aaabc, aaa o bbbcc. Si los símbolos fueran cifras, las palabras serían simplemente números. Como veremos a continuación, en realidad siempre podemos suponer que las palabras son números. En efecto, si el alfabeto es, como antes, a, b, c, entonces el conjunto de todas las palabras posibles comienza (ordenado lexicográficamente) así: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, etc., sucesión de palabras que podemos rotular o numerar como 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, etc.

De este modo, en lugar de aa podemos decir 4 y en lugar de c, 3 y, por ejemplo, la frase “c no es parte de aa” se transformará en “3 no es parte de 4” (frase que en sí misma parece carecer de sentido, pero que es de una claridad meridiana si sabemos qué significado le estamos dando a “3” y “4”).

De ahora en adelante, entonces, hablaremos únicamente de conjuntos numéricos, aunque el lector no deberá perder nunca de vista que estaremos hablando en realidad de palabras sobre un alfabeto cualquiera. Sea N, entonces, el conjunto de todos los enteros positivos y sea A un subconjunto de N. Vamos a definir a continuación qué significa que A sea recursivo o recursivamente numerable.

Definición: A es recursivo si existe un algoritmo que, dado un entero n, nos permite decidir si n pertenece o no pertenece a A.

En otras palabras, A es recursivo si existe una máquina de Turing que acepta como entrada válida a cualquier número n y que da como salida “1” si n pertenece a A y “2” en caso contrario.

Por ejemplo, el conjunto de todos los números primos es recursivo. En efecto, existe un algoritmo que, dado un número cualquiera, determina si el número es primo o no. Una opción es dividir a n por todos los números entre 2 y n-1 y ver si en algún caso el resto es 0 (2). Es cierto que para ciertos valores de n este algoritmo tardará siglos en darnos una respuesta, pero no es eso lo que nos preocupa aquí. Sólo nos interesa que el algoritmo dé siempre una respuesta correcta y que lo haga al cabo de una cantidad finita de tiempo. A los efectos de nuestra definición, si esa cantidad de tiempo resulta ser un millón de años, no habrá ningún problema.

En realidad, todos los conjuntos que el lector pueda imaginar serán, casi con certeza, conjuntos recursivos. El conjunto los números cuadrados, de los números perfectos, de los primos de Fermat, etc. son todos recursivos.

Una pregunta natural es entonces ¿existen conjuntos que no sean recursivos? Pues bien, sí existen y, de hecho, ya vimos un ejemplo. En la Parte 8 vimos que si numeramos todas las máquinas de Turing como T1, T2, T3,... entonces no existe ningún algoritmo que, dado un número n, determine si n es o no es una entrada válida para la máquina Tn. En otras palabras, el conjunto de todos los n que son entradas válidas para Tn es un conjunto no recursivo.

Parientes cercanos de los conjuntos recursivos, son los conjuntos recursivamente numerables.

Definición: La definición formal dice que un conjunto A es recursivamente numerable si existe una función recursiva F tal que A está formado por los números F(1), F(2), F(3),.... (3)

Una manera menos formal, pero tal vez más clara de explicarlo, es ésta: imaginemos que tenemos una computadora que, una vez que la encendamos, permanecerá en funcionamiento por los siglos de los siglos, llamémosla, para referirnos cómodamente a ella, la Computadora Permanente. Esta computadora, de tanto en tanto, imprimirá un número.

Un conjunto A es recursivamente numerable si es posible programar a la Computadora Permanente de tal modo que se cumplan las siguientes dos condiciones:

1) Todo número que la computadora imprima debe pertenecer a A (es decir, nunca imprimirá un número que no esté en A).
2) Todo número que pertenece a A, tarde o temprano, deberá ser impreso al menos una vez.

La relación entre esta definición informal y la definición formal de más arriba será clara si convenimos en llamar F(1) al primer número que la computadora imprima, F(2) al segundo y así sucesivamente.

Todo conjunto recursivo es también recursivamente numerable. En efecto, supongamos que A es recursivo, existe entonces un algoritmo que, dado un número n, determina si n pertenece o no a A. El siguiente es el programa que podríamos cargar en la Computadora Permanente:

Paso 1: Defina n = 1.
Paso 2: Determine si n pertenece o no al conjunto A (usando el algoritmo correspondiente). Si pertenece, imprima n. Si no pertenece, no haga nada.
Paso 3: Sume 1 al valor de n y vuelva al Paso 2.

¿Existirá algún conjunto que sea recursivamente numerable, pero no recursivo? Antes de responder a esta pregunta, comprendamos claramente qué significaría esto. Supongamos que A fuese recursivamente numerable, pero no recursivo, por una parte esto significa que podemos programar a la Computadora Permanente para que vaya imprimiendo los elementos de A, pero que no tenemos ninguna forma de saber de antemano si un número dado será impreso o no alguna vez.

Podemos imaginar la siguiente historia. Programamos la Computadora Permanente y la echamos a andar. Por unas horas no sucede nada. Un día y medio después la Computadora imprime se rápida situación los números 2, 345 y 222. Pasan unos días e imprime el 13. Al cabo de quince años ha impreso los números 2, 345, 222, 13, 77, 1.300.000, 4 y 80. ¿Imprimirá alguna vez el 1? No hay forma de saberlo de antemano. Sólo podemos esperar. Si resulta que el 1 pertenece a A, algún día lo sabremos, aunque tal vez tengamos que esperar miles de años para ello. Pero si resulta que el 1 no está en A, nunca lo sabremos. Es decir, si al cabo de un millón de años el 1 no ha sido impreso, no hay forma de saber si será impreso al día siguiente o si nunca los será.

Vimos antes que el conjunto de todos los n que son entradas válidas para la máquina Tn no es un conjunto recursivo, veamos ahora que sí es recursivamente numerable.

Para verlo imaginemos que en la Computadora Permanente vamos cargando sucesivamente varios programas que trabajan en paralelo. Primero le cargamos el programa de la máquina T1 con 1 como entrada. Mientras la máquina trabaja, introducimos el programa de la máquina T2 con la entrada 2. Luego programamos T3 con la entrada 3, y así sucesivamente. Programamos además la siguiente instrucción: “si en algún momento la máquina Tn se detiene y da una entrada válida, imprima n.” (4)

De este modo, la Computadora Permanente irá imprimiendo todos los n que son entradas válidas para Tn y ningún otro número. Es decir, hemos visto así que el conjunto de todos los n que son entradas válidas para la máquina Tn (que no es recursivo) es recursivamente numerable.

Estamos aquí en el corazón mismo de nuestro tema, de cara al mismísimo Teorema de Gödel. Tomemos alguna conjetura matemática aún no resuelta, por ejemplo la Conjetura de Goldbach. (5) Notemos que si la conjetura fuese finalmente demostrada, se habrá demostrado un teorema, pero si la conjetura es refutada, de todos modos se habrá demostrado un teorema (el teorema diría “la conjetura es falsa”).

Sin entrar todavía en detalles, y permitiéndonos un dejo de imprecisión, podemos decir que el Teorema de Gödel afirma que el conjunto de todos los teoremas matemáticos es recursivamente numerable, pero no recursivo. El papel de la Computadora Permanente sería jugado en este caso por la comunidad matemática, que va imprimiendo sucesivamente todos los teoremas en forma de papers.

Que el conjunto no sea recursivo significa que hay afirmaciones de las que nunca se sabrá si son o no teoremas. Podría suceder que ni la afirmación “La Conjetura de Goldbach es cierta”, ni “La Conjetura de Goldbach es falsa” lleguen a ser nunca impresas. En ese caso diríamos que la Conjetura de Goldbach es una “proposición indecidible”. El Teorema de Gödel asegura que tales proposiciones indecidibles existen, pero a priori no hay de modo de saber cuáles son.

Notas:

(1) Técnicamente suele hablarse también de la palabra vacía, que es aquella que carece de símbolos. Nosotros, sin embargo, no necesitaremos incluirla en nuestras consideraciones. Por cierto, el término palabra se usa aquí en un sentido puramente técnico, una palabra no tiene por qué tener significado.

(2) Es obvio que no es éste el mejor algoritmo para determinar si un número es primo o no. He elegido a propósito el menos eficiente de todos los algoritmos para mostrar que no se trata aquí de una cuestión de eficiencia. No me interesa hallar el mejor algoritmo, me interesa saber solamente si existe alguno.

(3) Véanse las partes anteriores del artículo, esencialmente F es recursiva si existe un algoritmo que permite calcularla.

(4) En lugar de ir programando en paralelo las máquinas T1, T2, T3,... podemos reducir todo el proceso a un solo programa. Éste indicaría ejecutar la primera instrucción de T1 con la entrada 1. Luego las dos primeras instrucciones de T1 y T2 con las entradas 1 y 2 respectivamente. Luego las tres primeras instrucciones de T1, T2 y T3 con las entradas 1, 2 y 3 respectivamente. Y así sucesivamente. Cada vez que una máquina se detiene y da una salida válida, su número es impreso.

(5) La Conjetura de Goldbach afirma que todo número par mayor que 2 es suma de dos números primos. Hasta el día de hoy no se sabe si es cierta o falsa. Véase aquí más información.

(A la parte 8 - A la parte 10)