Réduction à partir de $ARRÊTER$ à $A_{TM}$

Question

Je sais que la réduction de $A_{TM}$ pour $ARRÊTER$.Mais est la suite de la réduction à partir de $ARRÊTER$ pour $A_{TM}$ - il correct?

Nous sommes à la recherche pour le total de la fonction calculable $f$ cartographie de l' $ARRÊTER$ pour $A_{TM}$.La suite de TM $F$ calcule la réduction $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>

Je pense que la ligne if T accepts or rejects, *accept* est correct, mais ce serait génial si quelqu'un pouvait vérifier ce point.

Edit:J'ai trouvé les diapositives suivantes, mais je ne pense pas que la construction y est correct: http://slideplayer.com/slide/13791105/

Answer 1

Il y a plusieurs notions de "reduction". Vous avez correctement décrit un de nombreux-une réduction de $ARRÊTER$ pour $A_{TM}$.La réduction que vous avez lié à (plus de lien spécifique ici) est plutôt un la vérité-tableau de réduction.Ces plus générale, les objets (si votre résultat est plus forte).Chacun est à son tour remplacée par la notion beaucoup plus large de La réduction de Turing.

Alors que de nombreux un les réductions sont généralement le défaut notion dans la théorie de la complexité de Turing réductions et les structure de diplôme sont par défaut dans la théorie de la compilation.Notez que si tout ce que je veux faire est de prouver l'indécidabilité d'un ensemble, d'une réduction de Turing de certains connus pour être indécidable ensemble est suffisant.

---

Tout d'abord, laissez explicitement rappeler les définitions des langues concernées:

• $A_{TM}=\{\langle M,w angle:M$ s'arrête et accepte en entrée $w\}$.

• $HALT=\{\langle M,w angle:M$ s'arrête sur entrée $w\}$.

La réduction proposée de $ARRÊTER$ pour $A_{TM}$ est correct:compte tenu de $M$, nous pouvons computably construire une nouvelle machine $\hat{M}$ qui accepte précisément les cordes sur lesquelles $M$ s'arrête.(En gros, il suffit de remplacer tous les "rejeter" les états $M$ par "accepter" des états.)

---

Maintenant, nous allons regarder les autres de la réduction qui est lié à (plus de lien spécifique ici).

En gros, plutôt que d'aller à "l'arrêt de tous les états acceptent" l'argument lié considère séparément:

• la machine d'origine, et

• le "contraire" de la machine qui accepte exactement quand l'original rejette et vice-versa.

Une réponse affirmative pour l'un ou l'autre cas $A_{TM}$ assure une réponse affirmative pour la machine d'origine dans $ARRÊTER$.

Sur le dessus de ma tête, je ne vois aucune raison de le faire, plutôt que de suivre votre argument, surtout parce qu'il donne une plus faible résultat, mais il est correct et est suffisant pour prouver la plus large de la demande dans les diapositives, à savoir que $A_{TM}$ est indécidable.