Maquina De Turing

INTRODUCCION

Mediante la elaboración del presente informe, se pretende establecer un material de apoyo por el cual se logre asimilar los conceptos y fundamentos de la tercera unidad del módulo del curso Autómatas y Lenguajes Formales, referente a la máquina de Turing y las Funciones Recursivas.

Cabe destacar que se contó con una buena participación de los integrantes del grupo colaborativopara consolidar este trabajo donde se plasman los aportes más importantes que se realizaron.

DESARROLLO DE LAS ACTIVIDADES

1. Mediante un grafo explique la construcción modular de las Maquinas de Turing y describa cada uno de sus elementos.

Mediante esta técnica pueden desarrollarse máquinas de Turing complejas a partir de bloques de elementales a partir de máquinas más pequeñasmediaste diagramas de transiciones.

La construcción de máquinas 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

Se eliminan las características de inicio de los estados iniciales de las máquinas, exceptola de aquel donde iniciara la maquina compuesta.

Se eliminan las características de detención de los estados de parada de todas las máquinas y se introduce un nuevo estado de parada que no se encuentre en ninguno
de los diagramas que se combinan.

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 máquina deTuring 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 dejo la primera máquina de Turing, y la cabeza de lectura/escritura de la segunda se situara, al comienzo de la ejecución, sobre la celda de la cinta sobre la que termino la primera.

Máquina de Turing Compuesta.

2. Diseñe una MT que reconozca {0n1n: n ≥ 1}

• Cambie un 0 por una x (explique qué pasa con la maquina).
• Cambie un 1 por una y (explique quépasa con la maquina).
• Identifique en que momento la máquina de Turing se detiene.
• Calcule la función δ
• Grafíquela e identifique sus elementos.
• Identifique la función de transición.

Cambie un 0 por una Y (explique que pasa con la maquina).

Cuando se cambia un 0 por una X la cabeza se cambia de posición rumbo a la derecha hasta llegar y encontrar el primer 1 lo que hace que lamaquina se mueva
a la izquierda de la cinta.

Cambie un 1 por una Y (explique que pasa con la maquina).

Cuando se cambia un 1 por una Y la cabeza se cambia de posición rumbo a la
derecha hasta que llega y encuentra el primer cero, lo que hace que la maquina
avance a la derecha de la cinta.

Identifique en que momento la maquina de Turing se detiene.

La máquina de Turing se detiene cuandola maquina cambio y paso por encima de todos las entradas Y, y ya todos los 1 se hayan cambiado y solo quedan Y’s y X’s en la cinta.

Calcule la función 

Grafíquela e identifique sus elementos.

3. Construya una MT que acepte el Lenguaje

L = {abc: i ≥ 0} sobre Σ = {a,b,c}
Máquina de Turing funcionando. Verificación de sintaxis de entrada:

a-Se cambia la a por una x moviéndose a laderecha. (Explique qué pasa con la maquina).

R// Se cambia la a por una X y se mueve hacia la derecha pasando por encima de todas las a0s e Y s, hasta llegar a la primera b, cambia la primera b por una y, se mueve a la derecha pasando por encima de las bs y Zs y luego encuentra la primera c y la cambia por Z y se mueve a la izquierda.

b- Luego se mueve a la izquierda pasando por encima de...