I'm curious about a potential relation between the following two languages.

$L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$.

$L_2 := \{\langle M_1, M_2 \rangle : L(M_1) \ne L(M_2) \}$.

Is it true that $L_2$ mapping reduces to $L_1$?

I've had many failed attempts to construct a reduction and would appreciate any help.


1 Answer 1


Here are three hints.

  • Show that $L_2$ is not computably enumerable.
  • Show that $L_1$ is computably enumerable.
  • If $L_2$ mapping reduces to $L_1$, what does it imply?
  • $\begingroup$ Are you sure that $L_2$ is not computably enumerable? $\endgroup$ Mar 20, 2019 at 0:24
  • $\begingroup$ Try enumerating the pairs of TMs in $L_2$. You will find you just cannot find a way. Now prove indeed you cannot. $\endgroup$
    – John L.
    Mar 20, 2019 at 0:25
  • $\begingroup$ Of course, if you can show that $L_2$ is not computably enumerable, then there is no such reduction. But could you please prove this? I really don't see why this is true. $\endgroup$ Mar 20, 2019 at 0:31
  • $\begingroup$ But that language is computably enumerable. It's recognized by the universal Turing machine. $\endgroup$ Mar 20, 2019 at 0:51
  • $\begingroup$ We can reduce $\overline{HALT}= \{⟨M, w⟩\mid\text{ TM }M\text{does not halt on input } w\}$ to $L_2$. $\endgroup$
    – John L.
    Mar 20, 2019 at 0:54

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.