Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is emptiness of the intersection of the languages of two TMs decidable?

, , No Comments
Problem Detail: 


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

Asked By : Altaïr

Answered By : Rick Decker

Assuming you have a decider $R$ for DISJOINT, you could use this to make a decider D for $E_\text{TM}$ 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.)

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback