300CIG007Computabilidad y Lenguajes Formales: Teoría de la Computabilidad: Decidibilidad
Pontificia Universidad Javeriana Cali
Ingenieria de Sistemas y Computación
Prof. Gloria Inés Alvarez V.
Lo indecidible
Porque es importante estudiar problemas indecidibles?
Saber que un problema es indecidible, permite darse cuenta que el problema debe ser simplificado o alterado para encontrar una solución computacional.
Conocer las capacidades y limitaciones de la computación, da una perspectiva importante sobre la misma
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Relación entre problemas ylenguajesVamos a representar los problemas computacionales
mediante lenguajes formales.
Sea ADFA
={<B,w> | B es un DFA y w una cadena}
Ver si el autómata B acepta la cadena w, es lo mismo que determinar si <B,w> pertenece al lenguaje A
DFA
Mostrar que el lenguaje es decidible es lo mismo que mostrar que el problema lo es.
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
ADFA = { <B, w> | B es un DFA que acepta la cadena w } es decidible
M decide ADFA
M = “Con la entrada <B, w>, donde B es un DFA y w una cadena:1. Simule B con la entrada w2. Si la simulación termina en un estado de aceptación, acepte, sinó rechazar”
B se representa con sus componentes B = (Q, ∑, Γ, δ, q0,F)M empieza verificando la codificación de B, si no es correcta rechazaM lleva el control del estado actual de B, y de la posición sobre la
cadena de entrada, iniciando en q0, y en el extremo izquierdo de w
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
ANFA = { <B,w> | B es un NFA que acepta la cadena w } es decidible
ANFA representa el problema de verificar cuando un NFA B acepta
una cadena w.
M decide ANFA
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
ANFA = { <B,w> | B es un NFA que acepta la cadena w } es decidible
ANFA representa el problema de verificar cuando un NFA B acepta
una cadena w.
M decide ANFA
M = “Con la entrada <B, w>, donde B es un NFA y w una cadena:1. Convierta el NFA B en un DFA equivalente C2. Simule C con la entrada w3. Si la simulación termina en un estado de aceptación, acepte. Si no, rechace”
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
AREX = { <R,w> | R es una expresión regular que genera la cadena w } es decidible
AREX representa el problema de verificar cuando una expresión
regular R genera la cadena w.
M decide AREX
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes DecidiblesAREX = { <R,w> | R es una expresión regular que genera la
cadena w } es decidible
AREX representa el problema de verificar cuando una expresión
regular R genera la cadena w.
M decide AREX
M = “Con la entrada <R, w>, donde R es una Expresión Regular y w una cadena:1. Convierta el R en un DFA equivalente A2. Simule A con la entrada w3. Si la simulación termina en un estado de aceptación, acepte. Si la simulación no termina en un estado de aceptación, rechace”
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
ACFG = { <G,w> | G es una CFG que genera la cadena w } es decidible
ACFG representa el problema de verificar cuando una Gramática
Libre de Contexto G genera la cadena w.
M decide ACFG
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Lenguajes Decidibles
ACFG = { <G,w> | G es una CFG que genera la cadena w } es decidible
M decide ACFG
M = “Con la entrada <G, w>, donde G es una CFG, y w es una cadena:2. Convierta G en una gramatica equivalente en Forma Normal de
Chomsky3. Liste todas las derivaciones con 2n-1 pasos, donde n = |w|, si n = 0
entonces lise las derivaciones con 1 paso4. Si alguna de estas derivaciones genera w, acepte, de lo contrario,
rechace ”
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Relación entre clases de lenguajes
Regulares
Incontext.Decidibles
Turing-reconocibles
Problemas que no tienen solución computacional
Dado un programa, y una especificación precisa de lo que el programa debe hacer, verificar que el programa realiza lo especificado: El problema general de la verificación del software no tiene solución computacional
Verificar si una máquina de Turing acepta una entrada dada:
ATM = { <M,w> | M es una TM y M acepta w }
ATM es indecidible (aunque es Turing-reconocible)
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Problema de la Parada
ATM = { <M,w> | M es una TM y M acepta w }
ATM es Turing-reconocible:U = “Con la entrada <M, w>, donde M es una TM, y w es una cadena:2. Simule M con la entrada w3. Si alguna vez M llega a un estado de aceptación, acepte; si M alguna
vez llega a un estado de rechazo, rechace ”
Si M entra en un loop con w, U no decide ATM, si U tuviese una forma de determinar cuando M no va a
detenerse, podría rechazar la entrada...
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Método de la Diagonalización
Propuesto por el Matemático George Cantor en 1873
Trata de medir (comparar) los tamaños de conjuntos infinitos: para determinar esto no es posible contar los elementos de los conjuntos
Una forma de comparar los tamaños de dos conjuntos, sin contar sus elementos, es crear parejas de elementos de uno y otro conjunto
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Método de la Diagonalización
Definición:Dados dos conjuntos A y B, y una función f : A → B, f es
una función de correspondencia biyectiva si cumple: Para todo a, c ∈ A, si a ≠ c, entonces f(a) ≠ f(c) (función
inyectiva, 1 a 1) Si para todo b ∈ B existe un a ∈ A, tal que f(a) = b
(función sobreyectiva)
Definición:Un conjunto A es contable, si es finito, o si tiene el mismo
tamaño que ℕ (el conjunto de los números naturales ℕ = { 1,2,3,4…} )
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Método de la Diagonalización
Ejemplos:
ℰ = { 2, 4, 6, 8…}, el conjunto de los números pares, es contable
L = { 0, 1 }* es contable
Q = { m/n : m, n ∈ }ℕ es contable
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
5/45/45/35/25/1
4/54/44/34/24/1
3/53/43/33/23/1
2/52/42/32/22/1
1/51/41/31/21/1
…4/11/33/11/22/11/1
…654321nf(n)
El Método de la DiagonalizaciónEjemplos: El conjunto potencia de un conjunto contable infinito, no es
contable, el conjunto potencia de ℕ no es contable.Por contradicción: Un elemento T del conjunto potencia puede ser representado con
una cadena de 0s y 1s, tal que un 1 aparece en la posición i, si y solo si i ∈ T. Ej 011001 representa el conjunto { 2, 3, 6 }
Si el conjunto potencia es contable, entonces se puede tener la siguiente matriz:
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Si el conjunto potencia es contable, entonces se puede tener la matriz
Si se toma la cadena de la diagonal, y se reemplaza cada 0 por 1, y cada 1 por 0, la nueva secuencia corresponde a un elemento del conjunto potencia, pero es diferente de todos los ti
0101t5
0011t4
1011t3
0011t2
0001t1
El Método de la Diagonalización
Ejemplos: ℝ, el conjunto de los números reales, No es contable:
No existe correspondencia entre ℝ y ℕ
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
56545.4
23492.3
5798.2
1413.1
n
Si el conjunto ℝ es contable, entonces se puede tener la matriz
Si se toma la cadena de la diagonal (iniciando después del punto decimal), y se reemplaza cada digito por uno diferente, se obtiene un número r entre 0 y 1, que se diferencia en 1 digito –al menos-, de cualquiera de los números de la matriz
r ∈ℝ, pero no tiene correspondencia con un f(n) para algún n.
El conjunto de todas las máquinas de Turing es contable
El conjunto de toda las cadenas de ∑* es contable
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El conjunto de todas las máquinas de Turing es contable
El conjunto de toda las cadenas de ∑* es contable ∑ es un conjunto finito Se puede listar las cadenas de longitud 0, longitud 1, longitud 2
….
El conjunto de todas las Máquinas de Turing es contable
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El conjunto de todas las máquinas de Turing es contable
El conjunto de toda las cadenas de ∑* es contable ∑ es un conjunto finito Se puede listar las cadenas de longitud 0, longitud 1, longitud 2
….
El conjunto de todas las Máquinas de Turing es contable
Cada MT puede estar codificada con una cadena M. Si se generan las cadenas, y se omiten aquellas que no son
codificaciones de MT, se obtiene una lista de MTs
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El conjunto de todos los Lenguajes sobre un alfabeto no es contable
Sea L el conjunto de todos los lenguajes sobre el alfabeto ∑ no es contable
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El conjunto de todos los Lenguajes sobre un alfabeto no es contable
Sea L el conjunto de todos los lenguajes sobre el alfabeto ∑ no es contable
∑ es un conjunto finito ∑* es un conjunto infinito El conjunto L es el conjunto potencia de ∑*
Entonces, el conjunto de todos los lenguajes puede ser puesto en correspondencia con el conjunto de todas
las máquinas de Turing?
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El conjunto de todos los Lenguajes sobre un alfabeto no es contable Sea L el conjunto de todos los lenguajes sobre el
alfabeto ∑ no es contable ∑ es un conjunto finito ∑* es un conjunto infinito El conjunto L es el conjunto potencia de ∑*
Entonces, el conjunto de todos los lenguajes puede ser puesto en correspondencia con el conjunto de todas
las máquinas de Turing?
Entonces algunos lenguajes No son reconocidos por Máquinas de Turing….?
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Existen lenguajes que no son Turing-reconocibles Al aparear cada máquina de Turing con el
lenguaje que reconoce van a sobrar lenguajes
Para esos lenguajes no hay una máquina que los reconozca
Decir que no son Turing-reconocibles, es decir que no existe un algoritmo que los solucione.
Teorema: El Problema de la Parada es Indecidible
ATM = { <M,w> | M es una TM y M acepta w }
Por contradicción, asumimos que ATM es decidible,Entonces existe un H que es una TM:
acepta si M acepta wH (<M,w>) rechaza si M no acepta w
Si además creamos una TM D, que tiene H como subrutina, y ejecuta H para determinar que hace M con su propia descripción (H(<M, <M>>), pero entrega el resultado opuesto:
acepta si M no acepta <M>D (<M>) rechaza si M acepta <M>
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Problema de la Parada es Indecidible
acepta si M no acepta <M>D (<M>) rechaza si M acepta <M>
Que sucede cuando se ejecuta D (<D>) ?
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Problema de la Parada es Indecidible
acepta si M no acepta <M>D (<M>) rechaza si M acepta <M>
Que sucede cuando se ejecuta D (<D>) ?
H acepta <M, w> cuando M acepta w D rechaza <M> cuando M acepta <M> D rechaza <D> cuando D acepta <D>
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
El Problema de la Parada es Indecidible
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
acepta
acepta
<M4>
…
acepta
M4
acepta
M3
acepta
acepta
M2
acepta
acepta
M1
…<M3><M2><M1>Mi ( <Mj> )
…
…
?
<D>
…
…aceptaaceptarechaza
rechaza
D
rechaza
acepta
acepta
rechaza
<M4>
…
rechaza
aceptarechaza
M4
rechaza
rechaza
aceptaM3
rechaza
aceptaaceptaM2
aceptarechaza
aceptaM1
…<M3><M2><M1>
H (< Mi, <Mj> >)
Un lenguaje que no es Turing-reconocibleTeorema: Un lenguaje es decidible si y sólo si
es Turing reconocible y también lo es su complemento.
Demostración: Si A es decidible, entonces A y complemento
de A son reconocibles Si A y su complemento son reconocibles
entonces A es decidible M = “ Sobre la cadena w:
1. Ejecute M1 y M2 sobre w en paralelo2. Si M1 acepta, acepte. Si M2 acepta, rechace”
Un lenguaje que no es Turing-reconocibleCorolario:El complemento de ATM no es Turing
reconocible.
Demostración:Se ha mostrado que ATMno es Turing-decidible, y
también se ha mostrado que ATM es Turing-reconocible. Por el teorema anterior, necesariamente su complemento no puede ser reconocible.
Reducibilidad
Método 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 para resolver 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…
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
MINTM No es Turing-Reconocible
Si M es una máquina de Turing, la longitud su descripción <M>, es el número de símbolos de <M>. M es minima si no existe otra máquina de Turing equivalente a M con una descripción más corta.
MINTM = { <M> : M es una TM Mínima }
Teorema: MINTM No es Reconocible por una Máquina de Turing
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
MINTM No es Turing-Reconocible
Demostración: por contradicción Asumimos que alguna TM E enumera MINTM, y
llegamos a una contradicción
C = “con la entrada w:1. Obtenga la descripción <C> (Teorema de la
Recursión*)2. Ejecute el enumerador E hasta que genere una máquina
D con una descripción de longitud mayor que <C>.3. Simule D con la entrada w.”
* Una máquina de Turing que ignora la entrada e imprime una copia de su propia descripción, y luego ejecutar su propia descripción
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
MINTM No es Turing-Reconocible
Demostración: por contradicción. Asumimos que alguna TM E enumera MINTM, y
llegamos a una contradicción
C = “con la entrada w:1. Obtenga la descripción <C> (Teorema de la Recursión)2. Ejecute el enumerador E hasta que genere una máquina D con una
descripción de longitud mayor que <C>.3. Simule D con la entrada w.”
Contradicción: C es equivalente a D, pero la longitud de <C> es menor que la longitud de <D>
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
HALTTM No es Decidible
HALTTM = { <M, w> : 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 es decidible
Si R es una TM que decide HALTTM , construimos S:
S = “con la entrada <M,w>:1. Ejecuta R con la entrada <M,w>2. Si R rechazó, entonces rechaza 3. Si R aceptó, entonces simula M con w hasta que se detiene,4. Si M aceptó, entonces acepta; si M rechazó, entonces rechaza.”
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Algunas propiedades
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
UDUUDEl complemento de L, es del mismo tipo?
UUUDDEs L = R? (R es Regular)
UUUUDEs L1 ⊆ L2?
UUU?DEs L1 = L2?
UUUDDEs L = ∑*?
UUDDDEs L = Φ?
UDDDDw ∈ L?
Conjuntos R. E.
Conjuntos Recursivos
CFL’sDCFL’sConjuntos Regulares
D = Decidible; U = indecidible; ? = respuesta desconocida
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:
wi1wi2
wi3…wim
= xi1xi2
xi3…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í:
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
010111xiB
10101111wiA
321i Hay una solución:m=4, i1=2, i2=1, i3=1, i4=3
w2w1w1w3=x2x1x1x3=101111110
Ejemplo: Sea el ∑ = { 0, 1 }, y A, B definidos así:
01111101xiB
10101110wiA
321iNo hay solución
PCP No es Decidible
Demostración: Por contradicción: Si PCP fuese decidible, ATM seria
decidible.
Crearemos una versión modificada de PCP: MCPC. MPCP: dadas dos 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 = x1xi2
xi3…xim
Si MPCP es decidible, entonces PCP es decidible, ya que PCP es una reducción de MPCP
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
PCP No es Decidible
Demostración:
Reducimos ATM a MPCP, así: Para cada <M, w> construimos una instancia de
MPCP, que si tiene solución, tiene una que empieza con qow, y genera una cadena
# qow#α1qiβ1#...#αkqkβk#Donde: qk es un estado final (aceptación o rechazo) Las subcadenas entre #...# son pasos sucesivos de la
computación de M con la entrada w.
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
PCP No es DecidibleDemostración: MPCP se construye así:
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Para todo q ∈ F#q##Grupo IV
qqY
qXq
qXqYGrupo III: Para todo q ∈ F,
X,Y ∈ Γ
δ(q, □)=(p,Y,L)pZY#Zq#
δ(q,□)=(p,Y,R)Yp#q#
δ(q,X)=(p,Y,L)pZYZqX
δ(q,X)=(p,Y,R)YpqXGrupo II: Para todo q ∈ Q-F,
p ∈ Q,
X,Y,Z ∈ Γ
##
Para cada X ∈ ΓXXGrupo I
# qow##Primera Cadena
Lista BLista A
PCP No es DecidibleDemostración:
Si M inicia en q0w, y alcanza un estado de aceptación, entonces la instancia de MPCP con las listas A y B tiene una solución. Si M no alcanza un estado de aceptación, no hay solución posible para MPCP (la cadena que se forma con la lista B excede en longitud a la que se forma con la lista A).
Entonces, la instancia de MPCP tienen solución si y solo si M con la entrada w llega a un estado de aceptación.
Por lo tanto, si hubiese un algoritmo para solucionar MPCP habria un algoritmo para reconocer ATM, lo cual es una contradicción.
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Aplicación de PCP
Para demostrar que el problema de determinar si una gramática libre de contexto es ambigua es indecidible. [Hopcroft]
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón
Otros Problemas No Decidibles
El problema No. 10 de Hilbert: 10. Determination of the solvability of a Diophantine equation.
El problema de la verificación formal de programas (dada una especificación verificar si un programa la cumple), es indecidible.
El problema de determinar cuando una formula de lógica matemática(*) es verdadera o falsa, es indecidible.
(*) Incluye símbolos and, or, not, y cuantificadores para todo, existe…
Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 – Prof. Ma. Constanza Pabón