Semi-Entschlossenheit der Sprache $ \ Overline {l _ {\ epsilon}} $

Question

Betrachten Sie zunächst das Problem: Angegeben $ l_h={r (m) w: m \ in tm_0, w \ in l (m) \} $ wo $ r (m) $ sind codierte Übergänge von $ m \ in TM_0 $ . Angenommen, für den Widerspruch $ \ Overline {l_ {h}} $ ist semi-degable, dann gibt es $ q \ in TM_0 $ mit $ l (q)=Overline {l_ {h}} $ Daher für jeden $ m \ in TM_0 $ Wir haben folgende $$ q \ Akzeptiert \ Input \ R (M) W \ IFF M \ NICHT \ Akzeptieren \ Input \ W \ \ \ \ (1) $$ Dann konstruieren wir Maschine $ Z $ s.t. Verdoppelt die Eingabe und läuft Maschine $ q $ . Beachten Sie Folgendes für willkürliche $ m \ in TM_0 $ : \ beginnen {Alignat *} {2} Z \ Akzeptiert \ Input \ R (M) & \ IFF \ Akzeptiert \ input \ r (m) r (m) \\ & \ iff m \ nicht \ akzeptiert \ input \ r (m) \ end {alignat *} Wenn Sie $ M= Z $ nehmen, wird uns ein Widerspruch ergeben. Daher ist $ \ Overline {l_ {h}} $ nicht halb entschlossen.

Dieselbe Technik, die ich versuche, sich für den Fall zu bewerben $ l _ {\ Epsilon}={r (m): m \ in tm_0 \ \ text {s.t. $ M $ akzeptiert $ \ Epsilon $} \} $ Wobei $ r (m) $ codierte Übergänge von $ M \ in tm_0 $ . Aber ich bin mit einigen Problemen konfrontiert. Angenommen, für Widerspruch $ \ Overline {l _ {\ epsilon}} $ ist semi-entschlossen, dann gibt es $ q \ in Tm_0 $ mit $ l (q)=Overline {l _ {\ epsilon}} $ für jeden $ M \ in TM_0 $ Wir haben folgende $$ q \ Akzeptiert \ Input \ R (m) \ IFF M \ NICHT \ Akzeptieren \ Input \ Epsilon $$ Dann kann ich nicht wirklich geeignete $ Z $ für diesen Fall finden, da sich der Eingang verdoppelt, einfach nicht funktioniert. Alle Vorschläge werden geschätzt.

Answer 1

Annehmen für Widerspruch $ \ Overline {l _ {\ Epsilon}} $ ist semi-entschlossen.Es ist leicht zu beweisen, dass $ l _ {\ epsilon} $ von der Reduktion auf das Halteproblem, dh $ l_ {H} $ ist semi-entschlossen.Wenn $ l _ {\ epsilon} $ und $ \ Overline {l _ {\ epsilon}} $ SEMI- Dauerreich, daher $ l _ {\ Epsilon} $ ist entschieden.Dies ist ein Widerspruch, als $ l _ {\ epsilon} $ sowie $ l_ {h} $ sind halb entschlossen.

In diesem Beitrag wurde der folgende Anspruch verwendet:

$ \ textbf {claim:} \ Text {if $ L $ und $ \ Overline {l} $ sind semi-entschlossen, dann ist $ L $ entschieden} $