Page 97 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

97

∆/R

△/R
X/X △/△
X/R X/X
Y/R
X/X
Y/R Y/Y
X/R
X/R
Y/R T △/△
△/R
Y/R
△/R △/△
△/R X/X

X/R Y/Y

Y/R Y/Y

X/R

Y esta sería una máquina de Turing construida de MT más pequeñas, o sea una máquina de Turing
compuesta.

Todavía se puede hacer una abstracción más simple de esto, si hacemos una abstracción de cada
máquina simple y sabemos muy bien qué hace, no es necesario implicar el cómo lo hace en el
esquema que se presente, solo será necesario enlazar adecuadamente cada MT simple y ubicar la
transición correcta entre máquinas; y dejamos de lado todas las transiciones excesivas que se
muestran en el anterior diagrama.

Si hacemos esto podemos entonces considerar cada máquina simple como un nodo, con flechas
entre los nodos las transiciones entre bloques. Estas flechas se etiquetan de acuerdo 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 tiene una etiqueta x, entonces la ejecución se transferirá a la máquina b si a llega a su
antiguo estado de parada con una x en la celda actual. Así las cosas, el diagrama anterior,
fácilmente pueden ser:

X
M2

M1
Y M3

Existen varias nomenclaturas para establecer diagramas compuestos de máquinas de Turing. Una
estrategia que se usa es reemplazar varias flechas que tienen un mismo destino y una misma fuente
por una sola flecha rotulada con una lista de símbolo, o con una negación como esta ¬X, se
interpretaría así: todos los símbolos actuales distintos de X. Otra abreviatura es utilizar una flecha
sin etiquetas para representar que una transición se dará sin importar el símbolo o valor de la celda
actual, igual esto se puede representar también colocando un nodo al lado de otro: