M´aquinas de Turing IIC3242

IIC3242

–

M´ aquinas de Turing

1 / 42

Complejidad Computacional

Objetivo: Medir la complejidad computacional de un problema. Vale decir: Medir la cantidad de recursos computacionales necesarios para solucionar un problema. I

Tiempo

I

Espacio

I

...

Para hacer esto primero tenemos que introducir la noci´on de problema.

IIC3242

–

M´ aquinas de Turing

2 / 42

Problemas de decisi´on

Alfabeto Σ: Conjunto finito de s´ımbolos. I

Ejemplo: Σ = {0, 1}.

Palabra w : Secuencia finita de s´ımbolos de Σ. I

Ejemplo: w = 01101.

Σ∗ : Conjunto de todas las palabras construidas con s´ımbolos de Σ. Lenguaje L: Conjunto de palabras. I

IIC3242

–

Ejemplo: L = {0n 1n | n ∈ N}.

M´ aquinas de Turing

3 / 42

Problemas de decisi´on Problema de decisi´on asociado a un lenguaje L: Dado w ∈ Σ∗ , decidir si w ∈ L.

Ejemplo Podemos ver SAT como un problema de decisi´on. Suponga que P = {p, q}: I

I

IIC3242

–

Σ = {p, q, ¬, ∧, ∨, →, ↔, (, )} Algunas palabras de Σ∗ representan f´ ormulas, mientras que otras tales como ¬¬ y p¬q ∧ ∧ ∨ q no representan f´ormulas. SAT = {w ∈ Σ∗ | w representa una f´ ormula y w es satisfacible}.

M´ aquinas de Turing

4 / 42

Complejidad de un problema de decisi´on La complejidad de un lenguaje L es la complejidad del problema de decisi´on asociado a L. ¿Cu´ando decimos que L puede ser solucionado eficientemente? I

Cuando existe un algoritmo eficiente que decide L.

Ejercicio Muestre que L = {w ∈ {0, 1}∗ | w es un pal´ındromo} puede ser resuelto eficientemente. ¿Cu´ando decimos que L es un problema dif´ıcil? I

IIC3242

–

Cuando no existe un algoritmo eficiente que decide L.

M´ aquinas de Turing

5 / 42

M´aquinas de Turing

¿C´omo podemos demostrar que un problema es dif´ıcil? I

Para hacer esto, primero tenemos que formalizar la noci´on de algoritmo.

¿Qu´e es un algoritmo? ¿Podemos formalizar este concepto? I

M´aquinas de Turing: Intento por formalizar este concepto.

¿Podemos demostrar que las m´ aquinas de Turing capturan la noci´on de algoritmo? I

IIC3242

–

No, el concepto de algoritmo es intuitivo.

M´ aquinas de Turing

6 / 42

M´aquinas de Turing ¿Por qu´e creemos que las m´ aquinas de Turing son una buena formalizaci´on del concepto de algoritmo? I

Porque cada programa de una m´aquina de Turing puede ser implementado.

I

Porque todos los algoritmos conocidos han podido ser implementados en m´aquinas de Turing.

I

Porque todos los otros intentos por formalizar este concepto fueron reducidos a las m´aquinas de Turing. I

I

I

IIC3242

–

Los mejores intentos resultaron ser equivalentes a las m´aquinas de Turing. Todos los intentos “razonables” fueron reducidos eficientemente.

Tesis de Church: Algoritmo = M´ aquina de Turing.

M´ aquinas de Turing

7 / 42

M´aquinas de Turing: Formalizaci´on Definici´on M´aquina de Turing (Determinista): (Q, Σ, Γ, q0 , δ, F ) I

Q es un conjunto finito de estados.

I

Σ es un alfabeto tal que `, B 6∈ Σ.

I

Γ es un alfabeto tal que Σ ∪ {`, B} ⊆ Γ.

I

q0 ∈ Q es el estado inicial.

I

F ⊆ Q es un conjunto de estados finales.

I

δ es una funci´on parcial: δ : Q × Γ → Q × Γ × {I , N, D}. δ es llamada funci´on de transici´on.

IIC3242

–

M´ aquinas de Turing

8 / 42

M´aquinas de Turing: Funcionamiento La cinta de la m´aquina de Turing es infinita hacia la derecha. I

El s´ımbolo ` es usado para demarcar la posici´on 0 de la cinta.

Supuesto I I

Si δ(q, `) est´a definido: δ(q, `) = (q 0 , `, X ), con X ∈ {D, N} Si a ∈ Γ r {`} y δ(q, a) est´ a definido: δ(q, a) = (q 0 , b, X ), con b ∈ Γ r {`}.

