Welche unentschiedenswerte Sprache $ B $ ist für seine Ergänzung reduzierbar?

Question

Ich habe ein Problem begegnet, das ein Beispiel für ein nicht unentdeckbares Sprachen $ B $ B $ so bittet, dass $ B \ leq_m\ Overline {b} $ ...

Ich konnte es jedoch schwer finden, ein Beispiel zu konstruieren ... Meine Schwierigkeit ist, dass er eine unentdeckbare, aber turnierende erkennbare Sprache gegeben hat, sagen Sie $ A_ {TM} $ , seine Ergänzung $ \ Overline {A_ {TM}} $ ist nicht erkennbar und Loops.Wenn ich eine solche Sprache reduziere (sagen Sie $ x \ in A_ {TM} \ leq_m y \ in \ Overline {A_ {TM}} {_ {tm}} $ , die Instanz $ y \ in \ Overline {A_ {TM}} $ Kann nicht von keiner TM erkannt werden (seit per Definition $ \ Overline {A_{TM}} $ ist Looping) ...

Jede Hilfe?

Answer 1

$ H $ Seien Sie die Sprache aller Turing-Maschinen, die auf leeren Eingaben halten. Eindeutig $ H $ ist unentschlossen.

lass $ l={(1, t): t \ in h \ \ \ cup \ {(0, t): t \ nicht \ in h \} $ .

eindeutig $ l $ ist unentschlossen. Wenn $ L $ entschieden wurden, dann eine Turing-Maschine $ M $ für $ L $ würde auch das Vorhandensein einer Turing-Maschine $ M '$ implizieren, die entscheidet, dass $ H $ . $ M '$ mit input $ T $ Simuliert einfach $ M $ mit input $ (1, t) $ .

mehr für eine Turing-Maschine $ T $ und $ x \ in \ {0,1 \} $ < / span> wir haben: $$ (x, t) \ in l \ iff (1-x, t) \ nicht \ in l \ iff (1-x, t) \ in \ Overline {l}. $$

Dies, kombiniert mit der Tatsache, dass wir entscheiden können, ob ein gegebenes Wort eine gültige Turierungsmaschine kodiert, zeigt, dass $ L $ für $ \ Overline {l} $ .