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