Teoría de la computación

Reducibilidad
Def.: Sean L1, L2 ⊆ Σ∗ se dirá que L1 se reduce a L2 (L1 α L2) si existe una función total computable (o recursiva) f: Σ∗ → Σ∗ tal que ∀w ∈ Σ∗, w ∈ L1 ⇔ f(w) L2. Σ∗ L1 w . w’ . Σ∗ L1 f(w) . f(w’) .

Se dice que f es computable si existe una MT que la computa y que siempre se detiene.

w

Mf

f(w)

Mf nunca loopea. A veces, usaremos la expresión Mf(w) para referirnos a lafunción computada por la MT Mf

Nota: la reducibilidad es una transformación de instancias de un problema en instancias de otro problema. Ejercicio 1: Σ = {0, 1} L1 = {w ∈ Σ* / cant1(w) es par} L2 = {w ∈ Σ* / cant1(w) es impar} Donde cant1(w) es la cantidad de 1 que hay en w Demostrar que L1 α L2. Se construye Mf, una MT que computa la función de reducibilidad. Mf = δ: B → (1, S) 0 → (1, S) 1 →(0, S)

q0

q1

Hay que demostrar que Mf siempre se detiene y que w ∈ L1 ⇔ Mf(w) ∈ L2 1) Mf siempre se detiene: claramente sí, pues solamente ejecuta un movimiento.

2) w ∈ L1 ⇔ Mf(w) L2 Claramente si w comienza con 1 entonces cant1(Mf(w)) = cant1(w) – 1, y si w no comienza con 1 cant1(Mf(w)) = cant1(w) + 1. Por lo tanto a) Si w ∈ L1 ⇒ cant1(w) es par ⇒ cant1(Mf(w)) es impar ⇒ Mf(w) ∈ L2b) Si w ∉ L1 ⇒ cant1(w) es impar ⇒ cant1(Mf(w)) es par ⇒ Mf(w) ∉ L2 De a) y b) se tiene que w ∈ L1 ⇔ Mf(w) L2. Para practicar: Sean L1 = {w ∈ {0, 1}* tq cant1(w) es par} L2 = {w ∈ {0, 1}* tq cant1(w) = 1} Mf la siguiente máquina de Turing 1 → (B, D) 1 → (B, D) B → (1, S) q2

q1

0 → (B, D)

q0 0 → (B, D)

Demostrar que Mf computa una función de reducibilidad patra L1 α L2. Es decir que: w∈ L1 ⇔ Mf(w) L2 Ejercicio 2: Sea L un lenguaje recursivo (L ∈ R) y L1 = { tq L(M) = L y M siempre se detiene} L2 = { tq L(M) = L} Demostrar que L1 α L2 Para demostrar que L1 α L2 hay que encontrar una MT Mf que siempre se detenga para la cual sea cierto que ∈ L1 ⇔ Mf() ∈ L2 Se construye Mf que trabaja de la siguiente manera: recorre todas las quíntuplas de , si en la 3ra posición encuentra qA loreemplaza por qR, si encuentra qR lo reemplaza por qA. Hay que demostrar que Mf se detiene y que ∈ L1 ⇔ Mf() ∈ L2. 1) Mf siempre se detiene porque la entrada es finita. 2) ∈ L1 ⇔ Mf() ∈ L2. a) ∈ L1 ⇒ Mf() ∈ L2. Si ∈ L1 ⇒ L(M) = L ⇒ si w ∈ L ⇒ M para en qA ⇒ Mf() para en qR para la misma entrada si w ∉ L ⇒ M para en qR ⇒ Mf() para en qA para la misma entrada por lo tanto Mf() acepta L

⇒Mf() ∈ L2. b) Mf () ∈ L2 ⇒ Mf() acepta L ⇒ M acepta L (idem anterior) ⇒ ∈ L1 También se puede hacer con ∉ L1 ⇒ Mf() ∉ L2. Nota: si L1 α L2 significa que se puede resolver L1 a partir de la resolución de L2.

w M1

Mf

f(w)

M2

qA qR

Teorema: L1, L2 ∈ Σ y existe la reducción L1 α L2, si L2 ∈ R ⇒ L1 ∈ R. Dem.: L2 ∈ R ⇒ existe una máquina de Turing M2 tq L2 = L(M2) y M2 siempre sedetiene. Se construye M1 que hace: 1) Simula Mf sobre w y obtiene f(w) 2) Simula M2 sobre f(w) y acepta sii M2 acepta a) ¿L1 = L(M1)? w ∈ L(M1) porque L1 α L2 w ∉ L1 ⇒ f(w) ∉ L2 ⇒ M2 para en qR con input f(w) ⇒ M1 para en qR con input w ⇒ w ∉ L(M1) Por lo tanto, L1 = L(M1) b) ¿M1 se detiene siempre? Sí, pues Mf y M2 se detienen siempre por hipótesis. De a) y b) L1 ∈ R. Teorema: Sean L1, L2 ⊆ ∑* y lareducción L1 α L2, se cumple que L2 ∈ RE ⇒ L1 ∈ RE. Se demuestra de manera similar a la demostración del teorema anterior. Corolario: Sean L1, L2 ⊆ ∑* y la reducción L1 α L2, se cumplen que Si L1 ∉ R ⇒ L2 ∉ R Por las contrarrecíprocas Si L1 ∉ RE ⇒ L2 ∉ RE porque L1 α L2 w ∈ L1 ⇒ f(w) ∈ L2 ⇒ M2 para en qA con input f(w) ⇒ M1 para en qA con input w ⇒

Ejercicio 3: sea HP = {(, w) / M se detiene coninput w}, (Halting Problem), demostrar que HP ∈ (RE-R) 1) HP ∈ RE. Se construye una MT MHP tq L(MHP) = HP. MHP simula M sobre w, si M para (en qA o en qR) MHP para en qA, si M no para, MHP no para.

w MHP

M

qA qR

qA

2) HP ∉ R. Se puede probar con una reducción desde un lenguaje que no sea R, específicamente utilizando Lu α HP, y como Lu ∉ R será cierto HP ∉ R. Dem. Sea la...