Page 102 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

102

ENTREGA XI

MÁQUINAS DE TURING.

Máquinas de Turing de cintas múltiples:

Se les llama máquinas de Turing de k cintas donde k representa un entero positivo que indica el
número de cintas. Cada cinta tiene igualmente un extremo izquierdo y uno derecho y el acceso a
cada una se logra a través de una cabeza separada de lectura/escritura. La transición que se ejecute
en un instante determinado dependerá de la colección de símbolos presentes para estas cabezas,
junto con el estado actual de la máquina. La acción de una sola transición afecta solo a una de las
cintas de la máquina, esta acción puede ser escribir en la celda actual de esa cinta, mover la cabeza
correspondiente a una celda a la izquierda o mover una celda a la derecha.

Para evaluar la aceptación de una cadena con una máquina de k cintas, inicia con la máquina en
su estado inicial leyendo la primera cinta en su extremo izquierdo, a la vez que las otras cintas
están en blanco y todas las cabezas deben estar en el extremo izquierdo de sus cintas. La cadena
es aceptada si a partir de esta configuración inicial la maquina se detiene en su estado de parada.

Una máquina de Turing con varias cintas no tiene mayor potencial que una de una cinta, lo que sí
es que pude ser más funcional, aunque no más potente.

Máquinas de Turing no deterministas:

Estas máquinas son similares a una máquina de Turing tradicional o determinista, lo único que
puede que no se encuentre completamente definida, o lo que sería más importante que tenga más
de una sola transición definida para un mismo par estado-símbolo actual, pudiendo aplicarse más
de una transición. Si este es el caso, la maquina optaría por una elección no determinista y
proseguiría con sus cálculos mediante la ejecución de alguna de las opciones aplicables. Si por el
contrario, si se llega a un estado símbolo-estado actual, para el cual no existe una transición
aplicable, la máquina abandonaría los cálculos.

Así las cosas decimos que una maquina no determinista m acepta una cadena w si es posible que
m llegue a su estado de parada después de iniciar sus cálculos con la entrada de símbolos de w.
Lo que quiere decir, que si la maquina no es determinista, puede elegir una opción inadecuada en
un estado cualquiera y no llegar a su estado de parada, no porque la cadena en realidad no fuera
válida, sino por una “mala” decisión de la máquina. Por tanto, una cadena w se encuentra en L
(M) si y solo si m dispone de opciones que le permitan alcanzar el estado de parada al recibir W.

Adicional la máquina de Turing no determinista es una generalización de la MT tradicional, y
puede aceptar todo lenguaje que acepta una maquina tradicional. Las máquinas de Turing no
deterministas son incapaces de aceptar más lenguajes que las determinísticas, en consecuencia, la
introducción de no determinismo en MT no aumenta el potencial de reconocimiento de lenguajes
de las MT. O sea sucede igual que con los autómatas finitos deterministas.

Máquinas de Turing universales:

Se denomina así a una MT que recibe en su cinta una descripción codificada de otra máquina de
Turing y produce como resultado de su ejecución, el mismo resultado que produciría la MT
descrita en la cinta.