Combinacion de maquinas de turing

Solo disponible en BuenasTareas
  • Páginas : 3 (532 palabras )
  • Descarga(s) : 31
  • Publicado : 29 de junio de 2010
Leer documento completo
Vista previa del texto
COMBINACIÓN DE MÁQUINAS DE TURING
Podemos 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 cintacuando 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 lectura / escritura de la segunda se situará, al comienzo dela ejecución, sobre la celda de la cinta sobre la que terminó la primera.
Para ello se deberán seguir los siguientes pasos:
1. Eliminar la característica inicial de los estados iniciales detodas las máquinas, excepto la de aquel donde se iniciará la máquina compuesta.

2. Eliminar todas las características de detención de los estados de parada de todas las máquinas e introducir unnuevo estado de parada que no pertenezca a ninguno de los diagramas que se combinan.

3. Para cada uno de los antiguos estados de parada p y cada x en G, dibujar un arco de la siguiente forma:a) Si la máquina compuesta debe detenerse al llegar a una p con el símbolo actual x, dibujar un arco con la etiqueta x/x de p al nuevo estado de parada.

b) Si al llegar al estado p con elsímbolo actual x, la máquina compuesta debe transferir el control a la máquina M=(S, S, G, d, i, h), dibujar un arco con etiqueta x/z de p al estado q de M donde d(i, x)=(q, z).
En las grandes aplicacioneses conveniente evitar los detalles interiores de los bloques de construcción, conociendo la tarea de las máquinas más pequeñas se puede obviar como se lleva a cabo la tarea específica y dedicarse sóloal enlace entre ellas. Por ello se evita el uso de diagramas de transiciones detallados y se usa diagramas compuestos. En los que, cada uno de los bloques de construcción se representa como un nodo,las transiciones entre bloques se indican con flechas que se etiquetan con el valor que debe aparecer en la celda actual para que se recorra la flecha. Es decir, si una flecha del nodo A al nodo B...
tracking img