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.


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 '19 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 '19 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 '19 at 0:31
  • $\begingroup$ But that language is computably enumerable. It's recognized by the universal Turing machine. $\endgroup$ Mar 20 '19 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 '19 at 0:54

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.