Mapping-Reduktionen Komplement von A$_{TM}$

Question

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 \}$

Answer 1

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:

1. löscht das Band
2. schreibt $w$ auf dem Band
3. 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.

Answer 2

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.