Riduzione da $ HALT $ a $ A_ {TM} $

Question

Conosco la riduzione da $ a_ {tm} $ a $ halt $ .Ma è La seguente riduzione da $ halt $ a $ a_ {tm} $ corretto?

Stiamo cercando una funzione calcolabile totale $ f $ mappatura da $ halt $ a $ a_ {tm} $ . La seguente TM $ f $ calcola la riduzione $ 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>

.

Penso che la linea if T accepts or rejects, *accept* sia corretta, ma sarebbe fantastico se qualcuno potesse controllare questo.

Modifica: ho trovato le seguenti diapositive, ma non penso che la costruzione ci sia corretta: http://slidePlayer.com/slide/13791105/

Answer 1

Ci sono molteplici nozioni di "riduzione". Hai descritto correttamente una riduzione Molto-one di $ $ halt $ a $ A_ {TM } $ . La riduzione che hai collegato a (collegamento più specifico qui ) è invece un Riduzione della tabella di verità . Questi sono oggetti più generali (quindi il tuo risultato è più forte). Ognuno è a sua volta sottoboscato dalla nozione molto più ampia di Turing riduction .

Mentre molte riduzioni sono generalmente la nozione predefinita nella teoria della complessità della teoria della complessità, che turing riduzioni e il risultante struttura della laurea sono il valore predefinito nella teoria della computabilità. Si noti che se tutto ciò che voglio fare è dimostrare l'indecididabilità di alcuni set, una riduzione di Turing da un set noto-to-be-noncidable è sufficiente.

---

.

In primo luogo, richiamiamo esplicitamente le definizioni delle lingue coinvolte:

.

• $ a_ {tm}={\ langle m, w \ Rangle: m $ si ferma e accetta su input $ w \} $ .

• $ halt={\ langle m, w \ rangle: m $ halts on input $ w \} $ .

La tua riduzione proposta di $ halt $ a $ a_ {tm} $ è corretto : data $ m $ , possiamo elaborare in modo elaborato una nuova macchina $ \ hat {m} $ Che accetta precisamente quelle stringhe su cui $ m $ si ferma. (Fondamentalmente, sostituisci tutti tutti gli stati "rifiutanti" in $ m $ da "Accetta" Stati.)

---

.

Ora diamo un'occhiata all'altra riduzione che hai collegato a (collegamento più specifico qui ).

Fondamentalmente, piuttosto che andare a "tutti gli stati di fermi accetta" L'argomento collegato si ritiene separatamente:

.

• La macchina originale e

• La macchina "contraria" che accetta esattamente quando l'originale rifiuta e viceversa.

Una risposta affermativa per entrambi i casi in $ a_ {tm} $ garantisce una risposta affermativa per la macchina originale in $ HALT $ .

Off la parte superiore della mia testa non vedo alcuna ragione per farlo piuttosto che seguire la tua argomentazione, soprattutto perché produce un risultato più debole, ma è corretto ed è sufficiente per dimostrare la richiesta più ampia nelle diapositive, vale a dire $ A_ {TM} $ è indecidabile.