7_a Reducibilidad(1)

Vista previa del material en texto

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. 
 
w 
. 
L1 
w’ 
. 


 
f(w) 
 . 
L2 
f(w’) 
 . 


 
Se dice que f es computable si existe una MT que la computa y que 
siempre se detiene. 
 
 
 
Nota: la reducibilidad es una transformación de instancias de un 
problema en instancias de otro problema. 
 Mf w f(w) 
 Mf nunca loopea. A veces, 
usaremos la expresión 
M f(w) para referirnos a la 
función computada por la 
MT Mf 
 
Ej.: L1 = {w  {a, b}
*
 tq w comienza con a} 
 L2 = {w  {a, b}
*
 tq w comienza con b} 
Mf = <Q, , q0, F>; Q = {q0, q1};  = {a, b};  = {B, a, b}; F =  
 
Puede demostrarse fácilmente que Mf siempre se detiene y que 
w  

 w  L1  f(w)  L2. 
 
 
q0 
a  (b, S) 
q1 
 
b  (a, S) 
B  (B, S) 
 
 
 
Ejercicio 1:  = {0, 1} 
L1 = {w  
*
 tq cant1(w) es par} 
 L2 = {w  
*
 tq 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 = <{q0, q1}, {a, b}{a, b, B}, q0, > 
 
Hay que demostrar que Mf siempre se detiene y que 
w  L1  M f(w)  L2 
 
1) Mf siempre se detiene: claramente sí, pues solamente ejecuta un 
movimiento. 
q0 
B  (1, S) 
q1 
 
0  (1, S) 
1  (0, S) 
 
2) w  L1  M f(w) L2 ? 
 
Claramente si w comienza con 1 entonces cant1(M f(w)) = cant1(w) – 1, 
y si w no comienza con 1 cant1(M f(w)) = cant1(w) + 1. Por lo tanto 
 
a) Si w  L1  cant1(w) es par  cant1(Mf(w)) es impar  Mf(w)  L2 
b) Si w  L1  cant1(w) es impar  cant1(M f(w)) es par  Mf(w)  L2 
 
De a) y b) se tiene que w  L1  M f(w)  L2. 
 
Ejercicio 2: Sean L1 = {w  {0, 1}
*
 tq cant1(w) es par} 
 L2 = {w  {0, 1}
*
 tq cant1(w) = 1} 
 
Demostrar que L1  L2. Es decir construir M f(w) tal que 
w  L1  M f(w)  L2 
 
Habría que demostrar que Mf se detiene y que w  L1  M f(w)  L2. 
q0 
1  (B, D) 
0  (B, D) 
B  (1, S) 
q1 
q2 
1  (B, D) 
0  (B, D) 
Ejercicio 3: Sea L un lenguaje recursivo (L  R) y 
L1 = {<M> tq <M> es un cód. válido de MT, L(M) = L y M 
siempre se detiene} 
 L2 = {<M> tq <M> es un cód. válido de MT y 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 <M>  L1  M f(<M>)  L2 
Se construye Mf que trabaja de la siguiente manera: Si <M> no es un 
código válido de MT Mf se detiene sin hacer nada. De lo contrario 
recorre todas las quíntuplas de <M>, si en la 3ra posición encuentra qA lo 
reemplaza por qR, si encuentra qR lo reemplaza por qA. 
Nuevamente hay que demostrar que Mf se detiene y que: 
<M>  L1  M f(<M>)  L2. 
1) Mf siempre se detiene porque la entrada es finita. 
 
2) <M>  L1  M f(<M>)  L2. 
a) <M>  L1  M f(<M>)  L2? Si <M>  L1  L(M) = L  
si w  L  M para en qA  Mf(<M>) para en qR para la misma entrada 
si w  L  M para en qR  Mf(<M>) para en qA para la misma entrada 
por lo tanto M f(<M>) acepta L  M f(<M>)  L2. 
 
b) Se demuestra similarmente que <M>  L1  M f(<M>)  L2 . 
Además considérese que si <M> es un código inválido no pertenece a L1 
y M f(<M>) tampoco pertenece a L2 
 
Por lo tanto <M>  L1  M f(<M>)  L2. 
 
 
Nota: si L1  L2 significa que se puede construir una MT que acepte L1 a 
partir de la MT que acepta L2. 
Debe quedar claro que “en cierto sentido” L1 no puede ser más difícil 
computacionalmente que L2 porque se puede utilizar L2 para resolver L1. 
 
 
 
 
 Mf w 
 f(w) 
 M2 
 qA 
 qR 
 M1