Maquinas de Turing

Capítulo 13.

Máquinas de Turing
13.1. Conceptos generales
Definición. Descripciones instantáneas. Lenguaje
reconocido por una MT. Función computada por
una MT.

13.2. Otras definiciones
Equivalencia. Máquinas con alfabeto binario,
Máquinas no deterministas. Máquinas con dos
cintas.

13.3. MT para reconocer lenguajes
MT equivalente a una gramática de tipo 0.
Gramática de tipo 0equivalente a una MT.

13.4. MT para computar funciones
Funciones de un parámetro. Funciones de varios
parámetros. Funciones complejas.

1

13.1. Conceptos generales
Definición
Una máquina de Turing es una séptupla M= (Γ,Σ,•,Q,q0,f,F)
donde :
1. Γ es el alfabeto de símbolos de la cinta
2. Σ ⊂ Γ es el alfabeto de símbolos de entrada
3. • ∈ Γ es el símbolo blanco que no pertenece a Σ
4.Q es un conjunto finito de estados
5. q0 ∈ Q es el estado inicial
6. F ⊆ Q es el conjunto de estados finales
7. f es una función de transición parcial
f: Q×Γ → Q×Γ×{L,R}
Intuitivamente:
Dispositivo capaz de adoptar un estado determinado (de Q) y
que está conectado a una cabeza lectura/escritura que puede leer
y escribir símbolos en una cinta infinita. En cada acción o
movimiento:
1. lamáquina lee el símbolo de la cinta en la posición donde
se encuentra la cabeza de lectura/escritura
2. en función del símbolo leído y del estado actual la
máquina:
a. pasa a un nuevo estado (de forma determinista)
b. imprime un símbolo en la cinta en la misma posición
donde acaba de leer el símbolo actual
c. mueve la cabeza de lectura/escritura una posición a
la izquierda (L), o a laderecha (R).
Inicialmente, la cinta (infinita a ambos lados) contiene un
número finito de símbolos de Σ, precedidos y seguidos por un
número infinito de blancos. La cinta se comporta como un
dispositivo de entrada/salida.
2

Ejemplo 1:
M= ({a,b,•},{a,b},•,{q0,q1},q0,f,{q1})
f(q0,a)=(q0,a,R)
f(q0,b)=(q1,•,L)
... • a ... a b • ...
q0
... • a ... a • ...
q0

⇒ para en ... • a ... a • •...
q1
⇒ para en ... • a ... a • ...
q0

⇒ pasa todos los a’s que haya y cuando encuentra una b lo
cambia por • y para en el estado q1
Representación gráfica:
q0

(b,•,L)

q1*

(a,a,R)

- cada nodo corresponde a un estado de la MT
- cada transición f(qi,a)=(qj,b,X) con qi,qj∈Q, a,b∈Γ y X∈{L,R}
corresponde a un arco del nodo qi al nodo qj marcado con la
etiqueta (a,b,X)
- elestado inicial se marca con
y los estado finales con *
Descripciones instantáneas
- contiene el contenido de la cinta (sólo escribiremos los blancos
cuando sea necesario)
- se incluye el estado de la máquina en la posición delante del
símbolo donde se encuentra la cabeza lectora/escritora
q0aaaab
o
aaaabq1•
3

Movimiento:
q0aaab ├ aq0aab posible si y sólo si f(q0,a)=(q0,a,R)
q0aaab ├q0•baab posible si y sólo si f(q0,a)=(q0,b,L)
aaaq0b ├ aaa•q1• posible si y sólo si f(q0,b)=(q1,•,R)
Cierre transitivo de ├ (serie de movimientos):
q0aaab ├* aaaq1• si existe q0aaab ├ ... ├ aaaq1•
Una MT comienza en un estado inicial con alguna información
en la cinta, x1qix2 ,realiza una serie de movimientos y
posiblemente:
1. Entre en un bucle infinito (no pare nunca):
x1qix2├*∞
2. Llegue auna configuración en la que no es posible ningún
movimiento:
x1qix2 ├* y1qjay2 (para algún qj y a, tal que f(qj,a) no
esta definido)
Si, además, qj∈F, decimos que la máquina para en un estado
final. (por convención no definimos transiciones f(qj,a) para
ningún estado final qj)
Ejemplo 2:
M= ({a,b,•},{a,b},•,{q0,q1,q2},q0,f,{q2})
f(q1,b)=(q0,b,L)
f(q0,a)=(q1,a,R)
f(q0,b)=(q2,b,R)f(q1,a)=(q0,a,L)

f(q1,•)=(q0,•,L)

diferentes casos:
q0•
⇒ para en q0•
⇒ para en q2
q0bx1x2...xn├ bq2x1x2...xn
q0ax1x2...xn├ aq1x1x2...xn ├ q0ax1x2...xn ... (bucle infinito)
4

Lenguaje reconocido por una MT
El contenido de la cinta al iniciar una máquina puede
interpretarse como una palabra de un determinado lenguaje.
Definición:
Sea M= (Γ,Σ,•,Q,q0,f,F) una MT. El lenguaje...