Configuración de
una Máquina de Turing
Máquina de Turing
multicinta determinística
Este modelo es una extensión
del modelo anterior de 1 cinta a k_cintas de entrada, y k cabezas lectoras.
Una transición de estados depende del símbolo que se lee
en cada una de las cintas, luego la máquina cambia de estado, reescribe
un nuevo símbolo en cada cinta de entrada y mueve la cabeza lectora
de cada cinta en forma independiente.
La ventaja es que para reconocer
ciertos lenguajes es más fácil hacer el diseño de
la MT con k_cintas de entrada.
En general se suele utilizar
1 cinta que contiene los símbolos de entrada, cintas intermedias
para realizar cálculos auxiliares y una cinta de salida para el
caso particular de una máquina de Turing traductora.
Todo lo que se hace en multicinta
puede realizarse con el modelo de 1 cinta. Es decir, que son modelos equivalentes
ya que pueden reconocer los mismos lenguajes.
Máquina
de Turing no determinística
Al igual que con los AFND
y APND cuando se diseña una MTND esto significa que en un cierto
punto puedo tener varios cursos de acción, entonces:
Una máquina de Turing
no determinística acepta una cadena si cualquier secuencia de transiciones
conduce a un estado final. Como con los autómatas finitos, la adición
de no determinismo a las Máquinas de Turing no permite que la máquina
acepte nuevos lenguajes. Es decir, existe una equivalencia entre MTD y
MTND, para los conjuntos de lenguajes que reconocen.
Sin embargo el tiempo de
ejecución de las MTND, es más costoso que el caso de MTD.
Lenguaje aceptado por
la Máquina de Turing
Autómata linealmente
acotado
Es una máquina de
Turing particular. La restricción sobre el modelo general de Máquina
de Turing es que las transiciones se realizan sobre una cantidad de casilleros
acotada. Es decir, en vez de tener una cinta de entrada infinita sobre
la cual calcular, se restringe a una porción entre un casillero
que contiene un símbolo de inicio #, y un símbolo final $,
y se garantiza que las transiciones se van a realizar dentro de este conjunto
de casilleros en la cinta de entrada.
Para el caso del modelo
multicinta se extiende para cada cinta la condición de acotar el
espacio de trabajo.
Una máquina de Turing
con esta restricción ALA, permite reconocer un tipo de lenguajes
en particular que se denominan Lenguajes Sensibles al Contexto.