Abbildung von Reduktionen auf das Komplement von A.

Ich habe eine allgemeine Frage zu Mapping-Reduzierungen. Ich habe mehrere Beispiele für das Reduzieren von Funktionen auf gesehen$A_{TM}$

wo $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\}$

Das ist großartig, um Unentscheidbarkeit zu beweisen. Aber sagen wir, ich möchte stattdessen die Unkenntlichkeit beweisen. Das heißt, ich möchte die Folgerung verwenden, die hat. Wenn nicht erkennbar ist, ist nicht erkennbar.$A \le_{m} B$$A$$B$

Wie kann ich also für jede beliebige nicht erkennbare Sprache die auf reduziert werden kann (jede Beispielsprache würde zum Beispiel ausreichen), reduzieren ?$C$$\overline{A_{TM}}$$\overline{A_{TM}} \le_{m} C$

Der Einfachheit halber genügt es, TM in$\overline{A_{TM}}$.

BEARBEITEN

Zur Klarstellung, $\overline{A_{TM}} = \{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \}$

Lass uns nehmen $L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$das heißt, alle Maschinen, die kein Wort akzeptieren (dh deren Sprache leer ist).

Jetzt zeigen wir die Reduktion $\overline{A_{TM}} \le L_\emptyset$. Die Reduzierung erfolgt durch Eingabe$(\langle M \rangle,w)$ von $\overline{A_{TM}}$ und es in eine Eingabe umwandeln ${\langle \tilde M \rangle}$ zum $L_\emptyset$ so dass

Gegeben $(\langle M \rangle,w)$ wir können konstruieren $\tilde M$ auf folgende Weise. $\tilde M$ Bei Eingabe bewirkt y Folgendes:

1. löscht das Band
2. schreibt $w$ auf dem Band
3. läuft $M$ auf $w$und führt dasselbe aus (wenn $M$ akzeptiert, $\tilde M$ akzeptiert auch).

Überzeugen Sie sich selbst, dass es möglich ist, die Codierung von zu konstruieren $\tilde M$ aus der Kodierung von $M$ und von $w$. Lassen Sie uns nun überprüfen, ob diese Reduzierung gültig ist:

• Wenn $(\langle M \rangle,w) \in \overline{A_{TM}}$ dann $M$lehnt ab oder hört nicht auf. Wenn ja, dann auch$\tilde M$ akzeptiert nicht $y$für jede Eingabe $y$. Das heisst$L(\tilde M) = \emptyset$ somit $\langle \tilde M \rangle \in L_{\emptyset}$.
• Wenn $(\langle M \rangle,w) \notin \overline{A_{TM}}$ dann $M$ akzeptiert $w$also $\tilde M$ akzeptiert $y$ (für jeden $y$). Es folgt dem$L(\tilde M)=\Sigma^*$ was impliziert, dass $\langle \tilde M \rangle \notin L_{\emptyset}$.

Die "iff" -Bedingung gilt und wir haben eine Eingabe von erfolgreich zugeordnet $\overline{A_{TM}}$ in eine Eingabe von $L_\emptyset$. In diesem Fall sagen wir, wir haben reduziert$\overline{A_{TM}}$ zu $L_\emptyset$. Das heißt, wenn wir lösen können$L_\emptyset$können wir auch lösen $\overline{A_{TM}}$ indem Sie zuerst die Eingabe konvertieren und dann den zu lösenden Algorithmus ausführen $L_\emptyset$ auf dem konvertierten Eingang.

Sie können nicht für eine beliebige nicht erkennbare Sprache anzeigen $C$, Das $\overline{A_{TM}} \leq_m C$. Wenn$\overline{A_{TM}} \leq_m C$ dann insbesondere der Turing-Grad von $C$ ist größer oder gleich dem Turing-Grad von $\overline{A_{TM}}$, weil die Reduzierbarkeit von vielen Eins die Reduzierbarkeit von Turing impliziert. Der Turing-Grad von$\overline{A_{TM}}$ ist $0'$, das gleiche wie der Turing-Grad von $A_{TM}$. Es gibt viele nicht wiedererkennbare Sprachen, mit denen der Turing-Grad nicht zu vergleichen ist$0'$ (weder größer noch kleiner als $0'$).

Das Beispiel, das Ran G. gab, funktioniert, weil $L_\emptyset$ insbesondere ist $m$-gleichwertig $\overline{A_{TM}}$. Es gibt ein allgemeines Phänomen, bei dem die meisten "natürlichen" Probleme in der Regel miteinander vergleichbar sind$m$-Grad. Wenn Sie sich jedoch willkürliche Probleme ansehen, ist dies nicht mehr der Fall.