Reduzierung von $HALT$ auf $A_{TM}$

Question

Ich kenne die Reduzierung auf von $A_{TM}$ Zu $HALT$.Ist aber die folgende Reduktion aus $HALT$ Zu $A_{TM}$ richtig?

Wir suchen nach einer vollständig berechenbaren Funktion $f$ Zuordnung von $HALT$ Zu $A_{TM}$.Das folgende TM $F$ berechnet die Reduzierung $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

Ich denke, die Linie if T accepts or rejects, *accept* ist richtig, aber es wäre toll, wenn das jemand überprüfen könnte.

Bearbeiten:Ich habe die folgenden Folien gefunden, glaube aber nicht, dass der Aufbau darin korrekt ist: http://slideplayer.com/slide/13791105/

Answer 1

Es gibt mehrere Vorstellungen von "Reduktion". Sie haben a richtig beschrieben a Viele-Eins-Reduktion von $HALT$ Zu $A_{TM}$.Die Ermäßigung, auf die Sie verlinkt haben (spezifischerer Link). Hier) ist stattdessen a Wahrheitstabellenreduktion.Dies sind allgemeinere Objekte (daher ist Ihr Ergebnis stärker).Jedes wird wiederum durch den viel umfassenderen Begriff von zusammengefasst Turing-Reduktion.

Während Viele-Eins-Reduktionen im Allgemeinen der Standardbegriff in der Komplexitätstheorie sind, sind Turing-Reduktionen und die daraus resultierenden Abschlussstruktur sind die Standardwerte in der Berechenbarkeitstheorie.Beachten Sie, dass, wenn ich nur die Unentscheidbarkeit einer Menge beweisen möchte, eine Turing-Reduktion von einer bekanntermaßen unentscheidbaren Menge ausreicht.

---

Erinnern wir uns zunächst explizit an die Definitionen der beteiligten Sprachen:

• $A_{TM}=\{\langle M,w angle:M$ stoppt und akzeptiert die Eingabe $w\}$.

• $HALT=\{\langle M,w angle:M$ stoppt bei Eingabe $w\}$.

Ihre vorgeschlagene Reduzierung von $HALT$ Zu $A_{TM}$ Ist richtig:gegeben $M$, können wir rechnerisch eine neue Maschine bauen $\hat{M}$ die genau die Zeichenfolgen akzeptiert, auf denen $M$ stoppt.(Im Grunde ersetzen Sie einfach alle „Ablehnen“-Zustände in $M$ durch „Akzeptieren“-Zustände.)

---

Schauen wir uns nun die andere Ermäßigung an, auf die Sie verlinkt haben (spezifischerer Link). Hier).

Anstatt zu „Alle anhaltenden Staaten akzeptieren“ zu wechseln, berücksichtigt das verknüpfte Argument grundsätzlich Folgendes separat:

• die Originalmaschine und

• die „gegenteilige“ Maschine, die genau dann akzeptiert, wenn die ursprüngliche Maschine ablehnt und umgekehrt.

Eine bejahende Antwort für beide Fälle $A_{TM}$ stellt eine bejahende Antwort für die Originalmaschine sicher $HALT$.

Auf den ersten Blick sehe ich keinen Grund, dies zu tun, anstatt Ihrer Argumentation zu folgen, insbesondere weil sie zu einem schwächeren Ergebnis führt, aber sie ist richtig und reicht aus, um die umfassendere Behauptung in den Folien zu beweisen, nämlich diese $A_{TM}$ ist unentscheidbar.