Post on 11-May-2020
Clases 18 y 19: Máquina de Turing
1M. en C. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom
edfranco@ipn.mx
Contenido• Máquinas de Turing
• Definición formal de la máquina de Turing
• Funcionamiento de la máquina de Turing
• Ejemplo 01
• Representación gráfica
• Descripciones instantáneas
• Movimiento
• Cierre transitivo de ├ (serie de movimientos)
• Ejemplo 02
• Lenguaje reconocido por una MT
• Definición
• Convenciones
• Ejemplo 03
• Función computada por una MT
• Convenciones
• Ejemplo 04
Compiladores (Lenguajes y gramáticas - Edgardo A. Franco)
2
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
3
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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.
4
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Una máquina de Turing se puede definir
formalmente como una séptupla:
M= (Γ,Σ,•,Q,q0,f,F)
• Γ: Es el alfabeto de símbolos de la cinta.
• Σ: Es el alfabeto de símbolos de entrada, Σ ⊂ Γ.
• •: Es el símbolo blanco que no pertenece a Σ, • ∈ Γ.
• Q: Es un conjunto finito de estados.
• q0: Es el estado inicial, y cumple q0 ∈ Q.
• f: Es una función de transición parcial, de la forma:
f: Q×Γ → Q×Γ×{L,R}
• F: Es el conjunto de estados finales, F ⊆ Q.
5
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z• En cada acción o movimiento:
• La máquina lee el símbolo de la cinta en la posición
donde se encuentra la cabeza de lectura/escritura.
• 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 la derecha (R).
6
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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.
7
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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 • • …
q1⇒ para en
8
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
⇒ pasa todos los a’s que haya y cuando encuentra una b
lo cambia por • y para en el estado q1
… • a … a • …
q0
… • a … a • …
q0⇒ para en
9
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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).
• El estado inicial se marca con y los estado finales
con *.
10
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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
aaaabq1•
11
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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)
12
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
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 a una 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)
13
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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)
14
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• M= ({a,b,•},{a,b},•,{q0,q1,q2},q0,f,{q2})
f(q0,a)=(q1,a,R) f(q1,b)=(q0,b,L) f(q1,•)=(q0,•,L)
f(q0,b)=(q2,b,R) f(q1,a)=(q0,a,L)
diferentes casos:
1. q0• ⇒⇒⇒⇒ para en q0•
2. q0bx1x2...xn├ bq2x1x2...xn ⇒⇒⇒⇒ para en q2
3. q0ax1x2...xn├ aq1x1x2...xn├ q0ax1x2...xn ... (bucle infinito)
15
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• El contenido de la cinta al iniciar una máquina puede
interpretarse como una palabra de un determinado
lenguaje.
• Sea M= (Γ,Σ,•,Q,q0,f,F) una MT. El lenguaje
aceptado por M es:
L(M) = {x | q0x ├* y1qiay2, con qi∈∈∈∈F,
x∈∈∈∈Σ*,y1,y2∈∈∈∈Γ*, a∈∈∈∈Γ y f(qi,a) no esta definido}
16
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Inicialmente la cinta contiene una palabra x y la
cabeza de lectura/escritura se encuentra en la
posición del primer símbolo de x en el estado q0:
q0x.
• La máquina acepta x si se para en un estado final.
• El contenido de la cinta al parar es irrelevante.
• Se rechaza x si la máquina no se para nunca o se
para en un estado que no es final.
• Si la palabra es λ, la configuración inicial es q0•.
17
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
18
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Las MTs pueden transformar entradas en salidas:
• La entrada son todos los símbolos no blancos en la
cinta en el momento inicial.
• El contenido de la cinta (los símbolos no blancos) al
final de la computación (cuando la máquina se para
en un estado final) se considera como salida.
En otras palabras, se puede considerar una MT como
la implementación de una función f: y=f(x) si para la
configuración inicial q0x la máquina M para en una
configuración qfy, donde qf es un estado final de M:
q0x├M*qfy
19
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Codificación de los números naturales en el sistema
unario:
Se representa cada x∈Ν por una palabra w(x)∈{1}+
tal que |w(x)|-1=x
(0→”1”; 1→”11”; 2→”111”; 3→”1111” ...)
(se pueden usar otros tipos de codificaciones)
• Al inicio y al final de la ejecución la cabeza se
encuentra sobre el primer 1 a la izquierda.
• No hay transiciones definidas para estados finales.
20
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• M= ({1,•},{1},•,{q0,q1,q2,q3,q4,q5},q0,f,{q5})
f(q0,1)=(q0,1,R) f(q2,1)=(q3,•,L)
f(q0,•)=(q1,1,R) f(q3,1)=(q4,•,L)
f(q1,1)=(q1,1,R) f(q4,1)=(q4,1,L)
f(q1,•)=(q2,•,L) f(q4,•)=(q5,•,R)
21
Teo
ría
co
mp
uta
cio
na
l
Cla
ses
18
y 1
9:
Má
qu
ina
de
Tu
rin
g
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z•q0111•11•├ •1q011•11•├ •11q01•11•├•111q0•11•├ •1111q111•├ •11111q11•├•111111q1•├ •11111q21•├ •1111q31••├•111q41•••├ •11q411•••├ •1q4111•••├•q41111•••├ q4•1111•••├ •q51111•••
⇒ q0111•11├*q51111
⇒ calcula la suma de dos enteros positivos x+y,
donde x e y se representan mediante notación
unaria:1n corresponde al número n-1 . Es decir, x=0
se representa con “1”, x=1 se representa con “11”.