La Tesis de Turing
Tomemos la máquina de Turing que hemos descripto en la parte 3 y apliquemos las instrucciones de su programa a la entrada formada por cinco símbolos # consecutivos. Al cabo de unos pocos pasos llegaremos al estado q0 (que marca el final del cómputo), veremos entonces que la salida de la máquina correspondiente a esa entrada está formada por cuatro símbolos # consecutivos. Por otra parte, si tomamos como entrada un único símbolo #, entonces la máquina nunca llegará al estado q0. Es decir, la máquina se colgará entrando en un estado de cómputo perpetuo.
Definición: Dada una máquina de Turing, diremos que una entrada es válida para ella si al cabo de una cantidad finita de pasos la máquina llega al estado q0 y la salida así obtenida está formada por cierto número de símbolos # consecutivos.
Por ejemplo, para la máquina descrita en la parte 3, la entrada ##### (que indicaremos como #5) es válida, mientras que la entrada # (o #1) no lo es.
Démosle un significado concreto a estas entradas y salidas. Convengamos en que una sucesión de n símbolos # consecutivos (es decir #n) representa el número n. Otras entradas no tendrán significado para nosotros. Entonces, en el ejemplo anterior podemos interpretar que la entrada es el número 5 y que la salida es el 4.
Interpretando de esta forma las entradas y las salidas, es fácil comprobar que si la entrada de la máquina descripta en la parte 3 es un número n > 1 entonces la salida será el número n – 1; para n = 1, ya dijimos, la máquina no da salida alguna. En otras palabras, la máquina de la parte 3 representa un algoritmo que calcula la función f(n) = n – 1, cuyo dominio (1) es el conjunto de los enteros mayores que 1. (2)
La Tesis de Turing dice que, codificadas adecuadamente las entradas y las salidas, todo algoritmo puede representarse mediante una máquina de Turing (3). Es decir, para todo algoritmo A existe una máquina de Turing T tal que para cada entrada para la que A dé una salida, T también da una salida y además exactamente la misma. Si A no da una salida, T tampoco.
Observemos que no es posible demostrar esta tesis, ya que para obtener una tal demostración deberíamos tener una definición previa del concepto de algoritmo, pero justamente esta definición es lo que se pretende dar con el concepto de máquina de Turing. Sí podemos decir a favor de la tesis que todas las demás definiciones que se han dado del concepto de algoritmo (incluida la concepción de Alonzo Church) han resultado ser equivalentes a la dada por Turing, es decir los procesos representados por cualquiera de esas otras definiciones son exactamente aquellos que pueden representarse mediante máquinas de Turing.
Aceptada la Tesis de Turing como un axioma, concluimos que si pudiéramos demostrar que cierto problema matemático es irresoluble por cualquier máquina de Turing, entonces habremos demostrado que es irresoluble por cualquier programa informático, presente o futuro.
Notas:
(1) El dominio de f(n) es el conjunto de los valores de n para los cuáles el cálculo tiene sentido (es decir, para los cuales el cálculo puede realizarse y da como resultado un número entero mayor o igual que 1).
(2) Sólo trabajaremos con algoritmos cuyas entradas y salidas sean números, o conjuntos finitos de números enteros mayores o iguales que 1. Para representar conjuntos (o n-uplas) se pueden anotar en la cinta de la máquina varias series de símbolos # separadas por casillas vacías.
(3) Es posible definir máquinas que trabajen con más símbolos, que utilicen más cintas ó cuyos cursores puedan moverse dos ó más casillas a la vez. Sin embargo, tales cambios no representan ninguna diferencia esencial. Todo cálculo que pueda ser hecho por estas máquinas con más recursos puede también ser realizado, aunque en general más lentamente, por alguna máquina con una única cinta como la que hemos descrito en la parte 3.
(A la parte 3 - A la parte 5)
No hay comentarios.:
Publicar un comentario