Teoria de automatas

300CIG007

Computabilidad y Lenguajes Formales: Teoría de la Computabilidad: Reducibilidad
Pontificia Universidad Javeriana Cali Ingenieria de Sistemas y Computación Prof. Gloria Inés Alvarez V.

Reducibilidad


Es un metodo para probar que los problemas son indecidibles. Reducir es convertir un problema en otro, de tal forma que la solución del segundo problema pueda ser usada pararesolver el primero. También sucede en la vida diaria…ejemplo: el “problema” de venir esta mañana a la U…se reduce al problema de tener transporte… que se puede reducir al problema de tener el dinero para pagar un pasaje en bus…
Prof. Ma. Constanza Pabón





Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Reducibilidad para probar indecidibilidadCuando el problema A se reduce al problema B:  Si existe solución para B, entonces tambien hay solución para A.  La solución de A no puede ser más difícil que la solución de B.  Si B es decidible, A tambien lo es.  Si A es indecidible, B tambien lo es.

Estrategia de Demostración




Para mostrar que un problema es indecidible, se debe mostrar que otro problema, que ya se sabeindecidible, reduce a el. En otras palabras, mostrar que si existiera una MT que decidiera este problema, podríamos decidir un problema que se sabe indecidible

A continuación veremos algunos ejemplos.

HALTTM es Indecidible
HALTTM = { : M es una TM, y M se detiene para toda entrada w } Demostración: por contradicción. Asumimos que alguna HALTTM es decidible y lo usamos para demostrar que ATM esdecidible Si R es una TM que decide HALTTM , construimos S: S = “con la entrada :
1. 2. 3. 4.

Ejecuta R con la entrada Si R rechazó, entonces rechaza Si R aceptó, entonces simula M con w hasta que se detiene, Si M aceptó, entonces acepta; si M rechazó, entonces rechaza.”
Prof. Ma. Constanza Pabón

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

ETM esIndecidible
E = { | M es una MT y L(M) es vacío }

Algunas propiedades
Conjuntos Regulares DCFL’s CFL’s Conjuntos Recursivos Conjuntos R. E.

w ∈ L? Es L = Φ? Es L = ∑*? Es L1 = L2? Es L1 ⊆ L2? Es L = R?
(R es Regular) El complemento de L, es del mismo tipo?

D D D D D D D

D D D ? U D U

D D U U U U U

D U U U U U D

U U U U U U U

D = Decidible; U = indecidible; ? = respuestadesconocida
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón

PCP No es Decidible
 

PCP: El problema de Correspondencia de Post Una instancia de PCP consiste de dos listas de cadenas sobre algún alfabeto ∑: A = w1, w2, w3,…, wk B = x1, x2, x3,…, xk



La instancia de PCP tiene solución si hay una secuencia de enteros tales que:wi1wi2wi3…wim = xi1xi2xi3…xim La secuencia i1, i2, i3, …, im es una solución a la instancia de PCP

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

PCP
Ejemplo: Sea el ∑ = { 0, 1 }, y A, B definidos así:
i A wi 1 1 2 10 3 0

10111 10

B xi 111

Hay una solución: m=4, i1=2, i2=1, i3=1, i4=3 w2w1w1w3=x2x1x1x3=101111110Ejemplo: Sea el ∑ = { 0, 1 }, y A, B definidos así:
i 1 2 3

A wi 10 011 101 B xi 101 11 011

No hay solución

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

PCP es Indecidible
Demostración:  Por contradicción: Si PCP fuese decidible, ATM seria decidible.
 

Crearemos una versión modificada de PCP: MCPC. MPCP: dadasdos listas de cadenas A y B sobre un alfabeto ∑, la solución de MPCP es una lista de enteros 1, i2, i3, …, im, tal que w1wi2wi3…wim = x1xi2xi3…xim Si MPCP es decidible, entonces PCP es decidible, ya que PCP es una reducción de MPCP
Prof. Ma. Constanza Pabón



Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

PCP es Indecidible
Demostración:
 ...