Abbildung von Reduktionen auf das Komplement von A.

7

Ich habe eine allgemeine Frage zu Mapping-Reduzierungen. Ich habe mehrere Beispiele für das Reduzieren von Funktionen auf gesehenATM

wo ATM={M,w: For M 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.AmBAB

Wie kann ich also für jede beliebige nicht erkennbare Sprache die auf reduziert werden kann (jede Beispielsprache würde zum Beispiel ausreichen), reduzieren ?CATM¯ATM¯mC

Der Einfachheit halber genügt es, TM inATM¯.

BEARBEITEN

Zur Klarstellung, ATM¯={M,w:M is a turing machine which does not accept string w}

RageD
quelle

Antworten:

9

Lass uns nehmen L={ML(M)=}das heißt, alle Maschinen, die kein Wort akzeptieren (dh deren Sprache leer ist).

Jetzt zeigen wir die Reduktion ATM¯L. Die Reduzierung erfolgt durch Eingabe(M,w) von ATM¯ und es in eine Eingabe umwandeln M~ zum L so dass

(M,w)ATM¯ iff M~L

Gegeben (M,w) wir können konstruieren M~ auf folgende Weise. M~ Bei Eingabe bewirkt y Folgendes:

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

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

  • Wenn (M,w)ATM¯ dann Mlehnt ab oder hört nicht auf. Wenn ja, dann auchM~ akzeptiert nicht yfür jede Eingabe y. Das heisstL(M~)= somit M~L.
  • Wenn (M,w)ATM¯ dann M akzeptiert walso M~ akzeptiert y (für jeden y). Es folgt demL(M~)=Σ was impliziert, dass M~L.

Die "iff" -Bedingung gilt und wir haben eine Eingabe von erfolgreich zugeordnet ATM¯ in eine Eingabe von L. In diesem Fall sagen wir, wir haben reduziertATM¯ zu L. Das heißt, wenn wir lösen könnenLkönnen wir auch lösen ATM¯ indem Sie zuerst die Eingabe konvertieren und dann den zu lösenden Algorithmus ausführen L auf dem konvertierten Eingang.

Ran G.
quelle
5

Sie können nicht für eine beliebige nicht erkennbare Sprache anzeigen C, Das ATM¯mC. WennATM¯mC dann insbesondere der Turing-Grad von C ist größer oder gleich dem Turing-Grad von ATM¯, weil die Reduzierbarkeit von vielen Eins die Reduzierbarkeit von Turing impliziert. Der Turing-Grad vonATM¯ ist 0, das gleiche wie der Turing-Grad von ATM. Es gibt viele nicht wiedererkennbare Sprachen, mit denen der Turing-Grad nicht zu vergleichen ist0 (weder größer noch kleiner als 0).

Das Beispiel, das Ran G. gab, funktioniert, weil L insbesondere ist m-gleichwertig ATM¯. Es gibt ein allgemeines Phänomen, bei dem die meisten "natürlichen" Probleme in der Regel miteinander vergleichbar sindm-Grad. Wenn Sie sich jedoch willkürliche Probleme ansehen, ist dies nicht mehr der Fall.

Carl Mummert
quelle
Ich entschuldige mich, mein Wortlaut war schlecht. Ich wollte ein willkürlich bestimmtes Problem , das ist nicht mehr wiederzuerkennen. Ich habe nur nach einem Beispiel gesucht, um die Reduzierungen besser zu verstehen.
RageD