teorico

M´quinas de Turing
a
IIC3242

IIC3242

–

M´quinas de Turing
a

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.
Tiempo
Espacio
...
Para hacer esto primero tenemos que introducir la noci´n de
o
problema.

IIC3242

–M´quinas de Turing
a

2 / 42

Problemas de decisi´n
o

Alfabeto Σ: Conjunto finito de s´
ımbolos.
Ejemplo: Σ = {0, 1}.
Palabra w : Secuencia finita de s´
ımbolos de Σ.
Ejemplo: w = 01101.
Σ∗ : Conjunto de todas las palabras construidas con s´
ımbolos de Σ.
Lenguaje L: Conjunto de palabras.
Ejemplo: L = {0n 1n | n ∈ N}.

IIC3242

–

M´quinas de Turing
a

3 / 42

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

Ejemplo
Podemos ver SAT como un problema de decisi´n. Suponga que
o
P = {p, q}:
Σ = {p, q, ¬, ∧, ∨, →, ↔, (, )}
Algunas palabras de Σ∗ representan f´rmulas, mientras que
o
otras tales como ¬¬ y p¬q ∧ ∧ ∨ q no representan
f´rmulas.
o
SAT = {w ∈ Σ∗ | w representa una f´rmula y w es
osatisfacible}.

IIC3242

–

M´quinas de Turing
a

4 / 42

Complejidad de un problema de decisi´n
o
La complejidad de un lenguaje L es la complejidad del problema de
decisi´n asociado a L.
o
¿Cu´ndo decimos que L puede ser solucionado eficientemente?
a
Cuando existe un algoritmo eficiente que decide L.

Ejercicio
Muestre que L = {w ∈ {0, 1}∗ | w es un pal´
ındromo} puede ser
resueltoeficientemente.
¿Cu´ndo decimos que L es un problema dif´
a
ıcil?
Cuando no existe un algoritmo eficiente que decide L.

IIC3242

–

M´quinas de Turing
a

5 / 42

M´quinas de Turing
a

¿C´mo podemos demostrar que un problema es dif´
o
ıcil?
Para hacer esto, primero tenemos que formalizar la noci´n de
o
algoritmo.
¿Qu´ es un algoritmo? ¿Podemos formalizar este concepto?
eM´quinas de Turing: Intento por formalizar este concepto.
a
¿Podemos demostrar que las m´quinas de Turing capturan la
a
noci´n de algoritmo?
o
No, el concepto de algoritmo es intuitivo.

IIC3242

–

M´quinas de Turing
a

6 / 42

M´quinas de Turing
a
¿Por qu´ creemos que las m´quinas de Turing son una buena
e
a
formalizaci´n del concepto de algoritmo?
o
Porque cada programa deuna m´quina de Turing puede ser
a
implementado.
Porque todos los algoritmos conocidos han podido ser
implementados en m´quinas de Turing.
a
Porque todos los otros intentos por formalizar este concepto fueron
reducidos a las m´quinas de Turing.
a
Los mejores intentos resultaron ser equivalentes a las m´quinas
a
de Turing.
Todos los intentos “razonables” fueron reducidos
eficientemente.Tesis de Church: Algoritmo = M´quina de Turing.
a
IIC3242

–

M´quinas de Turing
a

7 / 42

M´quinas de Turing: Formalizaci´n
a
o
Definici´n
o
M´quina de Turing (Determinista): (Q, Σ, Γ, q0 , δ, F )
a
Q es un conjunto finito de estados.
Σ es un alfabeto tal que , B ∈ Σ.
Γ es un alfabeto tal que Σ ∪ { , B} ⊆ Γ.
q0 ∈ Q es el estado inicial.
F ⊆ Q es un conjunto de estadosfinales.
δ es una funci´n parcial:
o
δ : Q × Γ → Q × Γ × {I , N, D}.
δ es llamada funci´n de transici´n.
o
o

IIC3242

–

M´quinas de Turing
a

8 / 42

M´quinas de Turing: Funcionamiento
a
La cinta de la m´quina de Turing es infinita hacia la derecha.
a
El s´
ımbolo

es usado para demarcar la posici´n 0 de la cinta.
o

Supuesto
Si δ(q, ) est´ definido: δ(q, ) = (q , , X ), con X∈ {D, N}
a
Si a ∈ Γ { } y δ(q, a) est´ definido: δ(q, a) = (q , b, X ),
a
con b ∈ Γ { }.
Σ es el alfabeto de entrada y Γ es el alfabeto de la cinta.
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.
IIC3242

–

M´quinas de Turing
a

9 / 42

M´quinas de...