This question already has an answer here:


$\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$.

How do I know if this language is decidable or not? And How do I prove my answer?


marked as duplicate by Raphael Nov 20 '14 at 20:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Are you familiar with the concept of reductions? $\endgroup$ – Shaull Nov 20 '14 at 18:24
  • $\begingroup$ I don't know where to start. Is it undecidable ? $\endgroup$ – Altaïr Nov 20 '14 at 18:28
  • 1
    $\begingroup$ @Altaïr that's what you're trying to prove. Modify your question to show the precise steps you have taken to solve the problem, and where are you getting stuck. $\endgroup$ – Ryan Nov 20 '14 at 18:33
  • $\begingroup$ @Ryan I don't know how to start. I can't think of something. $\endgroup$ – Altaïr Nov 20 '14 at 18:35

Assuming you have a decider $R$ for DISJOINT, you could use this to make a decider D for $E_\text{TM} = \{\langle M\rangle\mid L(M)=\emptyset\}$ as follows:

D(<M>) =
   return R(<M>, <A>)

where $A$ was a TM, selected in such a way that $\langle M\rangle\in E_\text{TM}$ if and only if $(\langle M\rangle, \langle A\rangle)\in\text{ DISJOINT}$. All that's left for you is to find the $A$ and show that it satisfies the needed conditions. (There are a couple of ways to make this choice.)

  • $\begingroup$ Another possibility is to choose $M_1 = M_2$. $\endgroup$ – Yuval Filmus Nov 20 '14 at 21:51
  • $\begingroup$ @YuvalFilmus That's what I had in mind, along with the other choice. Didn't want to give it all away. $\endgroup$ – Rick Decker Nov 21 '14 at 14:37

Hint: If DISJOINT were decidable then even the special case in which $M_1$ is some fixed machine which accepts all inputs is decidable. This is the language $\{ \langle M \rangle : L(M) = \emptyset \}$, which you might be more familiar with.

  • $\begingroup$ I am confused. I don't understand. I think it's undecidable. Are you suggesting to Reduce $E_{TM}$ to $DISJOINT$ ? $\endgroup$ – Altaïr Nov 20 '14 at 18:51
  • $\begingroup$ Yes, that's another way of putting it. $\endgroup$ – Yuval Filmus Nov 20 '14 at 19:08
  • $\begingroup$ Are we gonna assume that DISJOINT is decidable and use that assumption to show that $E_{TM}$ IS decidable ? $\endgroup$ – Altaïr Nov 20 '14 at 19:55
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Nov 20 '14 at 19:55
  • $\begingroup$ So we assume we have a TM R that decides DISJOINT then we use R to construct TM S that decides $E_{TM}$ then we use R as subroutine to construct S. I just don't know how to write the algorithm. $\endgroup$ – Altaïr Nov 20 '14 at 20:01

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