Maquina De Turing

MAQUINA DE TURING

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.

Una máquina de Turing 4 es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, \ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

MODELO BASICO

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 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 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 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 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 que incluyen 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= <E, A, C, δ, e0, B, F> 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

...