Riduci $ l_c={\ Langle M_1 \ Rangle, \ Langle M_2 \ Rangle): L (M_1) \ Cap L (M_2) \ neq \ DemplySet \} $ a $ A_ {TM} $

Question

Come ridurre $ l_c={\ Langle M_1 \ Rangle, \ Langle M_2 \ Rangle): L (M_1) \ Cap L (M_2) \ neq \ DemptySet \} $ a $ A_ {TM}={\ Langle M, W \ Rangle: M $ è una macchina di Turing che accetta $ W $ }.

La mia prova: Costruisci una macchina di Turing $ N $ utilizzando una macchina di turing $ U $ che decide il linguaggio universale come subroutine per decidere $ L_C $ . $ N $ , su qualsiasi ingresso $ <\ Langbello M_1 \ Rangle, \ Langle M_2 \ Rangle> $ :
. $ 1. $ Costruisci un programma che genera parola $ w \ in \ sum ^ \ ast $ in ordine canonico .
. $ 2. $ Esegui $ U $ su $ \ Langle M_1 , w \ Rangle $ e $ \ Langle M_2, W \ Rangle $ .
$ 3. $ se $ u $ accetta entrambi, accettare.
$ 4. $ In caso contrario, torna a $ 1 $ .

Sembra che non funzioni. Perché se $ l (m_1) \ cap l (m_2)=vuoto $ , $ n $ Anello per sempre (non riesce a trovare tale $ W $ ).

Answer 1

La direzione di riduzione che stai chiedendo è un po 'strano. In genere, riduriamo da $ a_ {tm} $ , per mostrare l'indecidibilità.

Forse intendevi chiedere della direzione dell'altra direzione?

A qualsiasi aliquota, in risposta alla tua domanda: il tuo tentativo è stato in realtà abbastanza vicino, ha solo bisogno di un po 'di modifica. Ecco come puoi procedere:

Dato $ M_1, M_2 $ come input per $ l_c $ , costruire una nuova macchina $ N $ che funziona come segue: Dato input $ x $ , $ N $ Ignoralo (cioè cancellazioni $ x $ dal suo nastro), quindi inizia a simulare M_1 $ e $ M_2 $ su ogni parola $ w \ in \ sigma ^ * $ , in ordine canonico. Nota, tuttavia, che per simulare $ m_1 $ e $ m_2 $ su tutto < / EM> Parole, non possiamo semplicemente eseguirli su ogni parola arbitrariamente, poiché potremmo rimanere bloccati (non usiamo un oracle to $ a_ {tm} $ ). Invece, li eseguiamo in parallelo : eseguire $ m_1 $ e $ M_2 $ su ciascuna delle prime $ k $ parole in $ \ sigma ^ * $ per $ k $ passaggi, quindi aumentare $ k $ per 1. Questo è un trucco abbastanza comune, ma è piuttosto intelligente.

Ora, se in qualsiasi momento sia $ M_1 $ e $ M_2 $ Accetta, quindi $ N $ accetta. Altrimenti, continua a funzionare e ad aumentare $ k $ per sempre.

La riduzione è completata inviando $ $ alla $ a_ {tm} $ < / SPAN> Oracle (o, in alternativa, è completo se lo si tratta come una riduzione della mappatura).

Nota che $ N $ accetta $ \ epsilon $ (e qualsiasi altra parola) IF Una parola che è accettata sia da $ M_1 $ e $ M_2 $ .