Question

Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?

Assume $L_{3}$ is the intersection of some language $L_{1}$ $\epsilon$ RE and some other language $L_{2}$ $\epsilon$ REC .

Since $L_{2}$ $\epsilon$ REC, there must be a Turing-Machine $M_{2}$ that holds on every input, whethere or not the input x $\epsilon$ $L_{2}$. If we now have a k-NTM $M_{3}$ that on one band simulates $M_{2}$ and upon acceptance of the input switches to another band where it then simulates $M_{1}$ (for $L_{1}$).

Since $M_{1}$ is only ever simulated if $M_{2}$ accepts the input, $M_{1}$ only gets the chance to hold for every word x $\epsilon$ $L_{1}$ $\bigcap $ $L_{2}$.

That means we can already assume that we wont get stuck in a loop for words x $\notin $ $L_{2}$.

However that is not the case for words that are in the intersection or only in $L_{2}$ and not in $L_{1}$, as the simulation of $M_{1}$ wil also be recursively enumarable and may run forever, without us ever knowing whether the input is accepted or not.

If my thoughts so far were correct, that means that $L_{3}$ $\epsilon$ RE.

What I am uncertain about is if there is any sort of algorithm or technique with which we could make the simulation of $M_{1}$ decidable, or if maybe it is possible to make an entirely new TM, independent from $M_{1}$ and $M_{2}$ and make sure it is decidable?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top