Mapping-Reduktionen Komplement von A$_{TM}$
-
16-10-2019 - |
Frage
Ich habe eine Allgemeine Frage zur Zuordnung von Ermäßigungen.Ich habe gesehen, einige Beispiele der Reduzierung der Funktionen auf $A_{TM}$
wobei $A_{TM} = \{\langle M, w angle : ext{ Für } M ext{ ist eine turing-Maschine, die akzeptiert string } w\}$
das ist toll für den Nachweis der nicht-entscheidbarkeit.Aber sagen will ich beweisen Unkenntlichkeit statt.Das heißt, ich verwenden möchten die logische Folge gegeben, dass $A \le_{m} B$, wenn $A$ ist nicht mehr wiederzuerkennen, dann $B$ ist nicht mehr erkennbar.
So ist für jede beliebige unkenntlich Sprache $C$, die reduziert werden kann, um $\überstrichen{A_{TM}}$ (beliebiges Beispiel Sprache, würde ausreichen, um zuliebe Beispiel), wie kann ich die $\überstrichen{A_{TM}} \le_{m} C$?
Für Einfachheit, genügt lediglich betrachten TM $\überstrichen{A_{TM}}$.
BEARBEITEN
Für die Klärung, $\überstrichen{A_{TM}} = \{ \langle M, w angle :M ext{ ist eine turing-Maschine, die nicht akzeptieren string } w \}$
Lösung
Nehmen wir $L_{\emptyset}=\{ \langle M angle \mid L(M) = \emptyset \}$, das heißt, alle Maschinen, die Sie akzeptieren kein Wort (D. H., deren Sprache leer ist).
Wir zeigen die Reduktion $\überstrichen{A_{TM}} \le L_\emptyset$.Die Minderung erfolgt, indem ein input $(\langle M angle,w)$ von $\überstrichen{A_{TM}}$ und konvertieren Sie es in eine input ${\langle ilde M angle}$ für $L_\emptyset$, so dass
$$(\langle M angle,w) \in \überstrichen{A_{TM}} \quad ext{ iff }\quad \langle ilde M angle \in L_{\emptyset}$$
Gegeben $(\langle M angle,w)$, wir können bauen $ ilde M$ in th folgenden Weg.$ ilde M$ input y hat die folgenden:
- löscht das Band
- schreibt $w$ auf dem Band
- läuft $M$ auf $w$, und führt die gleiche (wenn $M$ akzeptiert, $ ilde M$ akzeptiert auch).
Sich überzeugen, dass es möglich ist, zu konstruieren die Codierung von $ ilde M$ aus der Codierung von $M$ und von $w$.Lassen Sie uns nun überprüfen, ob diese Reduktion gilt:
- Wenn $(\langle M angle,w) \in \überstrichen{A_{TM}}$ dann $M$, die entweder ablehnt oder nicht halt.Wenn dem so ist, dann ist auch $ ilde M$ nicht akzeptieren, $y$, die für jede Eingabe $y$.Dies bedeutet, dass $L( ilde M) = \emptyset$ so $\langle ilde M angle \in L_{\emptyset}$.
- Wenn $(\langle M angle,B) otin \überstrichen{A_{TM}}$ dann $M$ nimmt $w$, so $ ilde M$ nimmt $y$ (für jeden $y$).Es folgt, dass $L( ilde M)=\Sigma^*$, was impliziert, dass $\langle ilde M angle otin L_{\emptyset}$.
Die "iff" - Zustand hält und wir erfolgreich zugeordneten Eingabe von $\überstrichen{A_{TM}}$ in einer Eingabe von $L_\emptyset$.In diesem Fall sagen wir, dass wir reduced $\überstrichen{A_{TM}}$ an $L_\emptyset$.Das heißt, wenn wir können lösen $L_\emptyset$, können wir Sie auch lösen $\überstrichen{A_{TM}}$, indem zuerst die Eingabe, und dann läuft der Algorithmus löst $L_\emptyset$ auf den konvertiert-Eingang.
Andere Tipps
Sie können zeigen, für eine beliebige unkenntlich Sprache $C$, das $\überstrichen{A_{TM}} \leq_m C$.Wenn $\überstrichen{A_{TM}} \leq_m C$ dann insbesondere die Turing-Grad von $C$ ist größer als oder gleich der Turing Grad von $\überstrichen{A_{TM}}$, da viele-one-Reduzierbarkeit impliziert, Turing-Reduzierbarkeit.Die Turing-Grad von $\überstrichen{A_{TM}}$ ist $0'$, die gleiche wie die Turing-Grad von $A_{TM}$.Es gibt viele unkenntlich Sprachen, deren Turing Grad ist unvergleichlich mit $0'$ (weder mehr noch weniger als $0'$).
Das Beispiel, das Lief G.gab funktioniert, weil $L_\emptyset$ insbesondere ist $m$-äquivalent zu $\überstrichen{A_{TM}}$.Es ist ein Allgemeines Phänomen, dass die meisten "natürlichen" Probleme tendenziell vergleichbar mit jedem anderen in $m$-Grad.Aber wenn man sich bei beliebigen Problemen ist dies nicht mehr wahr.