Riduzione del A_LBA a E_LBA

Question

Ho un piuttosto interessante per riflettere e mi piacerebbe se potessi ottenere una risposta per esso. Stavamo discutendo il tema della riduzione mappatura oggi nel mio corso di teoria di calcolo e mi chiedevo perché questa riduzione non può esistere, $ A_ {LBA} \ leq_ {m} E_ {LBA} $, dal momento che entrambi sono automi legati lineari (LBA). Mi rendo conto che $ E_ {LBA} $ è indecidibile, $ A_ {LBA} $ è decidibile, e la prova normale usa $ A_ {TM} $, o $ E_ {TM} $, per dimostrare l'undecidibility di $ E_ { LBA} $. Sono solo curioso di sapere perchè la prova sta usando una TM per dimostrare un LBA. Ma, il mio professore non poteva trovare una soluzione per la mia confusione. Mi chiedevo è possibile questo, in caso affermativo, perché o perché no.

Definizioni:

$ A_ {LBA} = \ {\ M Langle, w \ rangle \ metà \ text {$ M $ è un automa legato lineare che accetta la stringa $ w $} \} $

$ E_ {LBA} = \ {\ langle M \ rangle \ metà \ text {$ M $ è un automa legato lineare con $ L (M) = \ emptyset $} \} $

$ A_ {TM} $ e $ E_ {TM} $ sono i problemi equivalenti per macchine di Turing.

Answer 1

Hai la tua mappatura nel modo sbagliato. Così com'è, sarebbe una riduzione da un problema decidibile ad un problema indecidibile. E 'certamente possibile (vedi sotto), ma non ci dice nulla.

Si ricordi che se $ A \ leq_ {m} B $, quindi un algoritmo risolvere $ B $ (o decidere l'appartenenza, in questo caso) può essere utilizzato per risolvere $ A $ (decide l'appartenenza a $ A $). Quindi la riduzione si sta guardando ci direbbe che ogni decisore a $ E_ {} LBA $ potrebbe essere usato per decidere $ A_ {LBA} $. Ci capita di sapere anche che $ E_ {LBA} $ è indecidibile, ma questo non ci evitare di essere un po 'decisiva per $ A_ {LBA} $ che non si decide $ E_ {LBA} $.

In realtà, la riduzione che non può esistere è di $ E_ {LBA} \ leq_ {m} {A_ LBA} $, in quanto ciò implicherebbe che potremmo decidere $ E_ {LBA} $, che sappiamo di poter 't.

Per la seconda parte, la prova (o meglio, una delle possibili prove) che $ E_ {LBA} $ è indecidibile è tramite la costruzione della mappatura $ A_ {TM} \ leq_ {m} E_ {LBA} $, così ancora una volta un decisore a $ E_ {LBA} $ ci darebbe un decisore a $ A_ {TM} $, ma sappiamo già che $ A_ {TM} $ è indecidibile così $ E_ {LBA} $ deve anche essere indecidibile.

Per quanto riguarda perché la prova usa un linguaggio che coinvolge macchine di Turing per mostrare qualcosa su automi bound lineare, è perché funziona.

una riduzione

$ A_ {LBA} $ è decidibile, siamo in grado di prendere l'input LBA $ M $ e la stringa $ w $, ed eseguire il decisore su $ \ Langle M, w \ $ rangle. Se accetta, mappiamo l'accaduto a un LBA $ M_ {rej} $ che rifiuta immediatamente. Se gli scarti decisore, mappiamo a un LBA $ M_ {acc} $ che subito accetta. Così $ M_ {acc} $ accetta tutto l'input e non ha $ E_ {LBA} $, e $ M_ {} rej $ rifiuta tutto l'input ed è in $ E_ {LBA} $.

Nota, naturalmente, che tale riduzione è in un certo senso banale, e il sottoinsieme di $ E_ {LBA} $ si associa a è finita e quindi decidibile (anche normale!).

Un'altra prospettiva

Date due lingue $ A $ e $ B $ tale che $ A \ leq_ {m} B $, ci sono due fondamentali (utili) cose che potrebbe essere in grado di dire:

• Se $ B $ è decidibile , allora $ A $ è anche decidibile.
• Se $ A $ è indecidibile , allora $ B $ è anche indecidibile.

Nel nostro caso $ A $ è decidibile, e $ B $ è indecidibile, il che corrisponde a nessuna di queste possibilità, quindi la riduzione $ A_ {LBA} \ leq_ {m} E_ {LBA} $ non ci dice nulla circa la decidibilità di entrambi.