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$
2
  • $\begingroup$ What do you mean by "a universal language"? $\endgroup$
    – Shaull
    Feb 5, 2020 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, 2020 at 14:39

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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