7. Mediante un grafo explique la construcción modular de las Máquinas de Turing y describa cada uno de sus elementos.

El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas más pequeñas, mediante 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 

a)      Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.

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

c)      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 máquina 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.

Maquinas de Turing Compuesta.