Maquina de turing

CIENCIAS DE LA COMPUTACION I 2009
MÁQUINAS DE TURING

Las máquinas de Turing, así como los AF y los AP se utilizan para aceptar cadenas de un lenguajedefinidas sobre un alfabeto A. El modelobá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 tiene unacelda 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 laizquierda (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 es unsí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 delectura/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 deTuring 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...