gsc

febrero 4, 2008

Algoritmos y máquinas de Turing

Filed under: General — gsc @ 1:40 pm

¿Qué es exactamente un algoritmo, o una máquina de Turing, o una máquina universal de Turing? ¿Por qué estos conceptos son tan cruciales para el punto de vista moderno acerca de lo que podría constituir un “dispositivo pensante”? ¿Existe alguna limitación absoluta para lo que un algoritmo pueda, en principio, hacer? Para tratar adecuadamente estas cuestiones es necesario examinar con cierto detalle la idea de algoritmo y de máquina de Turing.

Uno de los ejemplos más conocidos es el procedimiento hoy conocido como algoritmo de Euclides, que data de la época griega (c. 300 a.C.) , para encontrar el máximo común divisor de dos números, el mayor número divisor de estos dos números. Para ello, se realizan de forma sucesiva divisiones de estos dos números y los restos de las divisiones, hasta llega a una división exacta. El algoritmo de Euclides es el procedimiento sistemático mediante el que se encuentra ese divisor, pudiéndose aplicar para números de cualquier magnitud. Para números muy grandes el procedimiento puede tardar bastante tiempo, y cuanto mayor sean los números más tiempo necesitará. Pero en cualquier caso concreto el procedimiento llegará a su final y se obtendrá una respuesta definida en un número finito de pasos. En cada paso está perfectamente claro qué operación debe realizarse, y también es perfectamente clara la decisión de cuándo debe darse por terminado todo el proceso.

Este procedimiento no está todavía descompuesto en sus partes más elementales: se ha supuesto implícitamente que ya “sabemos” cómo efectuar la necesaria operación básica para obtener el resto de una división entre dos números naturales A y B arbitrarios. Dicha operación es también algorítmica.

A pesar de los antiguos orígenes históricos de ejemplos concretos de algoritmos, la formulación precisa del concepto general de algoritmo data sólo de este siglo. Se han dado varias descripciones alternativas de este concepto, siendo la más directa, convincente, e importante históricamente, la definición en términos del concepto conocido como máquina de Turing. El concepto fue introducido por Alan Turing para resolver un problema de muy amplio alcance, el Entscheidungsproblem, planteado por David Hilbert entre 1900 y 1928. Hilbert había pedido un procedimiento algorítmico general para resolver cuestiones matemáticas -o mejor dicho, una respuesta a la cuestión de si semejante procedimiento podía o o existir en principio. Dicho de otro modo: ¿existe algún procedimiento mecánico general que pueda, en principio, resolver uno tras otro todos los problemas de las matemáticas (que pertenezcan a una clase apropiadamente bien definida)?

