Kartierung von Reduktionen von R zu Re

Question

Lassen Sie $ l_1 $ etwas Sprache in $ R $ sein.Lassen Sie $ l_2 $ etwas Sprache in $ RE $ sein.Ist es notwendigerweise das? $ l_1 \ leq_m l_2 $ ? Ich weiß, dass für nicht triviale $ l_1 $ , $ l_1 $ in $ R $ Es ist richtig zu sagen, dass $ l_1 \ leq_m l_2 $ . Aber ich kann den ersten Fall nicht beweisen.

und eine andere Frage: Ich bin fast sicher, dass das Folgende trifft, obwohl ich nicht im Internet Bezug genommen habe: Die Identitätsfunktion ist eine Mapping-Reduktion von $ \ EleseSet $ bis $ \ EleseSet $ .

Answer 1

wenn $ l_2 \ neq \ sigma ^ * $ und $ l_2 \ neq \ emesyset $ dann $ l_1 \ in r $ und $ l_2 \ in RE $ impliziert $ l_1 \ le_m l_2 $ .

$ T $ Seien Sie eine Turing-Maschine, die $ l_1 $ entscheidet. Lassen Sie $ A, B \ in \ Sigma ^ * $ so, dass $ a \ in l_2 $ und < Span-Klasse="Math-Container"> $ b \ nicht \ in l_2 $ . Für $ x \ in \ Sigma ^ * $ , definieren $ \ phi (x)= \ begin {cases} A & \ Text {Wenn $ T (x) $ akzeptiert \\ \\ B & \ Text {Wenn $ T (x) $ ablehnt} \ ENDE {Hüllen} $ . Es ist einfach zu überprüfen, ob $ \ phi $ eine Zuordnungsreduzierung von $ l_1 $ bis $ l_2 $ .

wenn $ l_2=sigma ^ * $ dann $ l_1 \ in r $ und $ l_2 \ in RE $ Impliziert nicht $ l_1 \ le_m l_2 $ . < / p>

Dies ist zu sehen, z. B. indem Sie $ l_1=Eleseetet $ wählen.

wenn $ l_2=emesyetet $ dann $ l_1 \ in r $ und < Span-Klasse="Math-Container"> $ l_2 \ in RE $ Impliziert nicht $ l_1 \ le_m l_2 $ . .

Dies ist zu sehen, z. B. durch Auswahl der $ l_1=Sigma ^ * $ .