MAQUINA DE TURING

PowerPoint Presentation: 

MÁQUINA DE TURING Turing ideó un dispositivo imaginario al que denominó Máquina de computación lógica LCM (" Logical Computing Machine"), pero que ha recibido en su honor el nombre de máquina de Turing . Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.  Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia;  recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

PowerPoint Presentation: 

En realidad la máquina de Turing es más una abstracción matemática que un dispositivo físico o mecánico.  El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple. Existen diversas "variedades" de una máquina de Turing , pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones: Tiene una cinta sobre la que puede desplazarse a izquierda y derecha, un cabezal de lectura/escritura.  La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito;  este conjunto de símbolos se denomina el alfabeto de la máquina .

PowerPoint Presentation: 

En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o # ).  La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean necesarias para el funcionamiento de la máquina. El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto. Existe un registro de estado que almacena el estado de la máquina.  El número de estados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina.

PowerPoint Presentation: 

Existe una tabla de acción , que contiene las instrucciones de lo que hará el autómata.  Estas instrucciones representan en cierta forma el "programa" de la máquina.  Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos: Leer un carácter en la posición actual. Escribir un nuevo símbolo en esta posición (puede ser el mismo que había).  El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual. Desplazar el cabezal una celda a derecha o izquierda (R/L);  en algunos modelos el desplazamiento puede ser nulo (detener H). Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual.  Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.

PowerPoint Presentation: 

La tabla suele definirse mediante una matriz de cinco columnas que contiene : Estado/Carácter-leído/Carácter-a-escribir/Movimiento/Nuevo-estado En el siguiente ejemplo muestra una de estas tablas.  Representa el comportamiento de una máquina de turing que es capaz de sumar 1 a cualquier número unario.  El alfabeto solo tiene dos símbolos:  Vacío (0) y valor (1).  La máquina puede adoptar tres estados diferentes numerados del 0 al 2 (es costumbre señalar el estado inicial con 0).  El movimiento H (" Halt ") significa no desplazar el cabezal.  En este caso la máquina se detiene (o entra en un bucle sin fin).

PowerPoint Presentation: 

También es posible representar la tabla de acción mediante un grafo.  Los diferentes estados internos se representan por círculos.  Los cambios de estado con flechas a las que se añade una leyenda.  Generalmente se utiliza una flecha para señalar el estado inicial.  En la figura 1 se muestra el grafo correspondiente a la tabla.

PowerPoint Presentation: 

EJEMPLO: Supongamos una máquina de Turing con un alfabeto unario, en la que el nulo (ausencia de dato) lo señalamos con 0 .  La máquina puede tener cinco estados que denominamos { e0 , e1 , e2 , e3 , e4 }. El estado inicial es e0 ;  su tabla de acción se muestra a la derecha. Observe que la tabla debe contener al menos tantas filas como estados distintos.  La primera columna representa lo que podíamos denominar "estado mental" de la máquina.  La segunda columna indica el carácter leído;  representa la entrada (input) al autómata.  Las siguientes (en otro color) representan el comportamiento o respuesta de la máquina para la combinación estado/carácter-leído.  Esta respuesta tiene tres componentes:

PowerPoint Presentation: 

Una salida (escribir en la cinta). Indicado en la columna W . Un movimiento de avance o retroceso del cabezal sobre la cinta (indicado en la columna M ). Un cambio del estado interno actual del autómata a otro nuevo (columna N ). Observe que las filas pueden repetir el primer elemento;  significan las acciones a tomar en cada estado según el carácter leído.  Cada vez que se alcanza un estado para el que no exista una entrada para el carácter leído, la máquina se detiene.  En nuestro autómata la tabla señala acciones concretas para cualquier carácter leído ( 0 o 1 ) en cualquiera de los estados e1 , e2 , e3 y e4 , pero si en el estado e0 se lee un 0 , la máquina se detiene.

PowerPoint Presentation: 

La sucesión de pasos de cómputo es la siguiente (suponemos un estado inicial cualquiera ex ): 1.- Se lee un carácter c (en nuestro caso es necesariamente 0 o 1 ) 2.- Se mira en la tabla que fila corresponde a la combinación ex / c . 3a.- Si no existe entrada la máquina se detiene. 3b.- Si existe entrada se ejecuta la instrucción (columnas en marrón claro) en el siguiente orden: 3b1.- Se escribe en la posición actual el carácter señalado (puede ser el mismo que había). 3b2.- Se mueve el cabezal una posición a izquierda o derecha. 3b3.- Se pasa al estado señalado en la última columna (puede implicar no cambiar de estado). 3b4.- Se repite el ciclo desde el punto 1 .

PowerPoint Presentation: 

Ejercicio: Construir la maquina correspondiente a la Tabla anterior.