I am currently studying turing computability and related problems such as the halting problem with a background in formal languages.

I know that the class of recursive (decidable) languages is a closure under union, intersection and complement, and that recursively enumerable languages (semi-decidable) are a closure under union and intersection, but what about non-recursive (undecidable) languages?

To be more specific, I am trying to prove that a specific language of the form $$L = \{ w \in \Sigma^* : w \in A \lor w \in B \}$$ is non-recursive. I managed to prove that neither $A$ nor $B$ are recursive by reducing them to the universal halting problem, but I am not sure what that implies for $L$.

The exact language is $$L = \left\{ w\#u \in \left\{ 0, 1, \# \right\}^* | \\ M_w \text{ will halt with input } u \text{ or } M_u \text{ will halt with input } w \right\}$$ where $M_b$ is the turing machine whose transition function $\delta$ is represented using Gödel numbering as a binary string $b$.

Is the class of non-recursive languages a closure under union? If it is, how could I prove it myself or where could I find an existing proof?

  • $\begingroup$ What are you actually asking? The question in your title is rather different from the two questions in the body. $\endgroup$ – David Richerby Feb 25 '17 at 16:33

Non-recursive languages are closed under complement, but not under union or intersection.

Indeed, a decider for $A$ exists iff there is a decider for $A^c$. Hence the closure under complement.

However, let $B$ be any non-recursive language. $B^c$ is also non-recursive. But $B \cap B^c = \emptyset$ and $B \cup B^c = \Sigma^*$ are both recursive. Hence, non-recursive languages are not closed under union or intersection.

In the example you mention, you can not conclude anything about $L$ from $A,B$ being non recursive.

I will provide a hint for $L$, only. When you have a language of the form $L=\{f(x,y) | x,y\mbox{ s.t. } p(x,y)\}$, it is sometimes convenient to choose a particular value $a$ and study the related language $L_a = \{ y | y\mbox{ s.t. } p(a,y) \}$ first. Maybe one can choose $a$ to make $p(a,y)$ simple enough so that other proof techniques apply.

  • $\begingroup$ Well, this is not the anwer I hoped for, but your explanation is surprisingly simple and appears to be correct. Thank you! $\endgroup$ – just.kidding Feb 25 '17 at 12:02
  • $\begingroup$ @just.kidding I don't wish to spoil the exercise, but I added a hint. $\endgroup$ – chi Feb 25 '17 at 12:08
  • $\begingroup$ Thanks! I guess if $L_a$ is undecidable, then $L$ is as well, because $L$ must be decidable for all tuples $(x, y)$ in order to be decidable? $\endgroup$ – just.kidding Feb 25 '17 at 12:15
  • $\begingroup$ @just.kidding Yes. The point is now to find $a$ such that $L_a$ is undecidable, yet it reduces to $L$. $\endgroup$ – chi Feb 25 '17 at 15:24

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.