$
\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?
Best Answer
You are correct in your assumption about Turing Machines T and Tc that accept the languages L and Lc respectively. This means that T, when run on a finite string from L either 'accepts the string and halts' or 'loops indefinitely'. Tc behaves similarly for Lc. Now consider another Turing Machine M that is functionally equivalent to T and Tc combined. When M is run on a finite string from L, it either 'accepts the string and halts' (due to the functionality of T) or 'rejects the string and halts' (due to the functionality of Tc). Thus, it always halts making L decidable (or Recursive). Similarly, Lc also becomes recursive.