Automatas

4.- VARIANTES DE UNA MAQUINA DE TURING
Una máquina de Turing puede hacer cualquier cosa que pueda hacer una computadora real y aún cuando una MT no puede resolver ciertos problemas, estos problemas están más allá del los límites teóricos de la computación; es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia(generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles. La MT consta de un cabezal lector/escritor y una cinta infinita enla que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
Avanzar el cabezal lector/escritor para la derecha.
Avanzar el cabezal lector/escritor para la izquierda.
Una máquina de Turing es una tupla de 7 elementos (Q, Σ, Γ, δ, qo, qa(aceptar), qr (rechazar)), donde:
Q, Σ, Γ son conjuntosfinitos.
1. Q es el conjunto de estados
2. Σ es el alfabeto de entrada
3. Γ es el alfabeto de la cinta
4. δ: Q x Γ → Q x Γ x { L, R }
5. qo Є Q es el estado inicial
6. qa Є Q es el estado de aceptación
7. qr Є Q es el estado de rechazo, donde qa ≠ qr.
Según va computando una MT, ocurren cambios en el estado actual, el contenido de la cinta y la posición de la cabeza de la cinta. Una combinaciónde estos tres elementos se llama una configuración de la máquina de Turing. La idea subyacente en el concepto de máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde sepueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumérables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como elautómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
Existen muchas alternativas de la máquina de Turing, incluyendo cintas múltiples o indeterminismo. Estas son llamadas variantes del modelo de la máquina de Turing. Tanto el modelo original como sus variantes tienen el mismo poder, es decir, reconocen la misma clase de lenguajes. Para ilustrar larobustez del modelo de la máquina de Turing, hagamos una variación de la función de transición permitida. En la definición original, la función de transición fuerza a la cabeza de la cinta a moverse a la izquierda o a la derecha después de cada paso, la cabeza de la cinta no puede permanecer sin movimiento. Supongamos que le damos a la máquina de Turing la habilidad para que la cabeza de la cintapermanezca sin movimiento. La función de transición tendría la forma δ: Q x Γ → Q x Γ x { L, R, S }.
Los tipos de variantes de una maquina de Turing
Máquina de Turing indeterminista
Una máquina de Turing indeterminista se define de la forma esperada. En cada punto en una computación la máquina puede proceder de acuerdo a varias posibilidades. La función de transición para una máquina de Turingindeterminista tiene la forma
δ: Q x Γ → P(Q x Γ x { L, R })
En general, un cálculo , en una máquina no determinista, es un árbol de descripciones instantáneas (DI), en lugar de ser una secuencia lineal de DI, que es el caso de las máquinas deterministas. En el ejemplo, el árbol de DI es binario. De él representamos solo los dos itinerarios correspondientes a las funciones arriba indicadas:...