Page 91 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

91

ENTREGA X

MÁQUINAS DE TURING.

Son igualmente autómatas, máquinas conceptuales más generales, con el mismo poder
computacional en el contexto de reconocimiento de lenguajes.

Estas máquinas autómatas que ahora se conoce como máquina de Turing, fue presentada por Alan
m. Turing en 1936. Para este tiempo el interés de Turing era estudiar los procesos algorítmicos
utilizando un modelo computacional. Las máquinas de Turing se asemejan a los autómatas finitos
en que constan de un mecanismo de control y un flujo de entrada que se concibe como cinta; la
diferencia es que las máquinas de Turing pueden mover sus cabezas de lectura hacia adelante y
hacia atrás y pueden leer o escribir en la cinta, cosa que potencia en gran medida la capacidad de
las máquinas.

Propiedades básicas de las máquinas de Turing:

 La máquina de Turing contiene un mecanismo de control que en cualquier momento puede
encontrarse en uno de entre un número finito de estados. Uno de estos estados se denomina
estado inicial y representa el estado en el cual la máquina comienza los cálculos. Otro de
los estados se conoce como “estado de parada”; una vez que la máquina llega a ese estado
terminan todos los cálculos. De esta manera, el estado de parada de una máquina de
Turing difiere de los estados de aceptación de los autómatas finitos y de pila en que éstos
pueden continuar sus cálculos después de llegar a un estado de aceptación, mientras que
una máquina de Turing debe detenerse en el momento en que llegue a su estado de parada.
Así las cosas, el estado inicial de una máquina de Turing no puede ser a la vez el estado
de parada; por lo tanto, toda máquina de Turing debe tener cuando menos 2 estados.

 Una diferencia más importante entre una máquina de Turing y los autómatas vistos
anteriormente es que las máquinas de Turing pueden leer y escribir en su medio de entrada
(cinta). Dicho de otra forma, la máquina de Turing viene equipada con una cabeza de
lectura/escritura que permite leer o escribir sobre la cinta. Si esto es así la máquina de
Turing puede usar la cinta como dispositivo de almacenamiento auxiliar, con este
almacenamiento la máquina no se limita a insertar y extraer, sino que puede rastrear los
datos de la cinta y modificar las celdas que desee sin alterar las demás.

 La máquina de Turing tiene un alfabeto finito de entrada o alfabeto de la máquina, un
conjunto posiblemente mayor también finito de símbolos llamado símbolos de cinta, que
la maquina puede leer y escribir (parecido a los símbolos de entrada versus símbolos de
pila del autómata de pila). Los símbolos de cinta de una máquina de Turing pueden incluir
marcas especiales que no sean símbolos del alfabeto de la máquina. El espacio en blanco
es un símbolo que cae en esta categoría, se trata de un símbolo que se supone esta en
cualquier celda de la cinta que no esté ocupada. Si la máquina de Turing tiene que borrar
un símbolo de la cinta, lo hará escribiendo un espacio en blanco en ella, por lo que es un
símbolo de cinta, pero no del alfabeto de entrada.

 Las acciones específicas que puede realizar una máquina de Turing son operaciones de
lectura / escritura y de movimiento. La operación de escritura consiste en reemplazar un
símbolo en la cinta con otro símbolo y luego cambiar a un nuevo estado (el cual puede ser
el mismo en donde se encontraba antes). La operación de movimiento comprende mover