Semi-decidibilidad del idioma $ \ Overline {l _ {\ epsilon}} $

Question

En primer lugar, considere el problema: dado $ l_h={r (m) w: m \ in tm_0, w \ in l (m) \ \ in l (m) \ \ en l (m) \} $ donde $ r (m) $ son transiciones codificadas de $ m \ en tm_0 $ . Supongamos para la contradicción $ \ overline {l_ {h}} $ es semi-decidible, entonces hay $ q \ en tm_0 $ con $ l (q)=overline {l_ {h}} $ Por lo tanto, para cada $ m \ en tm_0 $ tenemos lo siguiente $$ Q \ acepts \ Input \ R (M) W \ IFF M \ no \ IFF M \ no \ IFF M \ PUT \ w \ \ \ \ (1) $$ Luego construimos la máquina $ Z $ S.T. Duplica la entrada y ejecuta la máquina $ q $ . Observe lo siguiente para el $ m \ in tm_0 $ : \ begin {alignat *} {2} Z \ acepts \ Input \ R (M) & \ IFF Q \ acepts \ Input \ R (M) R (M) \\ & \ iff m \ no \ acept \ in ingreso \ r (m) \ End {alignat *} Tomar $ m= z $ nos dará una contradicción. Por lo tanto, $ \ Overline {l_ {h}} $ no es semi-decidible.

La misma técnica que estoy tratando de solicitar el caso $ l _ {\ epsilon}={r (m): m \ in tm_0 \ \ texto {s.t. $ M $ acepta $ \ epsilon $} \ _ $ donde $ r (m) $ son transiciones codificadas de $ M \ en tm_0 $ . Pero me enfrento a algunos problemas. Supongamos para la contradicción $ \ Overline {l _ {\ epsilon}} $ es semi-decidible, luego hay $ q \ en TM_0 $ con $ L (q)=overline {l _ {\ epsilon}} $ Por lo tanto, para cada $ M \ en tm_0 $ tenemos lo siguiente $$ Q \ acepts \ Input \ R (M) \ IFF M \ no es \ acept \ input \ \ epsilon $$ Luego, realmente no puedo encontrar realmente $ z $ para este caso, ya que duplicar la entrada simplemente no funcionará. Se aprecian cualquier sugerencia.

Answer 1

Asumir para la contradicción $ \ overline {l _ {\ epsilon}} $ es semi-decidible.Se ha demostrado fácilmente que $ l _ {\ epsilon} $ es semi-decidible por reducción al problema de detención, es decir, $ l_ {H} $ es semi-decidible.Si $ l _ {\ epsilon} $ y $ \ overline {l _ {\ epsilon}} $ son semi-Cidable, por lo tanto, $ l _ {\ epsilon} $ es decidible.Esta es una contradicción, como $ l _ {\ epsilon} $ , así como $ l_ {h} $ son semi-decidibles.

En esta prueba se utilizó la siguiente reclamación:

$ \ textbf {afirmacion:} \ text {si $ l $ y $ \ overline {l} $ son semi-decidibles, entonces $ l $ es decidible} $