Maq. Turing

Universidad Mariano Gálvez de Guatemala
Ext. Guastatoya, El Progreso
Ing. Alexis Orellana
Lenguaje Formal y Autómatas

MAQUINA DE TURING

1890-11-8023
4to. Semestre
Sección A
Guastatoya, 10 de noviembre del 2012
Maquina de turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, unamáquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.
 La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicosa entender los límites del cálculo mecánico.
Una máquina de Turing consta de:
1. Una cinta que se divide en celdas, una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo especial llamado blanco (aquí escrito como 'B') y uno o más símbolos adicionales. La cinta se supone que es arbitrariamente extensible hacia la izquierda y hacia laderecha, es decir, la máquina de Turing siempre es suministrada con tanta cinta como necesite para su computación. Las celdas que no se hayan escrito previamente se asumen que están rellenas con el símbolo blanco. En algunos modelos la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible hacia la derecha.
2. Un cabezal que puedeleer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una (y sólo una) celda a la vez. En algunos modelos el cabezal se mueve y la cinta es estacionaria.
3. Un registro de estado que almacena el estado de la máquina de Turing, uno de los estados finitos. Hay un especial estado inicial con que el registro de estado es iniciado. Turing escribe que estos estadosreemplazan el "estado de la mente" en que ordinariamente estaría una persona realizando cálculos.
4. Una tabla finita de instrucciones (llamada ocasionalmente como tabla de acción o función de transición). Las instrucciones son usualmente 5-tuplas: qiaj→qi1aj1dk, (a veces 4-tuplas), que, dado el estado (qi) la máquina está actualmente en y el símbolo (aj) se está leyendo en la cinta (el símboloactualmente debajo del cabezal) le indica a la máquina hacer lo siguiente en secuencia (para los modelos de 5-tupla):
* Borra o escribe un símbolo (reemplazando aj con aj1), y entonces
* Mueve el cabezal (que es descrito por dk y puede tener los valores: 'L' para un paso a la izquierda, o 'R' para uno paso a la derecha, o 'N' para permanecer en el mismo lugar) y luego
* Asume elmismo o un nuevo estado como prescrito (ve al estado qi1).
Una máquina de Turing 4 es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

donde:5
*  es un conjunto finito de estados.
*  es un conjunto finito desí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ónparcial denominada función de transición, donde  es un movimiento a la izquierda y  es el movimiento a la derecha.
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:
* Mover el cabezal lector/escritor hacia la derecha....