4. Representación gráfica de una MT

En forma similar a las demás máquinas abstractas, una Máquina de Turing puede representarse gráficamente a través de los llamados Diagramas finitos o de transición. Un diagrama de transición está formado por un conjunto de nodos que corresponden a los estados de la MT. La transición δ(q,a)=(p,b,D)se representa así:

Según esto, tenemos para un diagrama de transición los siguientes elementos:

 

• Estados, representados por vértices: q, p
• El estado inicial de la máquina es aquel representado por una arista sin origen. El estado final o de aceptación está representado por una doble arista. 
• Transición entre estados, representada por una arista dirigida: (a/b, D): el primer término (a) indica el símbolo leído en el cabezal; el segundo término (b) indica el símbolo que el cabezal va a escribir. El último término es la indicación del siguiente movimiento del cabezal: derecha (D o R, por la palabra inglesa Right) o izquierda (I o L, de Left).

 

Para explicar el reconocimiento de la cadena por una MT se presenta el siguiente ejemplo. Sea M una MT con la siguiente descripción M=(Q,Σ,Γ,q_0,q_1,B,δ), donde Q={q_0,q_1 }, Σ={a,b}, y B indica el espacio en blanco.

 

Sus transiciones están dadas por:

 

 

 Esta MT reconoce a* sobre el alfabeto Σ. Sea la cadena w = aaa.

 

(1) El cabezal, representado con una flecha roja, lee el primer símbolo “a”. La transición dice que al estar en q0 y leer una “a”, se sobrescribe “a” y el cabezal se mueve a la derecha:

(2) A continuación, el estado sigue siendo q0, y el cabezal lee el segundo símbolo “a”. Nuevamente, queda en q0, sobrescribe una “a”, y el cabezal se mueve a la derecha.

(3) El proceso se repite para el último símbolo “a”

(4) En este instante, el cabezal lee un espacio en blanco, B. Según las transiciones de la MT, en el estado q0 un espacio B cambia el estado de la máquina a q1, mantiene B y mueve el cabezal a la derecha. El estado q1 es final de aceptación, por lo que la cadena es aceptada.