Maquinas de turing

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 deTuring 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 de decisi´n o
Problema dedecisi´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 o satisfacible}.

IIC3242

–

M´quinasde 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 resuelto eficientemente. ¿Cu´ndo decimos que L es unproblema 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? e M´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 de una m´quina de Turing puede ser a implementado. Porque todos losalgoritmos 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 a7 / 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 estados finales. δ es una funci´n parcial: o δ : Q × Γ → Q × Γ × {I , N, D}. δ es llamada funci´n de transici´n. o oIIC3242

–

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 entraday Γ 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 Turing: Funcionamiento a

Al comenzar a funcionar, la m´quina se encuentra en el estado q0 a y su cabeza lectora est´ en la posici´n 1 de...