Mappatura Riduzioni per completare di A $ _ {TM} $

Question

Ho una domanda di carattere generale su riduzioni di mappatura. Ho visto diversi esempi di riduzione delle funzioni a $ A_ {TM} $

dove $ A_ {TM} = \ {\ Langle M, w \ rangle: \ text {Per} M \ text {è una macchina di Turing che accetta stringa} w \} $

che è grande per dimostrare indecidibilità. Ma dico: Voglio dimostrare irriconoscibili, invece. Cioè, voglio usare il corollario che, dato $ A \ le_ {m} B $, se $ A $ è irriconoscibile allora $ B $ è irriconoscibile.

Quindi, per qualsiasi lingua non riconoscibile arbitraria $ C $ che può essere ridotto a $ \ overline {A_ {TM}} $ (qualsiasi lingua esempio sarebbe sufficiente per fare un esempio), come posso ridurre $ \ overline {A_ {TM }} \ le_ {m} C $?

Per semplicità, basti solo considerare TM in $ \ overline {A_ {TM}} $.

Modifica

Per chiarimenti, $ \ overline {A_ {TM}} = \ {\ Langle M, w \ rangle: M \ text {è una macchina di Turing che non accetta stringa} w \} $

Answer 1

Let introito $ L _ {\ emptyset} = \ {\ langle M \ rangle \ metà L (M) = \ emptyset \} $, cioè, tutte le macchine che accettano nessuna parola (ad esempio, la cui lingua è vuota) .

Ora ci mostrano la riduzione $ \ overline {A_ {TM}} \ le L_ \ emptyset $. La riduzione si effettua prelevando un ingresso $ (\ langle M \ rangle, w) $ di $ \ overline {A_ {TM}} $ e convertirlo in un ingresso $ {\ langle \ tilde M \ rangle} $ a $ L_ \ emptyset $ tale che

$$ (\ langle M \ rangle, w) \ a \ overline {A_ {TM}} \ quad \ text {} se e solo se \ quad \ langle \ tilde M \ rangle \ a L _ {\ emptyset} $$

Dato $ (\ langle M \ rangle, w) $ possiamo costruire $ \ tilde M $ in th modo seguente. $ \ Tilde M $ su input y esegue le seguenti operazioni:

1. cancella il nastro
2. scrive $ w $ sul nastro
3. corre $ M $ a $ w $, ed esegue le stesse (se $ M $ accetta, $ \ tilde M $ accetta pure).

Convinciti è possibile costruire la codifica di $ \ tilde M $ dalla codifica di $ M $ e da $ w $. Ora cerchiamo di verificare che questa riduzione è valida:

• Se $ (\ langle M \ rangle, w) \ a \ overline {A_ {TM}} $ allora $ M $ sia scarti o non lo fa battuta d'arresto. Se è così, anche $ \ tilde M $ non accetta $ $ y, per ogni ingresso $ y $. Questo significa $ L (\ tilde M) = \ emptyset $ quindi $ \ langle \ tilde M \ rangle \ a L _ {\ emptyset} $.
• Se $ (\ langle M \ rangle, w) \ notin \ overline {A_ {TM}} $ allora $ M $ accetta $ w $, quindi $ \ tilde M $ accetta $ y $ (per ogni $ y $ ). Ne consegue che $ L (\ tilde M) = \ Sigma ^ * $ che implica che $ \ langle \ tilde M \ rangle \ notin L _ {\ emptyset} $.

Il "se e solo se" condizione tiene e abbiamo mappato con successo un ingresso di $ \ overline {A_ {TM}} $ in un ingresso di $ L_ \ emptyset $. In questo caso si dice abbiamo ridotto $ \ overline {A_ {TM}} $ a $ L_ \ emptyset $. Cioè, se siamo in grado di risolvere $ L_ \ emptyset $, possiamo anche risolvere $ \ overline {A_ {TM}} $ convertendo prima l'ingresso e poi eseguire l'algoritmo che risolve $ L_ \ emptyset $ sull'ingresso convertito.

Answer 2

Non si può mostrare, per un linguaggio irriconoscibile arbitraria $ C $, che $ \ overline {A_ {TM}} \ leq_m C $. Se $ \ overline {A_ {TM}} \ leq_m C $ poi in particolare il grado di Turing di $ C $ è superiore o uguale al grado Turing di $ \ overline {A_ {TM}} $, perché molti-one riducibilità implica Turing riducibilità. Il grado di Turing di $ \ overline {A_ {TM}} $ è $ 0' $, lo stesso che il grado di Turing di $ A_ {TM} $. Ci sono un sacco di lingue irriconoscibili il cui grado di Turing è incomparabile con $ 0 '$ (né maggiore né meno di $ 0' $).

L'esempio che ha dato Ran G. opere perché $ L_ \ emptyset $, in particolare, è $ m $ -equivalent a $ \ overline {A_ {TM}} $. V'è un fenomeno generale che la maggior parte dei problemi "naturali" tendono ad essere paragonabile con l'altro in $ m $ gradi. Ma se si guarda a problemi arbitrarie questo non è più vero.