Ist es richtig zu sagen, dass l ist, wenn ich von LH nach LH nach LH zuordnen kann?

Question

Ich scheine nicht richtig zu verstehen, welche Reduktionen für Sprachen bedeutet.

lasst zum Beispiel sagen, dass es eine Sprache namens lm gibt.

Ich möchte sehen, ob lm rekursiv ist oder nicht, um zu tun, dass ich sagen kann, dass ich eine Reduzierung von L-Halt-Problem auf lm finde.

Und ich gehe davon aus, dass LM rekursiv ist, also zeige ich, dass das L-Halting-Problem auch rekursiv ist, was natürlich falsch ist, daher ist daher LM nicht rekursiv ist.

Kann ich aber sagen, dass LM ist, weil ich einen Weg gefunden habe, um LH auf LM zu reduzieren? Wenn nicht, wie kann ich zeigen, dass lm re ist?

Answer 1

Lassen Sie uns ein wenig klarstellen, da es viele Äquivalent / ähnliche Definitionen gibt, die zu Missverständnissen führen können.

.

• Sie können zeigen, dass eine Sprache $ L $ rekursiv ist, indem Sie eine rekursive Funktion $ \ chi_l $ (oder eine Turing-Maschine oder ein anderes äquivalentes Rechenmodell), das es entscheidet, dh $$ \ chi_l (x)=beginnen {Hüllen} 1 & \ Quad; x \ in l \\ 0 & \ Quad; \ text {otw}. \ ENDE {Hüllen} $$ Beachten Sie, dass $ \ chi_l $ für alle Eingänge definiert werden muss.

• Sie können eine dieser Sprache anzeigen $ L $ ist nicht rekursiv, indem Sie eine "Turing Reduction" von einem Nichts finden -Recursive Sprache dafür. Dies ist wahrscheinlich das, was Sie mit der Reduktion meinen, und es ist wie folgt definiert:

  Wir sagen, dass eine Sprache $ A $ turreth, auf eine Sprache, die $ B $ ist, Geschriebene $ a \ le_t b $ , wenn wir eine rekursive Funktion (oder Turniermaschine) erstellen können, die $ A $ < / span> Durch Annahme, dass es eine solche Funktion für $ B $ gibt.

  Wie Sie einmal definitionsgemäß sehen, der Turing-Reduktion irgendwie "Transfers Recursivität" von $ B $ bis $ A $ .

  für jeden $ a $ und $ B $ so, dass $ A \ leq_t b $ , wenn $ B $ rekursiv ist, ist dies also $ A $ .

  somit, wenn wir bereits wissen, dass einige $ A $ nicht rekursiv ist, und findet eine Reduktion $ a \ leq_t b $ für jeden $ b $ macht es auch nicht rekursiv.

• Sie können zeigen, dass eine Sprache $ L $ ist re, indem Sie eine rekursive Funktion $ \ varphi_l $ (oder Turing-Container), dass $ dom (\ varphi_l)= l $ (oder stoppt auf / akzeptiert es), beispielsweise $$ \ varphi_l (x)=beginnen {Hüllen} 1 & \ Quad; X \ in L \\ \ Uparrow & \ Quad; \ text {otw.} \ ende {cases} $$

  wo $ \ Uparrow $ bedeutet "nicht definiert" (oder "nicht hält). Es gibt andere Definitionen von Re-Ness, wie seine Namensscheine "Enumerability", die Sie leicht beobachten können, die diesem entsprechen.

• aber beim Zeigen einer Sprache $ L $ ist nicht re, Turing Reduktion hilft nicht, da dies nicht unbedingt erforderlich ist Übertragen von Re-Ness. Aktivieren Sie zum Beispiel, dass $ \ Overline {l_ {Halt}} \ leq_t l_ {halt} $ (in der Tat jede Sprache ist, dass sie ergänzend ist, und umgekehrt), Aber wir wissen, dass $ l_ {halt} $ ist, während $ \ Overline {l_ {halt}} $ ist nicht.

  Aber es gibt andere Arten von stärkerer -Ding-Reduktion, die die Re-Ness übertragen. Eine solche Reduktion wird als "viele-one-Lösbarkeit" bezeichnet:

  Wir sagen, dass eine Sprache $ A $ viele-one-reduktible zu einer Sprache $ B $ , geschrieben $ a \ leq_m b $ , wenn es eine totale rekursive Funktion gibt $ F $ so, dass das Für jeden Eingang $ x $ $$ x \ in A \ iff f (x) \ in B $$

  Dies ist eine stärkere -Rinderung in dem Sinne, dass $ a \ leq_m b $ impliziert $ A \ leq_t b $ (und nicht unbedingt umgekehrt). Also, wie die Turing-Reduktion, überträgt sie die Rekursivkraft. Wir haben auch

  für jeden $ a $ und $ B $ so, dass $ A \ leq_m b $ , wenn $ B $ ist, ist dies also $ A $ .

  Um zu sehen, wie dies wahr ist, nehmen Sie einfach $ \ varphi_a (x)=varphi_b (f (x)) $ .

  Daher ist die richtige Methode, um eine Sprache zu zeigen $ B $ ist nicht neu, ist, eine vieles-one-Reduktion zu finden $ A \ leq_m b $ für einige nicht-re-sprache $ a $ . Beachten Sie, dass das obige Beispiel hier nicht funktioniert, da $ \ Overline {l_ {Halt}} \ nleq_m l_ {halt} $ .

Für weiteres Lesen, siehe

l="nofollow noreferrer"> ccccess theorie von s.Barry Cooper pt.I, ch.7.