Máquina de Turing y Autómata Linealmente Acotado

Máquina de Turing

La máquina de Turing es un dispositivo mecánico que cuenta con una cinta infinita dividida celdas, y un cabezal de lectura/escritura que se mueve sobre la cinta y se desplaza por una celda a la vez y una unidad de control que puede cambiar de estado según el símbolo leído por el cabezal.

En la cinta hay infinitos segmentos donde se encuentra un carácter especial, que es el carácter blanco, excepto por los segmentos finitos donde se encuentran símbolos pertenecientes al alfabeto de entrada.

Un movimiento, en la máquina de Turing depende del símbolo leído por el cabezal y el estado actual en el que se encuentra la máquina, el resultado puede ser:

• Cambio de estado
• Imprime un símbolo en la cinta reemplazando al símbolo leído
• Se mueve la cabeza de la cinta a la izquierda, derecha o no hay nada

Pueden darse los 3 fenómenos anteriores, juntos o separados. Su nombre se debe a Alan Turing

Formalmente se define como una séptupla {V,∑,Q,q₀,f,q,b} donde:

• V es un conjunto finito no vacío de símbolo de la cinta
• ∑ es un alfabeto de entrada, donde ∑ є V
• Q es un conjunto de estados
• q₀ es el estado inicial
• f es la función de transición f:QxVàQxVx{I,D,P} donde I es izquierda, D es derecha y P es parada
• b es un carácter especial que representa al espacio en blanco, donde b єV pero b NOє ∑

Autómata linealmente acotado

Es una máquina de Turing no determinista que satisface, donde la cinta es finita, está acotada por ambos estados para esto se utiliza a caracteres especiales que permiten delimitar el principio y el final de la cinta. Además la cabeza lectora no podrá ir más a la izquierda que el símbolo que está en la izquierda, ni más.

Sirve para reconocer los lenguajes dependientes de contexto.

Formalmente se la define como ALA (autómata lineal acotado)= {V,∑,b,Q,q₀,q,f,<,>} donde:

• V es el conjunto finito no vacío del alfabeto de la cinta
• ∑ es el alfabeto de entrada, donde ∑єV
• b es un carácter especial, donde bєV, bNOє∑
• Q es el conjunto de estados finito no vacíos
• q₀ es el estado inicial
• q es el conjunto de estados finales
• f es la función de transición
• < y=""> símbolo de comienzo y fin de cinta respectiva