Máquinas de Turing

Las máquinas de Turing, así como los AF y los AP se utilizan para aceptar cadenas de un lenguaje definidas sobre un alfabeto A. El modelo básico de máquina de Turing, tiene un mecanismo de control, una cinta de entrada que se divide en celdas, y una cabeza lectora que lee un solo símbolo de la cinta por vez. La cinta tiene una celda de inicio de más a la izquierda, pero es infinita a derecha. Cada celda de la cinta puede contener exactamente un símbolo del alfabeto de la cinta C. Inicialmente, las n celdas más a la izquierda contienen una cadena , siendo |  | = n, definida sobre un subconjunto de C, llamado alfabeto de entrada A. Las infinitas celdas restantes contienen un símbolo blanco B, el cual es un símbolo especial del alfabeto C.
La diferencia fundamental con el autómata de pila y el autómata finito, es que se puede leer un símbolo y reescribirlo por otro símbolo, y además la cabeza lectora puede desplazarse a la izquierda, a la derecha o quedarse en el mismo lugar.
El modelo general de MT permite aceptar los lenguajes recursivos enumerables o estructurados por frases que incluyen todo el conjunto de lenguajes que describen procedimientos computacionales. Todo procedimiento computacional puede ser modelado con una Máquina de Turing.


 

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.