Σ es el alfabeto de entrada y Γ es el alfabeto de la cinta. I

I

IIC3242

–

Una palabra w ∈ Σ∗ de entrada de largo n es colocada en las posiciones 1, . . ., n de la cinta. Las posiciones siguientes (n + 1, n + 2, . . .) contienen el s´ımbolo B.

M´ aquinas de Turing

9 / 42

M´aquinas de Turing: Funcionamiento

Al comenzar a funcionar, la m´ aquina se encuentra en el estado q0 y su cabeza lectora est´ a en la posici´on 1 de la cinta. En cada instante la m´ aquina se encuentra en un estado q y su cabeza lectora est´a en una posici´on p. I Si el s´ ımbolo en la posici´on p es a y δ(q, a) = (q 0 , b, X ), entonces: I I I

IIC3242

–

La m´aquina escribe el s´ımbolo b en la posici´on p de la cinta. Cambia de estado desde q a q 0 . Mueve la cabeza lectora a la posici´ on p − 1 si X = I , y a la posici´on p + 1 si X = D. Si X = N, entonces la cabeza lectora permanece en la posici´ on p.

M´ aquinas de Turing

10 / 42

M´aquinas de Turing: Aceptaci´on

Los estados de F son utilizados como estados de aceptaci´on. I

Una palabra w es aceptada por una m´ aquina M si y s´olo si la ejecuci´on de M con entrada w se detiene en un estado de F .

Definici´on Lenguaje aceptado por una m´ aquina de Turing M: L(M) = {w ∈ Σ∗ | M acepta w }.

IIC3242

–

M´ aquinas de Turing

11 / 42

M´aquinas de Turing: Ejemplo Queremos construir una m´ aquina que verifique si el n´ umero de 0s en una palabra es par: M = (Q, Σ, Γ, q0 , δ, F ) I

Q = {q0 , q1 }.

I

Σ = {0, 1}.

I

