Suppose we have the language

$ \overline L = \{x∈\{0,1\}*:x∉L\}$

And we know that

$A ≤ HPL ≤ \overline A$

where HPL is the Halting problem.

We need to state whether A is finite, countably infinite and whether $A$ and $ \overline A$ is recursive or not or re or not.

We know that A reduces to HPL and HPL is re and therefore A is re. Since HPL reduces to $\overline A$ and HPL is not recursive then $\overline A$ is not recursive. Furthermore, if we know that a language is not recursive but its complement is re then the language is not re. We know so far that $\overline A$ is not recurisve but $A$ is re then it means that $\overline A$ is not re. Furthermore if you know that a language L is not re then either $\overline L$ is not re or $\overline L$ is re but not recursive. We know that $\overline A$ is not re but A is re and therefore, we can say that A is not recursive.

Can anybody tell me if my deduction is any good? Also, how can I know if A is finite/ count infinite? Any tip would be greatly appreciated!


Your analysis appears to be correct. But some clarity may help you. Let's analyse each case and check whether it is consistent with given information. As $\text{HPL} \leq \overline{A}$, $\overline{A}$ cannot be finite or recursive.

\begin{array}{|l|l|} \hline \textbf{If A is } & \textbf{Then }\overline{A} \textbf{ is}\\ \hline \mbox{Finite} & \mbox{Contradiction - }\overline{A} \text{ has to be FA; Violates HPL} \leq \overline{A} \\ \hline \mbox{Recursive} & \mbox{Contradiction - }\overline{A} \text{ has to be recursive; Violates HPL} \leq \overline{A}\\ \hline \mbox{Recursively Enumerable} & \text{Non-Recursively Enumerable}\\ \mbox{but not Recursive} & \\ \hline \mbox{Non-Recursively Enumerable} & \mbox{Contradiction - Violates } A \leq \text{HPL}\\ \hline \end{array}

You can now infer countability based on this information.


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.