Automatas

CIENCIAS DE LA COMPUTACION I

2008

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 de lectura/escritura que lee un solo símbolo de la cinta por vez. La cinta tieneuna 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 de más a la izquierda (n ≥ 0) contienen una cadena ω, siendo |ω|=n. ω está definida sobre un subconjunto de C, llamado alfabeto de entrada A. Las infinitas celdas restantes contienen un símbolo blanco B, el cual esun 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 de lectura/escritura 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 queincluyen todo el conjunto de lenguajes que describen procedimientos computacionales. Todo procedimiento computacional puede ser modelado con una Máquina de Turing. Formalmente se define una máquina de Turing como una 7-upla MT= donde: E: Conjunto finito de estados A: El alfabeto sobre el cual está definido el lenguaje que pretendemos reconocer. A⊆ C C: Alfabeto de la cinta. C=A ∪ {B} ∪Símbolos_Auxiliares A ∩ Símbolos_Auxiliares = ∅ e0: estado inicial B: símbolo blanco. B ∉ A y B ∈ C δ: E x C→ E x C x {D, I, N} donde {D, I, N} son posibles movimientos de la cabeza de lectura/escritura, Derecha, Izquierda o No hay movimiento respectivamente. Sin embargo, δ puede estar indefinida para algunos argumentos, por ejemplo no se permiten movimientos a izquierda de la celda de inicio de la cinta. F:Conjunto de estados finales. F⊆ E Los tipos de transiciones de estados de una MT determinística se definen como: 1) δ( ei , xk) =( ej , Y, D) 2) δ( ei , xk) =( ej , Y, I) 3) δ( ei , xk) =( ej , Y, N) donde xk, Y ∈ C; ei , ej ∈ E. Configuración de una Máquina de Turing Si ei es el estado actual, las cadenas α1 y α2 están ubicadas en las celdas de la cinta de entrada (α1 precede a α2) y la cabeza delectura/escritura esta apuntando al primer símbolo de α2, se define una configuración de MT como: α1 ei α2 ei ∈ E; α1 , α2 ∈ C* Luego, se define una relación de transición | en el espacio de posibles configuraciones de la MT, como: α1 ,α2 ,β1,β2 ∈ C* ; ei ,ej ∈E α1ei α2 | β1 ej β2

Supongamos la siguiente configuración, estado actual ei ; α1= x1 x2 …. xk-1; α2 = xk xk+1 ….xn donde x1,…,xn ∈C; ei ∈ E. La cabeza de lectura/escritura apunta al símbolo xk.

CIENCIAS DE LA COMPUTACION I
(1)

2008

x1 x2 ... xk-1 ei xk xk+1 ...xn | x1 x2 … xk-1 Y ej xk+1 ….xn Si existe la transición tipo(1), la MT pasa al estado ej , avanza la cabeza de lectura/escritura y reemplaza el símbolo xk por Y. x1 x2 ... xk-1 ei xk xk+1 ...xn | x1 x2 ...ej xk-1 Y xk+1 ...xn
(2)

-Si existe latransición tipo(2), la MT pasa al estado ej , retrocede la cabeza de lectura/escritura y reemplaza el símbolo xk por Y. -Si existe la transición tipo(3), la MT pasa al estado ej , no avanza la cabeza de lectura/escritura y reemplaza el símbolo xk por Y.

x1 x2 ... xk-1 ei xk xk+1 ...xn | x1 x2 ... xk-1 ej Y xk+1 ….xn

(3)

Máquina de Turing multicinta determinística Este modelo es una extensión delmodelo anterior de 1 cinta a k_cintas de entrada, y k cabezas de lectura/escritura. 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 de lectura/escritura de cada cinta en forma independiente. La ventaja es que para reconocer ciertos lenguajes es más fácil...