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

Question

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$).

Answer 1

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

Perhaps you meant to ask about the other direction?

At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed:

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 $<N,\epsilon>$ 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$.