Page 92 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

92

la cabeza una celda a la derecha o a la izquierda, y luego pasar a un nuevo estado (que una
vez más, puede ser el mismo que el de partida).

 La acción que se ejecutará en un momento dado dependerá del símbolo actual, es decir el
símbolo que esta visible para la cabeza de lectura y del estado actual del mecanismo de
control de la máquina.

La semántica de la representación funcional de la máquina de Turing es así:

A- Δ (P,X) = (Q,Y) que se lee así: si el estado actual es P y el símbolo actual es X
reemplazar la X con el símbolo Y, y pasar del estado P al estado Q.

B- Δ (P,X) = (Q,L) que se lee así: si el estado actual es P y el símbolo actual es X mover
la cabeza una celda a la izquierda y pasar al estado Q.

C- Δ (P,X) = (Q,R) se lee así: si el estado actual es P y el símbolo actual es X mover la
cabeza una celda a la derecha, y pasar al estado Q.

Obsérvese que, al describir con una función las transiciones de una máquina de Turing, la
máquina es determinista, porque existe una, y solo una transición asociada a cada par
estado-símbolo, donde el estado no es el de detención.

En una operación normal de la máquina de Turing se ejecutan transiciones repetidas hasta
llegar al estado de parada. Puede ocurrir una anomalía en su funcionamiento y es que la
cabeza lectura/escritura de la máquina puede rebasar el extremo izquierdo de la cinta. En
este caso, la maquina abandonará los cálculos y decimos que la ejecución de la maquina
sufrió una terminación anormal.

Esquema de una máquina de Turing

CINTA

CABEZA DE ESCRITURA
LECTURA LA CABEZA SE MUEVE EN
AMBAS
DIRECCIONES
INDICADOR DE
ESTADO

Al igual que con otros autómatas se puede realizar esquemas que representan las distintas
transiciones de una MT. Igual que con los otros autómatas se representan los estados con círculos,
identificando el estado de inicio y parada con un apuntador, y un doble círculo respectivamente,
y los arcos que conectan los estados. Cada arco se etiqueta con un par de símbolos separados por
una diagonal. El primer símbolo del par representa el símbolo de la cinta que debe existir en la
celda actual para que la transición sea aplicable, el segundo símbolo es el que se escribirá en la