# Is emptiness of the intersection of the languages of two TMs decidable? [duplicate]

Let

$\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?

• What have you tried? Where did you get stuck? Are you familiar with the concept of reductions? Nov 20, 2014 at 18:24
• I don't know where to start. Is it undecidable ? Nov 20, 2014 at 18:28
• @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. Nov 20, 2014 at 18:33
• @Ryan I don't know how to start. I can't think of something. Nov 20, 2014 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.)

• Another possibility is to choose $M_1 = M_2$. Nov 20, 2014 at 21:51
• @YuvalFilmus That's what I had in mind, along with the other choice. Didn't want to give it all away. Nov 21, 2014 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.

• I am confused. I don't understand. I think it's undecidable. Are you suggesting to Reduce $E_{TM}$ to $DISJOINT$ ? Nov 20, 2014 at 18:51
• Yes, that's another way of putting it. Nov 20, 2014 at 19:08
• Are we gonna assume that DISJOINT is decidable and use that assumption to show that $E_{TM}$ IS decidable ? Nov 20, 2014 at 19:55
• Yes, that's the idea. Nov 20, 2014 at 19:55
• 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. Nov 20, 2014 at 20:01