Reduza $ l_c={\ langer m_1 \ rangle, \ langer m_2 \ rangle): l (m_1) \ cap l (m_2) \ neq \ blackset \} $ a $ a_ {tm} $

Question

Como reduzir $ l_c= {\ langer m_1 \ rangle, \ langle m_2 \ rangle): l (m_1) \ cap l (m_2) \ neq \ blackset \} $ para $ a_ {tm}= {\ langer m, w \ rangle: M $ é uma máquina de Turing que aceita $ W $ }.

minha tentativa: Construir uma máquina de Turing $ n $ Usando uma máquina de Turing $ u $ que decide a linguagem universal como sub-rotina para decidir $ l_c $ . $ n $ , em qualquer entrada $ <\ langle m_1 \ rangle, \ langle m_2 \ rangle> $ :
. $ 1. $ Construa um programa que gere palavra $ w \ in \ sum ^ \ AST $ na ordem canônica .
. $ 2. $ Execute $ u $ na $ \ langle m_1 , w \ rangle $ e $ \ langle m_2, w \ rangle $ .
$ 3. $ se $ u $ aceita ambos, aceite.
$ 4. $ se não, de volta para $ 1 $ .

Parece não funciona. Porque se $ l (m_1) \ cap l (m_2)=FORTSET $ , $ n $ loop para sempre (só não consegue encontrar tal $ W $ ).

Answer 1

A direção da redução que você está pedindo é um pouco estranho. Normalmente, reduzimos de $ a_ {tm} $ , a fim de mostrar indecidibilidade.

Talvez você quisesse perguntar sobre a outra direção?

De qualquer forma, em resposta à sua pergunta: Sua tentativa foi realmente bastante próxima, só precisa de um pouco de modificação. Veja como você pode prosseguir:

dado $ m_1, m_2 $ como entrada para $ l_c $ , construa uma nova máquina $ n $ que funciona da seguinte forma: dada entrada $ x $ , $ N $ ignora (ou seja, apaga $ x $ de sua fita) e, em seguida, começa a simular $ M_1 $ e $ m_2 $ em cada palavra $ w \ in \ sigma ^ * $ , em ordem canônica. Note, no entanto, que, a fim de simular $ m_1 $ e $ m_2 $ em / em> palavras, não podemos simplesmente executá-los em cada palavra arbitrariamente, como podemos ficar presos (nós não usamos um oráculo para $ a_ {TM} $ ). Em vez disso, nós os executamos em paralelo : execute $ m_1 $ e $ m_2 $ em cada uma das primeiras $ k $ palavras em $ \ sigma ^ * $ para $ k $ etapas e, em seguida, aumenta $ k $ por 1. Este é um truque razoavelmente comum, mas é bastante inteligente.

Agora, se em qualquer ponto $ m_1 $ e $ m_2 $ aceite, então $ n $ aceita. Caso contrário, ele continua correndo e aumentando $ k $ para sempre.

A redução é concluída enviando $ $ para a $ a_ {tm} $ < / span> oracle (ou, alternativamente, é completo se você a tratar como uma redução de mapeamento).

Observe que $ n $ aceita $ \ epsilon $ (e qualquer outra palavra) IFF houver Uma palavra que é aceita por ambos $ m_1 $ e $ m_2 $ .