Reducir $L_c=\{\langle M_1 angle, \langle M_2 angle):L(M_1)\cap L(M_2) eq \emptyset\}$ a $A_{TM} $

Question

como reducir $L_c=\{\langle M_1 angle, \langle M_2 angle):L(M_1)\cap L(M_2) eq \emptyset\}$ a $A_{TM} =\{\langle M,w angle:M$ es una máquina de Turing que acepta $w$}.

Mi intento:Construir una máquina de Turing $N$ usando una máquina de turing $u$ que decide el lenguaje universal como subrutina para decidir $L_c$. $N$, en cualquier entrada $ <\langle M_1 angle, \langle M_2 angle >$:
$1.$ Construir un programa que genere palabras. $w \en \sum^\ast$ en orden canónico.
$2.$ Correr $u$ en $\langle M_1, w angle $ y $\langle M_2, w angle $.
$3.$ Si $u$ acepta ambos, acepta.
$4.$ Si no, volvamos a $1$.

Parece que no funciona.Porque si $L(M_1)\cap L(M_2)= \emptyset$, $N$ se repetirá para siempre (simplemente no puede encontrar tales $w$).

Answer 1

La dirección de reducción que está pidiendo es un poco extraña. Normalmente, reducimos de $ a_ {tm} $ , con el fin de mostrar la indecidabilidad.

¡Tal vez quisiste preguntar por la otra dirección?

En cualquier caso, en respuesta a su pregunta: su intento fue bastante cercano, solo necesita un poco de modificación. Aquí es cómo puedes continuar:

Dado $ m_1, m_2 $ como entrada para $ l_c $ , construir una nueva máquina $ n $ que funciona de la siguiente manera: Dada entrada $ x $ , $ N $ ignorarlo (es decir, borrar $ x $ desde su cinta), y luego comienza a simular $ M_1 $ y $ m_2 $ en cada palabra $ w \ in \ sigma ^ * $ , en orden canónico. Sin embargo, tenga en cuenta que para simular $ m_1 $ y $ m_2 $ en todos < / EM> Palabras, no podemos simplemente ejecutarlas en cada palabra arbitrariamente, ya que podríamos estar atascados (no utilizamos un Oracle to $ a_ {tm} $ ). En su lugar, los ejecutamos en paralelo : Ejecutar $ m_1 $ y $ m_2 $ En cada uno de los primeros $ k $ palabras en $ \ sigma ^ * $ para $ K $ pasos, y luego aumente $ k $ por 1. Este es un truco bastante común, pero es bastante inteligente.

Ahora, si en cualquier punto, tanto $ m_1 $ y $ m_2 $ aceptan, luego $ n $ acepta. De lo contrario, sigue funcionando y aumentando $ k $ para siempre.

La reducción se completa enviando $ $ a la $ a_ {tm} $ < / SPAN> Oracle (o, alternativamente, está completo si lo trata como una reducción de mapeo).

Tenga en cuenta que $ n $ acepta $ \ epsilon $ (y cualquier otra palabra) IFF está Una palabra que es aceptada por ambos $ m_1 $ y $ m_2 $ .