Gödel y Turing (Parte 10)

(A la parte 9 - A la parte 11)

Más sobre conjuntos recursivamente numerables

Veremos esta vez algunas cuestiones técnicas que nos serán de utilidad un poco más adelante.

Hablábamos en la parte anterior sobre conjuntos recursivos y conjuntos recursivamente numerables. Recordemos que un conjunto A es recursivo si existe un algoritmo que, dado un número n, nos permite determinar (en una cantidad finita de tiempo) si n pertenece o no pertenece al conjunto A (el tiempo que demore el algoritmo en dar una respuesta puede ser extremadamente largo, eso no importa siempre que sea finito).

Definición: Diremos que un algoritmo decide al conjunto A si admite como entrada válida a cualquier número n y da como salida un “sí” en caso de que n pertenezca a A y un “no” en caso contrario. (Si lo quisiéramos expresar en términos de máquinas de Turing, podríamos decir que la salida es # si n pertenece a A y ## en caso contrario.)

Es claro que A es recursivo si y sólo si existe un algoritmo que lo decide.

Un conjunto A, por otra parte, es recursivamente numerable si es posible programar a la Computadora Permanente (una computadora teórica que permanece encendida por tiempo indefinido imprimiendo números de tanto en tanto) de tal modo que todo número que la computadora imprime pertenece al conjunto A y tal que, además, pueda asegurarse todo elemento de A será impreso al menos una vez, aunque para que ello debamos esperar millones de años. (Para más detalles y ejemplos, véase la parte anterior.)

Vimos también que todo conjunto recursivo es recursivamente numerable, pero que existen conjuntos que son recursivamente numerables pero no recursivos. Específicamente vimos que si se numeran algorítmicamente todas las máquinas de Turing como T1, T2, T3,... entonces el conjunto de todos los n que son entradas válidas para Tn es recursivamente numerable, pero no recursivo.

Nuestra intención en esta parte es mostrar que existen conjuntos que no son ni siquiera recursivamente numerables.

Si A es un conjunto (siempre pensaremos en conjuntos formados por números enteros positivos), se llama complemento de A al conjunto formado por todos los números que no pertenecen a A. Por ejemplo, el complemento del conjunto de todos los números pares es el conjunto de los números impares; el complemento del conjunto de los números terminados en 5 es el conjunto de los números terminados en cualquiera de las otras nueve cifras, etc.

Un hecho obvio, pero fundamental, es que cualquiera sea el conjunto A todo número n pertenece, o bien a A, o bien a su complemento, y nunca a los dos a la vez.

Propiedad: Si A es un conjunto recursivo entonces su complemento también es recursivo.

En efecto, si A es recursivo entonces existe un algoritmo que lo decide. Tomemos el mismo algoritmo, pero agreguemos una instrucción que transforme el “sí” en “no” y viceversa, obtendremos así un algoritmo que decide el complemento de A.

Propiedad: Si A y su complemento son ambos recursivamente numerables entonces A es recursivo.

En efecto, si A y su complemento son ambos recursivamente numerables entonces existen dos Computadoras Permanentes, una que imprime los elementos de A y otra que imprime los de su complemento. Ahora bien, y esto es esencial, dado cualquier número n, éste número, al cabo de una cantidad finita de tiempo, será impreso por una y sólo una de las dos computadoras. El algoritmo para decidir A es entonces el siguiente: cuando le den un número n, ponga a andar las dos Computadoras Permanentes a la vez, la de A y la de su complemento, y espere a que n sea impreso por alguna de las dos (tarde o temprano esto sucederá). Si lo imprime la Computadora de A la salida es “sí”, si lo imprime la otra computadora la respuesta es “no”. (El argumento precedente falla si se tiene solamente una de las Computadoras Permanentes, pues no se tendría la garantía de obtener una respuesta al cabo de una cantidad finita de tiempo.)

Propiedad: Si A es recursivamente numerable, pero no recursivo entonces el complemento de A no es ni siquiera recursivamente numerable.

Esto es una consecuencia de la propiedad anterior. Si el complemento de A fuese también recursivamente numerable, entonces A sería recursivo.

Dijimos antes que el conjunto de todos los números n que cumplen la propiedad “n es entrada válida para la máquina Tn” es recursivamente numerable, pero no recursivo. En razonamiento precedente nos dice que el conjunto de todos los n que cumplen que “n no es entrada válida para Tn” no es ni siquiera recursivamente numerable. Si intentamos programar la Computadora Permanente para que imprima estos valores de n entonces fallará, es decir, o bien imprimirá números que no pertenecen al conjunto, o bien nunca imprimirá algunos de los números que sí están, no importa cuánto tiempo esperemos.

Llegados a este punto ya estamos en condiciones de enunciar e incluso demostrar el Primer Teorema de Incompletitud de Gödel. Sin embargo, para entenderlo cabalmente resulta conveniente conocer el contexto histórico en el que Kurt Gödel llevó adelante su idea. En la parte 12 acometeremos la tarea de comprender ese contexto histórico. En la parte 11 haremos una aclaración importante.

(A la parte 9 - A la parte 11)