# Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM}$

How to reduce $$L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$$ to $$A_{TM} =\{\langle M,w \rangle: M$$ is a Turing machine that accepts $$w$$}.

My try: Construct a Turing machine $$N$$ using a Turing Machine $$U$$ that decides universal language as subroutine to decide $$L_c$$. $$N$$, on any input $$<\langle M_1 \rangle, \langle M_2 \rangle >$$:
$$1.$$ Construct a program that generates word $$w \in \sum^\ast$$ in canonical order.
$$2.$$ Run $$U$$ on $$\langle M_1, w\rangle$$ and $$\langle M_2, w\rangle$$.
$$3.$$ If $$U$$ accepts both, accept.
$$4.$$ If not, back to $$1$$.

It seems does not work. Because if $$L(M_1)\cap L(M_2)= \emptyset$$, $$N$$ will loop forever(it just can't find such $$w$$).

• What do you mean by "a universal language"? Feb 5, 2020 at 14:03
• @Shaull universal language is $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$} Feb 5, 2020 at 14:39

The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $$A_{TM}$$, in order to show undecidability.

Given $$M_1,M_2$$ as input for $$L_c$$, construct a new machine $$N$$ that works as follows: given input $$x$$, $$N$$ ignores it (i.e., erases $$x$$ from it's tape), and then starts simulating $$M_1$$ and $$M_2$$ on every word $$w\in \Sigma^*$$, in canonical order. Note, however, that in order to simulate $$M_1$$ and $$M_2$$ on all words, we cannot simply run them on each word arbitrarily, as we might get stuck (we do not use an oracle to $$A_{TM}$$). Instead, we run them in parallel: run $$M_1$$ and $$M_2$$ on each of the first $$k$$ words in $$\Sigma^*$$ for $$k$$ steps, and then increase $$k$$ by 1. This is a fairly common trick, but it's quite clever.
Now, if at any point both $$M_1$$ and $$M_2$$ accept, then $$N$$ accepts. Otherwise, it keeps running and increasing $$k$$ forever.
The reduction is completed by sending $$$$ to the $$A_{TM}$$ oracle (or, alternatively, it's complete if you treat it as a mapping-reduction).
Note that $$N$$ accepts $$\epsilon$$ (and any other word) iff there is a word that is accepted by both $$M_1$$ and $$M_2$$.