Semi-decidibilidade da linguagem $ \ overline {l _ {\ epsilon}} $

Question

Primeiro, considere o problema: dado $ l_h= {r (m) w: m \ in tm_0, w \ in l (m)} $ onde $ r (m) $ são transições codificadas de $ m \ em tm_0 $ . Suponha para contradição $ \ overline {l_ {h}} $ é semi-decidível, então há $ \ em tm_0 $ com $ l (q)=overline {l_ {h}} $ portanto para cada $ m \ in tm_0 $ temos o seguinte $$ \ aceita \ entrada \ r (m) w \ \ \ \ \ não \ accept \ input \ w \ \ \ \ (1) $$ Em seguida, construímos máquina $ z $ s.t. Dobra a entrada e executa a máquina $ Q $ . Observe o seguinte para uma classe arbitrária $ m \ em TM_0 $ : \ begin {alignat *} {2} Z \ aceita \ entrada \ r (m) & \ iff \ aceita \ entrada \ r (m) r (m) \\ & \ iff m \ não \ accept \ entrada \ r (m) \ fim {alignat *} Tomando $ m= z $ nos cederá uma contradição. Assim, $ \ overline {l_ {h}} $ não é semi-decidível.

A mesma técnica que estou tentando solicitar o caso $ l _ {\ epsilon}={r (m): m \ in tm_0 \ text {s.t. $ M $ aceita $ \ epsilon $} \} $ onde $ r (m) $ são transições codificadas de $ M \ in tm_0 $ . Mas estou enfrentando alguns problemas. Assumir para contradição $ \ overline {l _ {\ epsilon}} $ é semi-decidível, então há $ q \ in Tm_0 $ com $ l (q)=overline {l _ {\ epsilon}} $ portanto para cada $ M \ in tm_0 $ temos o seguinte $$ \ aceita \ entrada \ r (m) \ \ \ \ \ \ \ não \ accept \ entrada \ \ epsilon $$ Então eu não consigo encontrar realmente apropriado $ Z $ para este caso, como duplicando a entrada simplesmente não funciona. Quaisquer sugestões são apreciadas.

Answer 1

Assuma para contradição $ \ overline {l _ {\ epsilon}} $ é semi-decidível.É facilmente provado que $ l _ {\ epsilon} $ é semi-decidível por redução ao problema da parada, ou seja, $ l_ {H} $ é semi-decidível.Se $ l _ {\ epsilon} $ e $ \ overline {l _ {\ epsilon}} $ são semi-Decidável, portanto $ l _ {\ epsilon} $ é decidível.Esta é uma contradição, como $ l _ {\ epsilon} $ , bem como $ l_ {h} $ são semi-decidíveis.

Neste comprovar a seguinte reivindicação foi utilizada:

.

$ \ textbf {reivindicar:} \ texto {se $ l $ e $ \ overline {l} $ são semi-decidíveis, então $ l $ é decidível} $