1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.