# 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?

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

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

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

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