Gödel y Turing (Parte 6)

(A la parte 5 - A la parte 7)

Funciones recursivas parciales

Toda máquina de Turing Z define de manera natural una función F cuyo dominio (1) está formado por todos los enteros positivos n tales que #n es una entrada válida para Z, es decir, todos los números que, cargados en Z dan (después de una cantidad finita de tiempo) una salida que representa un entero positivo. El número F(n) se define entonces del siguiente modo: F(n) = m si y sólo si #m es la salida que corresponde a la entrada #n.

Definición: Diremos que una función G es recursiva parcial si existe una máquina de Turing Z tal que la función F por ella definida coincide exactamente con la función G (es decir, si F y G tienen el mismo dominio y además para cada número n de ese dominio vale que F(n) = G(n)). Cuando el dominio de G está formado por todos los enteros positivos, decimos simplemente que la función es recursiva.

Expresado en términos más simples, una función G es recursiva parcial si existe un algoritmo (o un programa de computadora) que permite calcular G(n) para cualquier número n de su dominio y que, cuando intenta calcular G(n) para un n que no pertenezca al dominio, o bien entra en un ciclo de cómputo infinito o bien da una respuesta ininteligible.

Como ya hemos visto en la Parte 4, la función G(n) = n – 1 (cuyo dominio está formado por los enteros mayores que 1) es recursiva parcial. Para dar otro ejemplo, veamos que la función H(n) = log n, cuyo dominio es el conjunto de las potencias de 10, es también recursiva parcial. Gracias a la Tesis de Turing no será necesario mostrar explícitamente una máquina T que calcule H(n), alcanzará con mostrar cualquier algoritmo que haga ese cálculo, la Tesis nos garantiza que dicho algoritmo podrá traducirse a una máquina T. En este caso un algoritmo puede describirse de la siguiente manera:

1) Entrada: n.
2) Defina k = 1.
3) Calcule 10 elevado a la k y compárelo con n, si son iguales deténgase, en caso contrario vaya al paso siguiente.
4) Sume 1 al valor de k y vuelva al paso 3).
5) Salida: k.

En realidad toda función que esté descripta mediante una o varias fórmulas basadas en las operaciones usuales (suma, resta, producto, cociente, radicación, etc.) será una función recursiva parcial. Casi cualquier función que Ud., lector, pueda llegar imaginar será, casi con certeza, una función recursiva parcial.

Surge entonces la pregunta siguiente: ¿existen funciones que no sean recursivas parciales? Es decir, ¿existen funciones tales que no haya algoritmos capaces de calcularlas? Curiosamente la respuesta es afirmativa.

Una manera indirecta de demostrar la existencia de infinitas funciones no recursivas parciales es la siguiente. Puede probarse con no demasiada dificultad que el conjunto de todas las máquinas de Turing es numerable, mientras que el conjunto de todas las funciones del conjunto de los números naturales en sí mismo es no numerable. Por lo tanto deben existir necesariamente funciones no calculables por máquina de Turing alguna. Es decir, existen funciones que no pueden ser calculadas algorítmicamente (no pueden ser “comprendidas” por un programa de computadora).

En la parte 7 iniciaremos el proceso que nos permitirá mostrar explícitamente un ejemplo concreto de función no recursiva.

Nota:

(1) A los efectos de estas notas, el dominio de F es el conjunto de todos los enteros positivos n para los cuales F(n) puede calcularse y da como resultado un entero positivo. Por ejemplo, para F(n) = n/2 el dominio está formado por todos los números pares.

(A la parte 5 - A la parte 7)