4.2 CONSTRUCCIÓN MODULAR DE UNA MÁQUINA DE TURING

Mediante esta Técnica se pueden desarrollar maquinas de Turing complejas a partir de Bloques y apartir de maquinas mas pequeñas mediante diagramas de transiciones.

COMBINACIÓN DE MAQUINAS DE TURING

La construcción de maquinas de Turing se lleva a cavo 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.

Suponga que tenemos dos máquinas de Turing M1 y M2, con diagramas de tranciciones T1 y T2, respectivamente, y simbolos de cinta del conjunto . Si queremos desarrollar un diagrama de transiciones para otra máquina que simule las actividades de M1 seguidas por las de M2, bastaría con eliminar la designación de parada del estado de parada T1 y la caracteristica de inicio del estado inicial de T2, y luego dibujar un arco con etiqueta x/x para cada x en , del antiguo estado d eparada de T1 al antiguo estado inicial de T2.

(Este aprtado puede ser el deceado pero tiene desventajas)... Supongamos que queremos que la amquina compuesta se detenga después de simular M1, a menos que el símbolo actual, al llegar al estado de parada, sea z, en cuyo caso nos gustaria que la nueva máquina simulara las acciones de M2; o supongamos que necesitamos combinar 3 diagramas y controlar el paso de uno aotro dependiendo del valor del símbolo actual al llegar a cada uno de los antiguos estados de parada. En este caso re requiere un enlace mas complicado.

Si necesitamos combinar los diagramas de transiciones de varias máquinas que simule alguna combinación de las máquinas originales. Seguimos los siguientes pasos:

1. 
   
   Elimine la característica de inicio de los estados iniciales de todas las máquinas, excepto la de aquél donde iniciará la máquina compuesta.


2. 
   
   Elimine la caracyerística de detención de los estados de parada de todas las máquinas e introduzca un nuevo estado de parada que no 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 , dibuje un arco de la siguiente forma:

a).- Si la máquina compuesta debe detenerse al llegar a p con el símbolo actual x, dibuje un arco con etiqueta x/x de p al nuevo estado de parada.

b).- Si al llegar al estado p con el símbolo actual x, la máquina compuesta debe transferir el control a la máquina , dibuje entonces un arco con etiqueta x/z de p al estado q de M, donde .

Mueve la cabeza una celda hacia la derecha.

Encuentra la primera x ala derecha de la celda actual

Encuentra la primera y a la derecha de la celda actual

Encuentra la segunda ocurrencia del símbolo distinto de espacio en blanco que está a la derecha de la posición inicial de la cabeza

La Maquina compuesta de las figuras anteriores podria resumirse con el diagrama compuesto:

donde el nodo A representa la máquina que mueve su cabeza una celda a la derecha, B la máquina que busca una x y C la máquina que busca una y.

• Ejemplo de Maquinas de Turing compuesta:

• Otra abreviatura que utilizaremos consiste en aplicar la notacion:

........INTEGRANTES DEL EQUIPO.....

Martinez Martinez Tomas Alejandro

Marquez del Angel Yaznhara

Perdomo Sanchez Lizeth

Cruz Hernandez Ivan