Γ = {0, 1, `, B}.

I

F = {q0 }.

I

δ es definida como: δ(q0 , 0) = (q1 , B, D) δ(q0 , 1) = (q0 , B, D) δ(q1 , 0) = (q0 , B, D) δ(q1 , 1) = (q1 , B, D)

IIC3242

–

M´ aquinas de Turing

12 / 42

M´aquinas de Turing: Ejecuci´on Supongamos que w = 00010:

Inicio:

`

0

0

0

1

0

B

B

. . .

0

0

1

0

B

B

. . .

0

1

0

B

B

. . .

q0 Paso 1:

`

B

q1 Paso 2:

`

B

B

q0

IIC3242

–

M´ aquinas de Turing

13 / 42

M´aquinas de Turing: Ejecuci´on

Paso 3:

`

B

B

B

1

0

B

B

. . .

0

B

B

. . .

B

B

. . .

q1 Paso 4:

`

B

B

B

B

q1 Paso 5:

`

B

B

B

B

B

q0

Conclusi´on: La m´aquina acepta w = 00010.

IIC3242

–

M´ aquinas de Turing

14 / 42

El lenguaje aceptado por una m´aquina de Turing: Ejemplos

Ejemplo Para la m´aquina M mostrada en las transparencias anteriores: L(M) = {w ∈ {0, 1}∗ | w contiene un n´ umero par de s´ımbolos 0}.

Ejercicio Construya una m´aquina de Turing que acepte el lenguaje L = {w ∈ {0, 1}∗ | w es un pal´ındromo}.

IIC3242

–

M´ aquinas de Turing

15 / 42

Complejidad de un algoritmo

Una M´aquina de Turing puede no detenerse en alguna entrada. I

Primera noci´on de algoritmo: MT que se detiene en todas las entradas.

¿C´omo se mide el tiempo de ejecuci´on de un algoritmo? Para una MT con alfabeto Σ:

IIC3242

–

I

Paso de M: Ejecutar una instrucci´on de la funci´on de transici´on.

I

tiempo M (w ): N´ umero de pasos ejecutados por M con entrada w ∈ Σ∗ .

M´ aquinas de Turing

16 / 42

Complejidad de un algoritmo

Definici´on El tiempo de funcionamiento de una MT M en el peor caso es definido por la funci´on tM : tM (n) = m´ax{ tiempo M (w ) | w ∈ Σ∗ y |w | = n }.

Ejercicio Construya una m´aquina de Turing que funcione en tiempo O(n2 ) y acepte el lenguaje L = {w ∈ {0, 1}∗ | w es un pal´ındromo}.

IIC3242

–

M´ aquinas de Turing

17 / 42

M´aquinas de Turing con varias cintas Definici´on MT con k cintas: (Q, Σ, Γ, q0 , δ, F ) I

Q es un conjunto finito de estados.

I

Σ es un alfabeto tal que `, B 6∈ Σ.

I

Γ es un alfabeto tal que Σ ∪ {`, B} ⊆ Γ.

I

q0 ∈ Q es el estado inicial.

I

F ⊆ Q es un conjunto de estados finales.

I

δ es una funci´on parcial: δ : Q × Γk → Q × Γk × {I , N, D}k . δ es llamada funci´on de transici´on.

IIC3242

–

M´ aquinas de Turing

18 / 42

M´aquinas de Turing con k cintas: Funcionamiento

La m´aquina tiene k cintas infinitas hacia la derecha. I

El s´ımbolo ` es usado para demarcar la posici´on 0 de cada cinta.

Σ es el alfabeto de entrada y Γ es el alfabeto de las cintas. I

IIC3242

–

Una palabra w ∈ Σ∗ de entrada de largo n es colocada en las posiciones 1, . . ., n de la primera cinta.

I

Las siguientes posiciones (n + 1, n + 2, . . .) de la primera cinta contienen el s´ımbolo B.

I

Las restantes cintas contienen el s´ımbolo B en las posiciones 1, 2, 3, . . .

M´ aquinas de Turing

19 / 42

M´aquinas de Turing con k cintas: Funcionamiento La m´aquina tiene una cabeza lectora por cinta. I

Al comenzar, la m´ aquina se encuentra en el estado q0 , y cada cabeza lectora est´ a en la posici´on 1 de su cinta.

En cada instante la m´ aquina se encuentra en un estado q y su cabeza lectora i se encuentra en la posici´ on pi . I Si el s´ ımbolo en la posici´on pi es ai y δ(q, a1 , . . . , ak ) = (q 0 , b1 , . . . , bk , X1 , . . . , Xk ), entonces: I

I I

IIC3242

–

La m´aquina escribe el s´ımbolo bi en la posici´on pi de la i-´esima cinta. Cambia de estado desde q a q 0 . Mueve la cabeza lectora de la i-´esima cinta a la posici´on pi − 1 si Xi = I , y a la posici´ on pi + 1 si Xi = D. Si Xi = N, entonces la m´aquina no mueve la cabeza lectora de la i-´esima cinta.

M´ aquinas de Turing

20 / 42

MT con k cintas: Aceptaci´on y complejidad Una palabra w es aceptada por una MT M con k cintas si y s´olo si la ejecuci´on de M con entrada w se detiene en un estado final. L(M) = {w ∈ Σ∗ | M acepta w }.

Para una MT con k cintas y alfabeto Σ: I

Paso de M: Ejecutar una instrucci´on de la funci´on de transici´on.

I

tiempo M (w ): N´ umero de pasos ejecutados por M con entrada w ∈ Σ∗ .

I

Tiempo de funcionamiento M en el peor caso: tM (n) = m´ax{ tiempo M (w ) | w ∈ Σ∗ y |w | = n }.

IIC3242

–

M´ aquinas de Turing

21 / 42

MT con k cintas: Ejemplo

Ejercicio Construya una MT M con dos cintas que funcione en tiempo O(n) y acepte el lenguaje L = {w ∈ {0, 1}∗ | w es un pal´ındromo}. Soluci´ on: Definimos M = (Q, Σ, Γ, q0 , δ, F ) de la siguiente forma:

IIC3242

–

I

Q = {q0 , qc , qr , qv , qa }

I

Σ = {0, 1}

I

Γ = {0, 1, B, `}

I

F = {qa }

M´ aquinas de Turing

22 / 42

MT con k cintas: Ejemplo

I

Funci´on δ es definida de la siguiente forma:

(q0 , B, B) (q0 , 0, B) (q0 , 1, B) (qc , 0, B) (qc , 1, B) (qc , B, B) (qr , 0, 0) (qr , 0, 1)

IIC3242

–

→ → → → → → → →

M´ aquinas de Turing

(qa , B, B, N, N) (qc , 0, 0, D, D) (qc , 1, 1, D, D) (qc , 0, 0, D, D) (qc , 1, 1, D, D) (qr , B, B, I , I ) (qr , 0, 0, I , N) (qr , 0, 1, I , N)

(qr , 1, 0) (qr , 1, 1) (qr , `, 0) (qr , `, 1) (qv , 0, 0) (qv , 1, 1) (qv , B, `)

→ → → → → → →

(qr , 1, 0, I , N) (qr , 1, 1, I , N) (qv , `, 0, D, N) (qv , `, 1, D, N) (qv , 0, 0, D, I ) (qv , 1, 1, D, I ) (qa , B, `, N, N)

23 / 42

Aceptaci´on en distintos modelos

Un lenguaje L es aceptado por una MT M si L = L(M). I

¿Es posible aceptar m´ as lenguajes si se usa cintas adicionales?

Teorema Si un lenguaje L es aceptado por una MT M1 con k cintas, entonces L es aceptado por una MT M2 con una cinta.

Ejercicio Demuestre el teorema. I

IIC3242

–

¿Cu´al es la diferencia de complejidad entre M1 y M2 ?

M´ aquinas de Turing

24 / 42

Complejidad en distintos modelos Un lenguaje L es aceptado por una MT M en tiempo O(t(n)) si L = L(M) y tM (n) es O(t(n)). I

La definici´on es id´entica para el caso de Ω(t(n)) y Θ(t(n)).

¿Es posible aceptar m´ as r´ apido si se usa cintas adicionales?

Teorema Si un lenguaje L es aceptado por una MT M1 con k cintas en tiempo O(t(n)), entonces L es aceptado por una MT M2 con una cinta en tiempo O(t(n)2 ).

Ejercicio Demuestre el teorema. I

IIC3242

–

¿Es posible reducir la diferencia entre M1 y M2 ?

M´ aquinas de Turing

25 / 42

Complejidad en distintos modelos Sea L = {w ∈ {0, 1, #}∗ | w es un pal´ındromo}. I

L es aceptado por una MT con dos cintas en tiempo O(n).

I

¿Puede ser L aceptado en tiempo lineal por una MT con una cinta?

Proposici´on Sea M una MT con una cinta. Si L = L(M), entonces M funciona en tiempo Ω(n2 ). Demostraci´ on: Suponga que L = L(M), donde M es una MT con una cinta. I

IIC3242

–

Sin perdida de generalidad, suponemos que M siempre recorre toda la palabra de entrada.

M´ aquinas de Turing

26 / 42

Complejidad en distintos modelos Para w ∈ {0, 1, #}∗ , sea w r la palabra obtenida al escribir w en el sentido inverso. Defina Ln como el siguiente lenguaje (para n divisible por 4): n

n

Ln = {w # 2 w r | w ∈ {0, 1} 4 }. N´otese que Ln ⊆ L. Sea w ∈ Ln y n4 ≤ i ≤ 3n 4 . Entonces Ci (w ) es la secuencia de estados [q1 , . . ., qk ] en que se encuentra M despu´es de moverse entre las posiciones i e i + 1 (en cualquiera de las dos direcciones) en la ejecuci´on que tiene a w como entrada. I

IIC3242

–

C (w ) = {Ci (w ) |

M´ aquinas de Turing

n 4

≤i ≤

3n 4 }.

27 / 42

Complejidad en distintos modelos Lema Si w1 , w2 ∈ Ln y w1 6= w2 , entonces C (w1 ) ∩ C (w2 ) = ∅. Demostraci´ on: Suponga que el lema es falso. Entonces existen n i , j ∈ { 4 , . . . , 3n 4 } tales que Ci (w1 ) = Cj (w2 ). Sean u1 y u2 las palabra formadas por los primeros i s´ımbolos de w1 y los u ´ltimos n − j s´ımbolos de w2 , respectivamente. Dado que Ci (w1 ) = Cj (w2 ), se tiene que u1 u2 es aceptado por M. I

¿C´omo se demuestra esto?

Pero u1 u2 no es un pal´ındromo, por lo que tenemos una contradicci´on. IIC3242

–

M´ aquinas de Turing

28 / 42

Complejidad en distintos modelos Para w ∈ Ln , sea sw la secuencia m´ as corta en C (w ). I

Sn = {sw | w ∈ Ln }.

Por el lema sabemos que sw1 6= sw2 si w1 6= w2 . n

I

Por lo tanto: |Sn | = |Ln | = 2 4

Sea m el largo de la secuencia mas larga en Sn . I

Cantidad de posibles secuencias de largo a lo m´as m: m X i =0

IIC3242

–

M´ aquinas de Turing

|Q|i

=

|Q|m+1 − 1 . |Q| − 1

29 / 42

Complejidad en distintos modelos

De lo anterior concluimos que: I

|Q|m+1 −1 |Q|−1

n

≥ 24 .

¿Por qu´e?

Se tiene entonces que m es Ω(n). I

Por lo tanto existe w0 ∈ Ln para el cual |sw0 | es Ω(n).

Entonces: Todas las secuencias en C (w0 ) son de largo Ω(n). Conclusi´on: Con entrada w0 , la m´ aquina M toma tiempo Ω(n2 ). I

IIC3242

–

Puesto que M tiene que generar largo Ω(n).

M´ aquinas de Turing

n 2

secuencias de estados de

30 / 42