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?

  • $\begingroup$ Yes, the intersection is recursively enumerable. However, it seems not easy to understand your line of reasoning. $\endgroup$ – John L. Jan 23 '19 at 18:57
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jan 23 '19 at 18:58
  • $\begingroup$ I apologize, I tried to put into words what exactly was confusing me. Attempting to somehow conceptualize a way to make a new TM was my first idea but I'm having trouble with defining whether or not a language is decidable, so I don't know if one can make sure the machine for the intersection will be decidable. $\endgroup$ – Krios Jan 23 '19 at 19:07
  • $\begingroup$ "a Turing-Machine ... that holds on every input". By "holds", do you mean running forever? Or do you mean "halts"? $\endgroup$ – John L. Jan 23 '19 at 20:03
  • $\begingroup$ Ah yes, sorry. Language barrier. I mean halt. $\endgroup$ – Krios Jan 23 '19 at 20:04

You have been going well. Yes, $L_3=L_1\cap L_2\in\text{ RE} $.

Could it be that $L_3$ is recursive?

The answer is not necessarily. There are several cases here.

  • If $L_1$ is a recursive language as well, then $L_3$ is also recursive.

  • If $L_1$ is not a recursive language, then $L_3$ may or may not be recursive.

    • For example, let $L_2$ be the languages of all words. Then $L_3=L_2$ is not recursive.
    • For example, let $L_2$ be the language that does not contain any word. Then $L_3$ is also the language that does not contain any word, which is recursive.

Exercise 1. Show that if both $L_1$ and $L_2$ are recursive, then $L_1\cap L_2$ is recursive.

Exercise 2. Construct two languages $L_1$ and $L_2$ that satisfy all following conditions.

  • $L_1$ is recursively enumerable.
  • $L_2$ is recursive and $L_2$ is not the language of all words.
  • $L_1\cap L_2\subsetneq L_1$ is recursively enumerable but not recursive.
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.