2
$\begingroup$

$ \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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Berci
    Apr 14, 2020 at 12:05
  • $\begingroup$ 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. $\endgroup$
    – sesodesa
    Apr 14, 2020 at 12:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .