Semi-decidabilità della lingua $ \ overline {l _ {\ epsilon}} $

Question

Prima considerare il problema: data $ l_h={r (m) w: m \ in tm_0, w \ in l (m) \} $ dove $ R (M) $ Le transizioni codificate di $ m \ in tm_0 $ . Supponiamo per contraddizione $ \ overline {l_ {h}} $ è semi-decidabile, quindi c'è $ q \ in tm_0 $ con $ l (q)=overline {l_ {h}} $ Pertanto per ogni $ m \ in tm_0 $ Abbiamo quanto segue $$ Q \ Accetti \ INPUT \ R (M) W \ IFF M \ non \ non \ accetta \ Input \ w \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Quindi costruiamo la macchina $ z $ s.t. Raddoppia l'ingresso e le esecuzioni della macchina $ Q $ . Osservare quanto segue per arbitrario $ m \ in tm_0 $ : \ Begin {alignat *} {2} Z \ accetti \ input \ r (m) e \ iff q \ accetti \ input \ r (m) r (m) \\ & \ IFF M \ non \ non \ accetta \ Input \ r (m) \ end {alignat *} Prendendo $ m= z $ ci produrrà una contraddizione. Quindi, $ \ overline {l_ {h}} $ non è semi-decidabile.

La stessa tecnica che sto cercando di richiedere il caso $ l _ {\ epsilon}={r (m): m \ in tm_0 \ \ text {s.t. $ M $ Accetta $ \ Epsilon $} \} $ dove $ r (m) $ Le transizioni codificate di $ M \ in tm_0 $ . Ma sto affrontando alcuni problemi. Assumere per contraddizione $ \ overline {l _ {\ epsilon}} $ è semi-decidabile, allora c'è $ Q \ in Tm_0 $ con $ l (q)=overline {l _ {\ epsilon}} $ Pertanto per ogni $ M \ in tm_0 $ Abbiamo quanto segue $$ Q \ Accetti \ INPUT \ R (M) \ IFF M \ non \ non \ Accetta \ Input \ \ Epsilon $$ Quindi non riesco davvero a trovare appropriato $ z $ per questo caso, come raddoppiando l'ingresso semplicemente non funzionerà. Eventuali suggerimenti sono apprezzati.

Answer 1

Supponiamo per contraddizione $ \ overline {l _ {\ epsilon}} $ è semi-decidabile.È facilmente dimostrato che $ l _ {\ epsilon} $ è semi-decidabile per riduzione del problema di fermezza, ovvero $ l_ {H} $ è semi-decidabile.Se $ l _ {\ epsilon} $ e $ \ overline {l _ {\ Epsilon}} $ sono semi-Decidable, quindi $ l _ {\ epsilon} $ è decidabile.Questa è una contraddizione, come $ l _ {\ epsilon} $ così come $ l_ {h} $ sono semi-decidabili.

In questo dimostra il seguente reclamo è stato utilizzato:

.

$ \ textbf {reclamo:} \ text {se $ l $ e $ \ overline {l} $ sono semi-decidabili, quindi $ L $ è decidabile} $