Decidability of empty intersection of two languages accepted by Turing machines

Problem Detail: 

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle L = \{ (R(M_1), R(M_2)) \mid L(M_1) \cap L(M_2) = \emptyset \}$,

where $R(M_1)$ and $R(M_2)$ are representations of Turing machines $M_1$, resp $M_2$ and $L(M_1)$, $L(M_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M_1)$ and $L(M_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is undecidable and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M_1$ and not $M_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?

Asked By : Smajl

Answered By : David Richerby

It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M_1$ that accepts all inputs. $L(M_1)\cap L(M_2) = L(M_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30077