Page 95 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

95

CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING.

Se pueden construir máquinas de Turing complejas a partir de bloques elementales de MT. Dicho
de otra forma, podemos conceptuar ciertas tareas y representarlas en MT y luego a través de estas
implementaciones simples, unirlas y producir otras MT más complejas.
Esto se puede comprender como los módulos de programas que se elaboran y luego se unen para
formar una pieza de código o aplicación más compleja.

O sea, pequeños programas que, al unirlos, creamos grandes sistemas de software. Para hacer
esto, es útil representar los programas de las máquinas de Turing por medio de diagramas de
transiciones y combinarlas de manera apropiada.

Supongamos que tenemos 2 MT a saber M1 y M2 con diagramas de transición T1 y T2
respectivamente y símbolos de cinta del conjunto . Si se quiere desarrollar un diagrama de
transición para otra máquina que simule las actividades de m1 seguidas por M2, basta con eliminar
la designación de parada del estado de parada de T1 y las características de inicio del estado inicial
de T2, y luego dibujar un arco con etiqueta X/X para cada X en , del antiguo estado de parada
de T1 al antiguo estado inicial T2.

Este enfoque muestra lo que se desea hacer y debe concretarse siguiendo los siguientes pasos:

 Eliminar las características de inicio de los estados iniciales de todas las MT
simples, excepto la de aquél donde iniciará la máquina compuesta.

 Eliminar las características de detención de los estados de parada de todas las MT
simples e introducir 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 , dibujar un arco
así:

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

 Sí al llegar al estado P con el símbolo actual X, la máquina compuesta debe
transferir el control a la máquina M = (S, ∑, , , H), dibuje entonces un
0
arco con etiqueta X/Z de P al estado Q de M, donde ( ,X) = (Q,Z).
0

Veamos los siguientes bloques de construcción:

X/R
Y/R
△/R

M1: mueve la cabeza de lectura-escritura una celda a la derecha si lee X, Y, o espacio en blanco.