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”.