Indecibilidad

Introducción a la indecidibilidad
José M. Sempere Departamento de Sistemas Informáticos y Computación Universidad Politécnica de Valencia

Lenguajes y problemas
Un problema será considerado cualquier cuestión formulada en términos formales (matemáticos). Diremos que un problema es de decisión si su resolución implica la afirmación o negación de un predicado lógico. Existen otros tipos deproblemas que no son de decisión (p.ej. los problemas de optimización y los problemas de búsqueda). Un problema de decisión es decidible sii existe un algoritmo que lo resuelva (en caso contrario es indecidible)

Podemos asociar a cualquier problema (de decisión) un lenguaje formal de acuerdo con el siguiente esquema
codificación en Σ problema (parametrizado) instancia lenguaje

asignación deparámetros

codificación en un alfabeto predefinido Σ

El lenguaje asociado al problema Π, que denotaremos por LΠ, será formado por aquellas cadenas que codifican instancias del problema con solución afirmativa. Si el lenguaje asociado a un problema es recursivo entonces existe una MT que acepta el lenguaje y siempre para. La MT es el algoritmo de resolución del problema y el problema esdecidible. Todos los problemas con un número finito de instancias son decidibles (sus lenguajes asociados son finitos y, por lo tanto, recursivos).

Propiedades de cierre de los lenguajes recursivamente enumerables y recursivos

Teorema. Los lenguajes recursivos son cerrados bajo complementario
L=L(M1)
S (w ∈L(M1))

L=L(M2)
S N (w ∉L(M2))

w

M1
N (w ∉L(M1))

w

M1 M2
N S (w ∈L(M2))Teorema. Los lenguajes recursivos son cerrados bajo unión
L1=L(M1)
S (w ∈L(M1))

L2=L(M2)
S (w ∈L(M2))

w

M1
N (w ∉L(M1))

w

M2
N (w ∉L(M2))

S

S (w ∈L(M3)) S

w

M1 M3

N / activar M2

w

M2
N N (w ∉L(M3))

L(M3) = L(M1) ∪ L(M2) = L1 ∪ L2

Teorema. Los lenguajes recursivamente enumerables son cerrados bajo unión
L1=L(M1)
S (w ∈L(M1))

L2=L(M2)
S (w∈L(M2))

w

M1

w

M2

S

M1
w

S (w ∈L(M3))

M2 M3

S

activar simultáneamente M1 y M2 finalizar cuando finalicen M1 o M2 Si M1 o M2 paran y rechazan M3 no para

L(M3) = L(M1) ∪ L(M2) = L1 ∪ L2

Teorema. Los lenguajes recursivos son cerrados bajo intersección
L1=L(M1)
S (w ∈L(M1))

L2=L(M2)
S (w ∈L(M2))

w

M1
N (w ∉L(M1))

w

M2
N (w ∉L(M2))

N

N (w∉L(M3)) N

w

M1 M3

S / activar M2

w

M2
S S (w ∈L(M3))

L(M3) = L(M1) ∩ L(M2) = L1 ∩ L2

Teorema. Los lenguajes recursivamente enumerables son cerrados bajo intersección
L1=L(M1)
S (w ∈L(M1))

L2=L(M2)
S (w ∈L(M2))

w

M1

w

M2

S / activar M2

w

M1
w

M2

S

S (w ∈L(M3))

M3 L(M3) = L(M1) ∩ L(M2) = L1 ∩ L2
Si M1 o M2 paran y rechazan M3 no paraTeorema. Si un lenguaje L y su complementario son recursivamente enumerables entonces L es recursivo (y su complementario también)
L=L(M1)
S (w ∈L(M1))

L=L(M2)
S (w ∈L(M2))

w

M1

w

M2

S

M1
w

S (w ∈L(M3))

M2 M3

S

N (w ∉L(M3))

L(M3) = L(M1) = L

M3 para siempre y acepta L

Corolario Sea L un lenguaje arbitrario. Siempre se cumplirá una de las tres siguientesafirmaciones (a) L y su complentario son recursivos (b) Ni L ni su complementario son recursivamente enumerables (c ) L o su complementario es recursivamente enumerable pero no es recursivo, mientras que el otro lenguaje no es recursivamente enumerable.

C1 : ¿ Existen lenguajes que no sean recursivamente enumerables ? C2 : ¿ Existen lenguajes que sean recursivamente enumerables pero no recursivos ?El problema universal
Sea M una máquina de Turing arbitraria y w una cadena arbitraria. ¿acepta M la cadena w ?
Parámetros del problema: M, w Restricciones del problema: M = (Q, Σ, Γ, δ1, q0, B, F) F = { q2} Γ = { 0, 1, B } w ∈ (0+1)* (si el problema restringido es indecidible entonces el problema universal también lo es)

Codificación de máquinas de Turing: M = (Q, Σ, Γ, δ1, q1, B,...