# Is a language $L$ recursive, if it and its complement $L^c$ are both recursively enumerable?

$$\newcommand{\lang}{L} \newcommand{\Nset}{\mathbb N} \newcommand{\Lset}{\mathcal L} \newcommand{\Rec}{\mathcal R} \newcommand{\RecEnum}{\Rec_\Nset} \newcommand{\accept}{\mathbf{a}} \newcommand{\reject}{\mathbf{r}} \newcommand{\halt}{\mathbf{h}}$$ Let $$\Rec$$ be the set of recursive languages and $$\RecEnum$$ the set of recursively enumerable languages (hence the $$\Nset$$ in the subindex). If $$\lang\in\RecEnum$$ and $$\lang^c \in \RecEnum$$, where $$\lang^c$$ is the complement of $$\lang$$, is $$L \in \Rec$$?

### Some thoughts

Ok, so the only tools I have available to me at the moment are Turing-machines $$T$$ and the fact that $$\Rec\subset\RecEnum$$. I'm aware that a language $$L \in \RecEnum$$, if some Turing machine accepts it, as in ends up in the special accept-state $$\accept$$ when reading input $$l\in\lang$$.

On the other hand, a language $$L$$ is simply recursive, if it is solved by a Turing-machine and at the same time the Turing-machine $$T$$ halts, given any other input. Solving a language means that a Turing-machine accepts any input $$l \in L$$ and rejects it, if $$l \notin L$$. Halting means a Turing-machine ends up in one of its special states $$\accept$$, $$\reject$$ or $$\halt$$, accept, reject and halt respectively, during its execution.

In other words, if $$\lang \in \RecEnum$$ and $$\lang^c \in \RecEnum$$, they should both be acceptable via some Turing machines $$T$$ and $$T^c$$, as in $$\lang = \lang(T)$$ and $$\lang^c = \lang(T^c)$$. However, this does not mean that the machines reject or halt given the respective input $$l^c \notin \lang$$ and $$l\notin\lang^c$$.

I would then be inclined to say that the claim is false, simply because to me it seems like having $$\lang^c\in\RecEnum$$ as well says nothing about the recursive nature of $$\lang$$. But are there any concrete counterexamples?

• The claim is true. We can set up a Turing machine that parallelly runs a program for $L$ and for $L^c$, and since at least one of them will stop on any input, we can evaluate it in finite time. Apr 14, 2020 at 12:05
• Oh, that makes perfect sense, now that I think about it. We don't really need to worry about the state $\mathbf h$, as it is used to halt the computation for some other reason than acceptance $\mathbf a$ or rejection $\mathbf r$. But in this case there are no alternatives besides ending up in $\mathbf a$ or $\mathbf r$, as $T$ complements $T^c$ and vice versa. Apr 14, 2020 at 12:21