Nos resulta intuitivo pensar que muchos de los problemas en los que nos vemos envueltos en la vida ordinaria no tienen solución computacional. “¿Me amaría aún si yo hubiese actuado de otro modo?”, “Estuvo realmente Moisés flotando en el Nilo?” no son preguntas que intuitivamente admitan una respuesta computacional. Otros problemas teóricos y científicos son también, al menos aparentemente, insolubles en términos computacionales. Por “computable” entenderemos siempre aquí computable en sentido estándar, esto es, capaz de ser soluble por medios finitos, precisos y recursivos.

Sí es sorprendente y de alto interés teórico el que (a) se demuestre rigurosamente que determinados problemas son insolubles por cualquier computación, y (b) tales problemas sean formulables aritméticamente. Imaginemos que introducimos arbitrarias secuencias finitas en un sistema dotado de estas reglas: (1) responde “sí” si la secuencia codifica un programa que termina, (2) responde “no” si no lo hace (no codifica un programa o no termina). Este es el problema de la parada de Turing, para el que demostró que no existe un procedimiento algorítmico de decisión. El interés de este resultado de indecibilidad computacional es que permite demostrar la indecibilidad de cuantos problemas plantean tareas que permitan decidirlo. Rice generaliza y extiende los resultados de Turing para  cualquier propiedad no trivial de funciones  parciales.

Es de interés advertir que éste y otros resultados limitativos de la lógica, como la incompletud, no nos enseñan que nosotros podamos demostrar resultados inaccesibles a ningún ordenador. Podemos, y esto no es sorprendente, creerlos.

2. Conceptos

La idea general de computación suele hacerse matemáticamente precisa mediante la noción de recursión. La tesis de Church establece que todas las funciones computables son recursivas. Bajo este supuesto, todas las funciones computables son definibles en el lenguaje de la aritmética formal, o bien, indistintamente, mediante los algoritmos de las máquinas de Turing.

De este modo, a cada programa o cómputo M corresponde un número natural n que es su código o índice M_n. El resultado de introducir una entrada o input k en la máquina M, da como resultado una secuencia M(k). En consecuencia los lenguajes de computación se aplican a sí mismos, como un cómputo puede aplicarse sobre su propio código (M_m(m)), y ésta es fuente tanto de fructíferas aplicaciones como de limitaciones lógicas de la computabilidad.

Decimos que un conjunto es recursivamente enumerable syss es definible en el lenguaje RE de la aritmética formal de primer orden (básicamente es el lenguaje estándar sin negación y cuantificación acotada). De modo equivalente, decimos que un lenguaje es recursivamente enumerable si contiene todas las cadenas finitas que codifican una máquina de Turing y una entrada, de manera que la máquina se para en ese input. Un conjunto (un problema, un lenguaje) es recursivo si tanto él mismo como su complemento son recursivamente enumerables.

Por ejemplo, consideremos el problema TERMINA que consiste en determinar, dado un programa con código m y una entrada n para ese programa,  si el programa termina o no en n. El problema TERMINA(m,n) es recursivamente enumerable, puesto que existe algún programa que acepta TERMINA,  en el sentido de terminar si su entrada está en TERMINA, y no hacerlo en caso contrario. Un programa que computa TERMINA, termina en alguna entrada n. 

Consideremos ahora el complemento NOTERMINA del problema TERMINA. Si existe un programa para él, terminará si su entrada está en NOTERMINA, y en caso contrario no terminará. Como veremos, NOTERMINA no es recursivamente enumerable, y por tanto TERMINA no es recursivo.  Este es informalmente el curso de la argumentación siguiente. 

3. Pruebas

Teorema de enumeración. Hay una relación diádica T(x,y) que es recursivamente enumerable y enumera recursivamente todos los conjuntos recursivamente enumerables. Esto es, para cualquier conjunto C recursivamente enumerable hay un código e tal que C={n:T(e,n)}.

Prueba: Sea R_e el conjunto {x:T(e,x)}. T_e es recursivamente enumerable, pues tanto T como e son definibles en el lenguaje RE. Puesto que C es por hipótesis también recursivamente enumerable, es definido por una fórmula en una variable libre x. Sea e el código o número de Gödel de esa fórmula. Por tanto C=T_e.

Cierto teorema “diagonal”. La relación diagonal no es computable (recursiva).

Prueba: Sea K el conjunto {x:T(x,x)}. K es recursivamente enumerable, pero su complemento –K no lo es. Si lo fuese, -K=T_e para algún e. Pero para todo x, por definición de complemento, x pertenece a –K  syss x no pertenece a T_x. En el caso particular de e,  tenemos e pertenece a –K syss e no pertenece a T_e, esto es syss e no pertenece a –K, lo que es contradicción clásica.

Teorema de parada. TERMINA no es computable (recursiva).

Prueba: Supongamos por reductio que la función en dos argumentos t (m,n) fuese computable siendo t(m,n)=1 ó =0 dependiendo de si la máquina m, tomando como entrada n, termina o no.  Si lo fuese, la función diagonal t(n,n)=t’(n) lo sería, lo cual es imposible por el anterior teorema diagonal.}