viernes, 12 de noviembre de 2010

Máquina de Turing.


Created by:
(Del monte, Vazquez, Flores, Torres)4SIS2



Objetivo de creación modular de una maquina de Turing

Mediante esta técnica se puedan desarrollarse maquinas de Turing complejas a partir de bloques de elementales a partir de maquinas mas pequeñas mediaste diagramas de transiciones.

La construcción de maquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

Pasos para la construcción de una máquina de Turing

1.-Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.
2.-Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos se encuentre en ninguno de los diagramas que se combinan.
3.-Para cada uno de los antiguos estados de parada p y cada x en y.

Ejemplificación de dicha construcción.


Los diagramas compuestos para la construcción modular de una maquina de Turing

Son aquellos en los que cada uno de los bloques de construcción se representa como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Un sistema Turing completo es aquel que puede simular el comportamiento de una máquina de Turing. Es evidente que salvando los problemas de memoria, los ordenadores modernos y los lenguajes de programación de uso general, son sistemas de Turing completos. También es evidente, que con independencia de su forma concreta, cualquier dispositivo que se comporte como un sistema de Turing completo, puede en principio ejecutar cualquier cálculo que realice cualquier computador.


Nota: Observe que la anterior afirmación no menciona para nada la posible dificultad de escribir el programa o del tiempo que pueda emplear en realizar el cálculo (cualquier cálculo que pueda hacer un ordenador puede teóricamente efectuarse con papel y lápiz).



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.


Maquina s de Turing Compuesta.


Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla , donde:
es un conjunto finito de estados.
es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. ( )
es el estado inicial.
es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
es el conjunto de estados finales de aceptación.
es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo como símbolo de "no movimiento" en un paso de cómputo.

Funcionamiento

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.





Visualización de una Maquina de Turing, en la que se ve el cabezal y la cinta que se lee
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.