Semi-dette de la langue $ \ Overline {l _ \ \ epsilon}} $

Question

Prenez d'abord considérer le problème: donné $ l_h={r (m) w: m \ in tm_0, w \ in l (m) \ \} $ $ r (m) $ sont codés des transitions de $ m \ in tm_0 $ . Supposons une contradiction $ \ overline {l_ {h}} $ est semi-décitable, alors il y a $ q \ in tm_0 $ avec $ l (q)=overline {l_ {h}} $ donc pour chaque M $ M \ in tm_0 $ nous avons ce qui suit $$ q \ accepte \ entrée \ r (m) w \ iff m \ ne pas \ accepter \ entrée \ w \ \ \ \ (1) $$ Ensuite, nous construisons la machine $ Z $ s.t. Double l'entrée et exécute la machine $ q $ . Observez ce qui suit pour le $ M \ in tm_0 $ : \ commence {alignat *} {2} Z \ accepte \ entrée \ r (m) & \ iff q \ accepte \ entrée \ r (m) r (m) \\ & \ iff m \ ne \ pas \ accepter \ entrée \ r (m) \ fin {alignat *} Prenant $ m= z $ nous donnera une contradiction. Par conséquent, $ \ Overline {l_ {h}} $ n'est pas semi-décidable.

La même technique que j'essaie de postuler pour l'affaire $ l _ {\ epsilon}={r (m): m \ in tm_0 \ \ text {s.t. $ M $ accepte $ \ epsilon $} \} $ où $ r (m) $ sont codés de transitions de $ M \ in tm_0 $ . Mais je suis confronté à des problèmes. Supposez-vous pour la contradiction $ \ overline {l _ {\ epsilon}} $ est semi-décitable, alors il y a $ q \ in Tm_0 $ avec $ l (q)=overline {l _ {\ epsilon}} $ donc pour chaque $ M \ in tm_0 $ nous avons ce qui suit $$ q \ accepte \ entrée \ r (m) \ iff m \ ne pas \ Accepter \ entrée \ \ epsilon $$ Ensuite, je ne peux pas vraiment trouver approprié $ z $ pour ce cas, car doubler, l'entrée ne fonctionnera tout simplement pas. Toute suggestion est appréciée.

Answer 1

suppose de contradiction $ \ overline {l _ {\ epsilon}} $ est semi-décitable.Il est facilement prouvé que $ l _ {\ epsilon} $ est semi-décitable par réduction du problème d'arrêt, c'est-à-dire $ l_ {H} $ est semi-décitable.Si $ l _ {\ epsilon} $ et $ \ overline {l _ {\ epsilon}} $ sont semi-Decidable, donc $ l _ {\ epsilon} $ est décembre.C'est une contradiction, comme $ l _ {\ epsilon} $ ainsi que $ l_ {h} $ sont semi-décidables.

Dans ce prouve, la revendication suivante a été utilisée:

$ \ textbf {réclamation:} \ texte {si $ l $ {$ \ overline {l} $ est semi-décitable, puis $ l $ est décritable} $