Trabajo de automatas

Tema 11. Máquinas de Turing: lenguajes
Fernando Cuartero Jos´ A. G´ mez e a Jos´ M. Puerta e Departamento de Inform´ tica a EPSA - UCLM

c {fernando,jgamez,jpuerta}@info-ab.uclm.es

Tema 11. M´ quinas de Turing: lenguajes – p.1/17 a

Contenidos
1. Introducción 2. Definición del modelo de máquina de Turing (MT). 3. Variaciones al modelo de MT. 4. MT como reconocedor de lenguajes. 5. MT ylenguajes de tipo 0. 6. Autómatas Linealmente Acotados y lenguajes de tipo 1.

c {fernando,jgamez,jpuerta}@info-ab.uclm.es

Tema 11. M´ quinas de Turing: lenguajes – p.2/17 a

Introducción
La máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea intuitiva de algoritmo. Tesis de Church: existirá un algoritmo pararesolver un problema si y sólo si ese problema puede ser resuelto por una máquina de Turing. Es decir, un problema será resoluble por un computador sii existe al menos una MT que lo computa. Existen modelos de computación equivalentes a la MT, pero no de mayor potencia computacional. Caracterización de las MTs en función de lo que pueden hacer: Aceptadores: reconocen la clase de los lenguajes detipo 0. Computadores: computan la clase de las funciones µ-recursivas.

c {fernando,jgamez,jpuerta}@info-ab.uclm.es

Tema 11. M´ quinas de Turing: lenguajes – p.3/17 a

Limitaciones de los modelos conocidos (AFs y APs)
Para reconocer lenguajes más complejos que los libres de contexto, no es suficiente una memoria auxiliar en forma de pila. Considérense por ejemplo los lenguajes:

L1 = {anbn cn | n ≥ 1}. L2 = {ww | w ∈ (0 + 1)∗ }
Es claro que una pila no es suficiente para el lenguaje L1 , pero ¿y si usamos 2 pilas? Por otra parte, no parece apropiado usar una estructura de pila LIFO para el lenguaje L2 , pero ¿y si usamos una estructura en forma de cola FIFO? Parece claro entonces que la limitación no está en el modelo de máquina de estados finitos, sino en la forma en que seestructura la memoria. Se pueden estudiar distintas opciones para aumentar la potencia de reconocimiento de los autómatas, pero sin duda, el más usado por su potencia y sencillez es la m´ quina de Turing. a
c {fernando,jgamez,jpuerta}@info-ab.uclm.es Tema 11. M´ quinas de Turing: lenguajes – p.4/17 a

El modelo de Máquina de Turing
En la MT usaremos la propia cinta de entrada/SALIDA como memoriaauxiliar. Por tanto, ahora tendremos una cabeza lectora/ESCRITORA posicionada sobre ella. Los símbolos de entrada se disponen de forma consecutiva a partir de la primera casilla. El resto de las casillas de la cinta se supone que contienen un símbolo especial (B) que representa un blanco.
a b c d B B B

Cabeza Lectora/Escritora

Control Finito
c {fernando,jgamez,jpuerta}@info-ab.uclm.es Tema11. M´ quinas de Turing: lenguajes – p.5/17 a

Máquina de Turing: Definición Formal
Definición. Una máquina de Turing es una séptupla M = (Q, Σ, Γ, δ, q0 , B, F) donde: Q, Σ, q0 y F representan lo mismo que en los AFs. Γ es un conjuto finito de símbolos que representa el alfabeto de la cinta. (Σ ⊂ Γ). B ∈ Γ es el símbolo blanco contenido por defecto en todas las casillas de la cinta. (B ∈ /Σ). δes la función de transición, definida como: δ : Q × Γ −→ Q × Γ × {L, R} En función del estado actual y del símbolo actualmente apuntado (leído), se: 1. cambiar de estado, 2. imprimir un símbolo en la casilla actualmente apuntada, y 3. mover la cabeza L/E una posición a la izquierda/derecha.
c {fernando,jgamez,jpuerta}@info-ab.uclm.es Tema 11. M´ quinas de Turing: lenguajes – p.6/17 aVariaciones al modelo de MT
Existen numerosas modificaciones al esquema anteriormente presentado de Máquina de Turing. Si bien todas ellas son equivalentes computacionalmente, el uso de uno u otro modelo puede facilitar el diseño para la resolución o demostración de cierto problema. Veamos 5 de estas modificaciones: MT con cinta infinita por ambos extremos. Este fue el modelo inicialmente presentado por...