Máquina de Tring

 ¿Qué es la Máquina de Turing?

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una má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 una CPU dentro de un computador.

6.2   construccion modular de la maquina de turing

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 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.

Una Máquina de Turing consta de una cinta infinita dividida en espacios de trabajo o celdas yuxtapuestas que actúa como memoria, un cabezal capaz de leer y escribir símbolos en la cinta y moverla de celda en celda a derecha e izquierda, un registro de estado, y una tabla finita de instrucciones o tabla de acción.

La máquina de Turing es considerada un autómata con la capacidad de reconocer lenguajes formales de acuerdo a la jerarquía de Chomsky, razón por la cual es muy superior a otros autómatas como el autómata con pila o el autómata finito.

Existen diversos tipos de máquinas de Turing: con movimiento stay o “esperar”, con cinta infinita a ambos lados, con cinta multipista, multicinta, determinista y no determinista, la Máquina de Turing Cuántica. En resumen, una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT, ambos formados por un código binario de unos y ceros.

6.3 lenguajes aceptados por la maquina de turing

Máquina de Turing multicinta determinística

Este modelo es una extensión del modelo anterior de 1 cinta a k_cintas de entrada, y k cabezas de 

lectura/escritura. Una transición de estados depende del símbolo que se lee en cada una de las 

cintas, luego la máquina cambia de estado, reescribe un nuevo símbolo en cada cinta de entrada y 

mueve la cabeza de lectura/escritura de cada cinta en forma independiente. 

La ventaja es que para reconocer ciertos lenguajes es más fácil hacer el diseño de la MT con 

k_cintas de entrada. 

En general se suele utilizar 1 cinta que contiene los símbolos de entrada, cintas intermedias para 

realizar cálculos auxiliares y una cinta de salida para el caso particular de una máquina de Turing 

traductora. 

MTM= < E, A, C, δ, e0, B, F > 

donde E, A, C, e0, B, F, se definen como antes 

y δ: E x C k→ E x (C x {D,I,N}) k donde {D,I,N} son posibles movimientos de la cabeza de 

lectura/escritura. 

Todo lo que se hace en multicinta puede realizarse con el modelo de 1 cinta. Es decir, que son 

modelos equivalentes ya que pueden reconocer los mismos lenguajes. 

Máquina de Turing no determinística

Al igual que con los AFND y APND cuando se diseña una MTND esto significa que en un cierto 

punto puedo tener varios cursos de acción, entonces: 

MTND=< E, A, C, δ, e0, B, F > 

donde E, A, C, e0, B, F, se definen como antes y 

δ: E x C k→ Pf (E x (C x {D,I,N}) k ) Pf denota un subconjunto finito de E x (C x {D,I,N})k 

Es decir: 

δ( ei

, a1, a2,…,ak) ={(ej , (Y1, d1 ) (Y2,d2 ) …. (Yk,dk )); (en , (Y1’,d1’ ) (Y2’,d2’ )…(Yk’,dk ’))...}

donde ei

, ej, en ∈ E ; a1, a2,…,ak,Y1,Y2,. Yk,Y1’,Y2’…Yk’∈ C; d1 ,d2 …dk ,d1’,d2’,…dk ’∈{D, I, N} 

Una Máquina de Turing no determinística acepta una cadena si cualquier secuencia de transiciones 

conduce a un estado final. Como con los autómatas finitos, la adición de no 

determinismo a las Máquinas de Turing no permite que la máquina acepte nuevos lenguajes. Es 

decir, existe una equivalencia entre MTD y MTND, para los conjuntos de lenguajes que aceptan. 

Sin embargo el tiempo de ejecución de las MTND, es más costoso que el caso de MTD