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 $qquaddisplaystyle 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
