I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$.

How can I reduce the former to the latter: $L_\cap\leq_RL_U$? My idea was to build a machine $M$ simulating $M_1$ and $M_2$ in series. $M$ accepts a word if and only if both $M_1$ and $M_2$ do. So we feed all words to the machine taking $M$ and words until we find one, otherwise keep running. But the proplem is the machine is not halting guaranteed since it can run forever. What will be the correct solution?

  • $\begingroup$ You write in words that you want to reduce $L_U$ to $L_\cap$ but in symbols that you want to reduce the other way. Which is it? $\endgroup$ Commented Jan 30, 2019 at 15:21
  • $\begingroup$ @DavidRicherby Actually both direction. But I got stuck by one, the one as in the symbol. I had the idea now. Could you help me to see whether is correct or not? For $L_\cap\leq_R L_U$, first test the correctness whether they are two valid machine codes. If no then reject right away. If yes, rewrite a program called $A$ needing empty input and with a big while loop running through all words and in the loop let the words are fed to both $M_1$ and $M_2$ in series: Just simulate them together. If the word is accepted then return accept, otherwise check the next word (in alphabetic order). $\endgroup$
    – Upc
    Commented Jan 30, 2019 at 15:41
  • $\begingroup$ @DavidRicherby Now feed this new program $A$ with $\lambda$ to the oracle machine can solve $L_U$. If accept then output accept, otherwise reject. $\endgroup$
    – Upc
    Commented Jan 30, 2019 at 15:43
  • 2
    $\begingroup$ @XavierYang, please update in the question since the description in the comment is much better what is in the question. $\endgroup$
    – John L.
    Commented Jan 30, 2019 at 15:44

1 Answer 1


Your solution is almost there: I do not think it is necessary to construct a machine that always halts. The problem running $M$ on input $w$ does not always halt either.

Running $M_1$ and $M_2$ over all input strings $x$ is tricky: indeed,if one of the machines does not halt on a particular input, then the new machine $M$ will not consider the next input. The solution for that is usually called dove tiling, where more and more inputs are simulated step by step.

This can be avoided (or better: hidden) by assuming non-deterministic machines. $M$ guesses an input $x$ and simulates both $M_1$ and $M_2$ on that input $x$. Now $M$ halts (on the empty input) whenever the languages of $M_1$ and $M_2$ intersect.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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