Page 23 - Revista FIUDE 2014

Al momento de comenzar a procesar una cadena, la cinta contiene como información sólo la cadena que
se va a procesar y el resto de la cinta hacia la derecha está en blanco.
Si la máquina precisa guardar información, usa la cinta como medio de persistencia.
Para leer la información que guardó en la cinta, la máquina puede mover el cabezal hacia adelante o
atrás.
La máquina continúa computando hasta que decide aceptar o rechazar la cadena que venía inicialmente
escrita en la cinta. La salida de la máquina (aceptación o rechazo de la cadena inicial) se obtiene al entrar
en determinados estados de aceptación o rechazo.
Si la máquina al intentar procesar una cadena determinada no llega a entrar a un estado de aceptación o
rechazo y queda eternamente dando vueltas en sus estados sin parar, se rechazará la cadena.
A diferencia de los autómatas finitos, las máquinas de Turing pueden escribir y leer en la cinta que tienen
mientras que los autómatas finitos no tienen cinta ni ningún otro mecanismo de memoria auxiliar.
Además a diferencia de los autómatas finitos, los estados de aceptación o rechazo toman efecto
definitivamente al momento de visitarlos y ponen un alto a la ejecución, dictaminando en ese momento
que la cadena que se está procesando es aceptada o rechazada.
Un ejemplo de Máquina de Turing, es la máquina M que permite reconocer las cadenas del lenguaje L
4
4
mencionado anteriormente L = { 0#0, 1#1, 00#00, 01#01, 10#10, 11#11, … }.
4
El objetivo de esta máquina es determinar si la cadena de entrada consiste en dos subcadenas idénticas
separadas por el símbolo #.
La estrategia que utilizará la máquina será mover el cabezal haciendo zig-zag hacia los lugares
correspondientes en los dos lados del símbolo # e ir determinando si símbolo por símbolo éstos se
corresponden. Además se irán escribiendo marcas en forma del símbolo x, en la cinta para ir recordando
qué partes de la cadena ya fueron visitadas.
La máquina realizará múltiples pasadas sobre la cadena de entrada usando su cabezal lector-escritor y en
cada pasada, comparará un símbolo a la izquierda del #, con su correspondiente a la derecha del #.
Para llevar registro de qué símbolos a ambos lados del # ya fueron visitados, la máquina los irá tachando
a medida que los vaya examinando.
El siguiente diagrama de estados muestra cómo quedaría diseñada la máquina de Turing M que aceptaría
4
solamente aquellas cadenas del lenguaje L ,
4

Tiene los siguientes estados abstractos:
S, T, U, V, W, X, Y, Z, FIN.
S es el único estado inicial del autómata.
FIN es el estado de aceptación (sólo
puede haber uno).
El estado especial de RECHAZO no se
incluye en el diagrama para preservar la
legibilidad del mismo.

Revista de la Facultad de Ingeniería