Page 108 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 108
108
Además: L es recursivamente enumerable si y sólo si existe una máquina de Turing M tal que
para todo W ∈ A∗: W ∈ L si y sólo si MT se detiene con entrada W.
Problemas decidibles versus problemas recursivamente enumerables
Teorema: si un lenguaje es decidible entonces es recursivamente enumerable.
Además, existen lenguajes recursivamente enumerables y no decidibles, el conjunto universal (U)
sería un ejemplo, porque si el universal son recursivamente enumerables y allí están los recursivos
(que pueden ser vistos como un subconjunto o su complemento) entonces el resto dl universal no
será decidibles. Existe un teorema de reducción que permiten demostrar estas afirmaciones, pero
no vamos a entrar allá.