Parte de la dificultad apara resolver esta cuestión consistía en decidir lo que se debe entender por “procedimiento mecánico”. El concepto quedaba fuera de las ideas matemáticas comunes de la época. Para poder manejarse, Turing trató de imaginar cómo podría formalizarse el concepto de “máquina”, descomponiendo su modo de operar en términos elementales. En este sentido, Turing consideraba también el cerebro humano como un ejemplo de “máquina”, de modo que, cualesquiera que fueran las actividades que pudiera llevar a cabo un matemático humano cuando aborda sus problemas de matemáticas éstas también tendría que entrar en la etiqueta de procedimientos mecánicos.

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

  • avanzar el cabezal lector/escritor hacia la derecha.
  • avanzar el cabezal lector/escritor hacia la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(Estado, valor) -> (Nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta. Disponiendo de este autómata de estados sencillo, no resulta complicado construir máquinas concretas que efectúen operaciones aritméticas básicas, como la suma de dos números, su multiplicación, o la elevación de uno a la potencia del otro. También pueden darse operaciones cuyo resultado es un par de números naturales, tales como la división con resto – u otras en las que el resultado es un conjunto finito pero arbitrariamente grande de números. Por otra parte, pueden construirse máquinas de Turing para las que no se especifica por adelantado qué operación aritmética hay que realizar, si no que las instrucciones para ello están introducidas en la cinta. Quizás la operación concreta que haya que realizar en una etapa depende del resultado de algún cálculo que la máquina tiene que hace en alguna etapa anterior (ejecución condicional). Parece evidente que, a partir de máquinas de Turing que realizan operaciones aritméticas o lógicas, podrían construirse tareas más complicadas de naturaleza algorítmica, y que puede realizar cualquier operación mecánica. Resulta razonable matemáticamente definir una operación mecánica como una operación que puede ser llevada a cabo por una máquina semejante. Desde el momento en que un procedimiento es suficientemente claro y mecánico, resulta razonable creer que se puede encontrar una máquina de Turing que realmente lo realice, por lo que parece que la máquina de Turing responde a su objetivo inicial.

El problema de la Parada

Hasta ahora, solo se han considerado operaciones con números naturales, y se ha señalado que simples máquinas de Turing pueden manejar números naturales de tamaña arbitrariamente grande, a pesar de que cada máquina tiene un número finito fijo de estados internos diferentes. ¿Qué ocurre con el resto de números? Los números negativos y fracciones pueden ser fácilmente manejados por máquinas de Turing, y los numeradores y denominadores pueden ser tan grandes como se desee, adoptando la codificación apropiada para los signos “-” (menos) y “/” (división). Sin embargo, para las expresiones decimales infinitas como Pi (3,1415…) o Raíz cuadrada de 2 (1.4142…) ni el input ni el output de una máquina de Turing puede ser infinito: sería posible construir una máquina que generase uno tras otro los números que componen Pi (3, 1, 4,1, etc.), pero esto no está permitido a una máquina de Turing. Mientras la máquina no hay alcanzado una instrucción STOP, el otuput está sujeto a posibles cambios, y, por consiguiente, no puede ser dado por válido. Por otro lado, una vez que se ha alcanzado el STOP, el output es necesariamente finito.

Volviendo al objetivo para cual Turing desarrollo originalmente sus ideas: ¿existe algún procedimiento mecánico para responder a todas las cuestiones matemáticas pertenecientes a una clase amplia pero bien definida? Turing descubrió que podía enunciar su versión de la pregunta en términos del problema de decidir si la n-ésima máquina de Turing se parará o no cuando actúe sobre el número m. Este problema fue llamado problema de la detención o de la parada. Resulta fácil consturir una lista de instrucciones con arreglo a las cuales la máquina no se parará para ningún número m (por ejemplo, n= 1 ó 2, o cualquier otro caso en que no haya ninguna instrucción STOP). Sería correcto decir que un presunto algoritmo no es de mucha utilidad cuando sigue actuando idefinidamente sin pararse núnca. Eso no es en modo alguno un algoritmo. ¿Cómo decidir si una máquina de Turing particular (a la que se le introduce un input específico) se parará alguna vez o no? Para muchas máquinas de Turing esto no será dificil de responder; pero, en ocasiones, puede no ser tan sencillo.

Para demostrarlo, supongamos que el problema de la parada tiene solución, es decir, supondremos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing para con una entrada determinada.

Consideremos una máquina de Turing P, que recibe como entrada una máquina de Turing M y una cadena w codificadas en la cinta y una a continuación de la otra (Mw), y que se encarga de ejecutar M sobre la cadena w. La máquina P parará y aceptará la entrada si M para con w, y parará y rechazará la entrada si M no para con w.

Modificamos la máquina P, creando una máquina P’ equivalente. Esta máquina no parará si M para con w, y parará si M no para con w. Obsérvese que esta modificación es trivial en términos de máquinas de Turing.

Ahora crearemos una máquina D, cuya función es la siguiente. Recibe una máquina M, la pasa por una máquina que se encarga de copiar la máquina M a continuación. Por lo tanto, a la salida de la máquina copia, la cinta contendrá MM (la codificación de la máquina repetida). A continuación, D coge este resultado y lo pasa a través de P’. Con esto intentamos decidir si la máquina M para con la entrada M. Es decir, si M para con la entrada M, entonces D no para, y si M no para con la entrada M, entonces D para. Nótese que la máquina de copia no es difícil de implementar.

Por último, tomaremos una máquina D (denominaremos SD), y le aplicaremos como entrada una máquina D. SD aplica como entrada a la máquina que recibe, la misma máquina. Por lo tanto, esta máquina en principio parará si D no para con entrada D, y no parará si D para con entrada D. Pero si SD no para y si D para con entrada D, sabiendo que D=SD, llegamos a una contradicción, por que aplicar D a SD debería dar como resultado lo mismo que aplicar D sobre D. Del mismo modo para el otro caso. Por lo tanto, el problema de la parada no tiene solución.

Todas las máquinas que hemos ido implementando en la demostración son, exceptuando P, relativamente fáciles de hacer, por lo que la clave de la demostración se encuentra, por reducción al absurdo, efectivamente en P, que es quien sostenía la hipótesis acerca de la resolubilidad del problema.

 

About these ads

El tema Rubric. Crea un blog o un sitio web gratuitos con WordPress.com.

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: