Reduza $ l_c={\ langer m_1 \ rangle, \ langer m_2 \ rangle): l (m_1) \ cap l (m_2) \ neq \ blackset \} $ a $ a_ {tm} $
-
29-09-2020 - |
Pergunta
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 $ ).
Solução
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 $
Observe que $ n $ aceita $ \ epsilon $ (e qualquer outra palavra) IFF houver Uma palavra que é aceita por ambos $ m_1 $ e $ m_2 $ .