patternMinor
Decidability of empty intersection of two languages accepted by Turing machines
Viewed 0 times
languagesemptyacceptedtwodecidabilityintersectionturingmachines
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#30077, answer score: 7
Revisions (0)
No revisions yet.