Gödel y Turing (Parte 8)

(A la parte 7 - A la parte 9)

Una función no recursiva

Vimos en la parte anterior que existe una forma de numerar todas las máquinas de Turing (T1, T2, T3,...) de manera tal que sea posible construir una máquina de Turing U (llamada máquina universal) que al recibir como entrada el par (n,m) imita el comportamiento que tendría la máquina Tn al recibir como entrada al número m. Más precisamente, si ante la entrada m la máquina Tn se detiene después de una cantidad finita de pasos, lo mismo sucederá con U al recibir el par (n,m) y en ambos casos la salida será la misma. Si con la entrada m la máquina Tn entra en un estado de cómputo infinito, lo mismo sucederá con U al recibir el par (n,m).

Recordemos ahora que cada máquina de Turing (llamémosla Z) define una función F cuyo dominio es el conjunto de todas las entradas válidas de Z, es decir el conjunto de todos los enteros positivos n que, ingresados en Z, hacen que la máquina se detenga después de una cantidad finita de pasos y que dé como salida algún número m. El valor de F(n) se define, precisamente, como ese número m.

Recordemos finalmente que una función F es recursiva parcial si y sólo si existe una máquina de Turing Z tal que F es la función definida por ella. Es decir, una función es recursiva parcial si existe un algoritmo que permite calcular F(n) para cada n de su dominio y que se “cuelga” si intenta calcular el valor de F(n) para algún n que no pertenezca al dominio. Si este dominio está formado por todos los números enteros positivos entonces la función se denomina recursiva.

Vamos a definir ahora una función G, cuyo dominio será el de todos los números enteros positivos y que, como veremos, no es recursiva.

Instrucciones para calcular G(n):

Entrada: n.
Paso 1: Determine si n es una entrada válida para Tn.
Paso 2: Si en el paso 1 la respuesta es sí, calcule la salida de U(n,n),, si es el número m, defina G(n) = m + 1.
Paso 3: Si en el paso 1 la respuesta es no, defina G(n) = 1.
Salida: G(n).

Demostremos que la función G no es recursiva. Supongamos que sí lo fuera, entonces existiría un número n tal que Tn calcula G. Como el dominio de G es el conjunto de todos los enteros positivos entonces n es una entrada válida para Tn, llamemos m a la salida. Este m es la salida de U(n,n), luego G(n) = m + 1. Luego, la salida de Tn no coincide con el valor de G(n), lo cual contradice que Tn calcule G.

No existe entonces ningún algoritmo que permita calcular la función G. Pero el conjunto de instrucciones que definen G(n) ¿no es acaso un algoritmo que calcula el valor de G(n)? ¿Cómo podemos salir de esta aparente contradicción?

La respuesta es que un conjunto de instrucciones no es necesariamente un algoritmo. Para que realmente lo sea, debemos estar seguros de que cada uno de sus pasos puede ejecutarse mecánicamente. La única conclusión que nos permite evitar la paradoja es que el conjunto de instrucciones que define a G no es realmente un algoritmo.

¿Es posible ejecutar mecánicamente el Paso 2 o el Paso 3? Evidentemente sí. Por lo tanto, el “culpable” sólo puede ser el Paso 1, es este paso el que no puede ejecutarse mecánicamente, el que no puede reducirse a una serie de pasos elementales.

Por lo tanto, no existe ningún algoritmo que, dado un número n, nos permita determinar si n pertenece es o no una entrada válida para Tn. Una ligera modificación del argumento nos permite demostrar que no existe un algoritmo que, dado n, permita decidir si al recibir esta entrada la máquina Tn se detendrá o no se detendrá al cabo de una cantidad finita de tiempo. A este último problema se lo denomina tradicionalmente “el problema de la parada” (en inglés, the halting problem.) El problema de la parada, entonces, no es resoluble algorítmicamente.

El Entscheidungsproblem es el problema (planteado por David Hilbert) que pide decidir si, dada una cierta rama de la Matemática, será posible hallar un algoritmo que resuelva todos los problemas que puedan plantearse en ella. El razonamiento anterior nos muestra que la respuesta al Entscheidungsproblem es negativa. En efecto, en la teoría de algoritmos el problema de la parada no es resoluble algorítmicamente. Por lo tanto no es posible resolver mecánicamente todos los problemas de esa rama del conocimiento.

Es importante destacar que la imposibilidad se refiere a la existencia de un método general que permita decidir, para cualquier n, si la entrada #n es válida para la n-ésima máquina T (el mismo método para todos los valores de n). Sí es posible, en cambio, resolver la cuestión para valores específicos de n, usando en cada caso mecanismos diferentes.

Nota: Se insinúa aquí un argumento a favor de la idea de que la mente humana es esencialmente superior a una computadora. Este argumento diría así: hay cuestiones que una computadora no puede resolver, pero sí la mente humana. El argumento, hay que decirlo, es falaz y la falacia está muy claramente explicada en el artículo que se puede descargar haciendo click aquí. Hasta donde sabemos, el "juego" entre cerebro y computadora sigue todavía empatado.

(A la parte 7 - A la parte 9)