Are finite and recursive instances of $L$ possible with the following constraints?

$\text{L $\subseteq$ {0,1}*}$ and $L \leq HALT \leq \overline L$ where $\overline L = \{\text{ x $\in$ {0,1}* : x $\notin$ L }\}$.

NOTE: Raphael and Yuval kindly pointed out that I was overlooking $\overline L$ is undecidable. Aside from this oversight, are there any other issues, e.g. conceptual misunderstandings, logical fallacies, etc. in the explanation below?

As I understand it:

  1. A finite instance of $L$ is possible. Since the language is finite, an evaluating Turing Machine (TM) could not loop indefinitely on input, and consequently would halt either in an "accept" or "reject" state. Since the language stops on all inputs, it is recursive and thus can be reduced to $HALT$, which is recursively enumerable.

  2. Since a finite instance (which is recursive) is possible, logically a recursive $L$ must also be possible.

  • $\begingroup$ You are ignoring that $\overline{L}$ needs to be undecidable. $\endgroup$ – Raphael Aug 24 '16 at 9:05
  • $\begingroup$ @Raphael is my understanding that $\overline L$ includes all strings not included in the finite $L$ -- hence $\overline L$ is infinite -- and therefore undecidable, correct? $\endgroup$ – Brandeis King Aug 24 '16 at 17:21
  • 1
    $\begingroup$ @BrandeisKing, check the definition of undecidable again. Infinite doesn't imply undecidable! $\endgroup$ – D.W. Aug 24 '16 at 18:59
  • $\begingroup$ Indeed. Many infinite sets decidable; in fact, finite (and co-finite) sets are very boring (in terms of computational complexity) and fall below regular languages in complexity. All of the classes you'll meet during the usual courses are harder! $\endgroup$ – Raphael Aug 24 '16 at 19:48
  • $\begingroup$ Undecidable, as I understand, means anything that is not in $R$ but in $RE$ or not in $RE$. When I apply this to infinite sets (countable or otherwise), per my understanding, infinite sets have the capacity to loop indefinitely -- thus placing them in $RE$ (or undecidable) category. But I believe @Raphael points out, that infinite sets are in fact decidable or in $R$. Therefore, I've clearly misunderstood something. Is my understanding of undecidable wrong or the assumption that all infinite sets have the capacity to loop indefinitely? $\endgroup$ – Brandeis King Aug 24 '16 at 22:11

To narrow down the search space, consider what you know about closure properties and HPL.

  1. The class of decidable languages $R$ is closed against complement.
  2. HPL is not in $R$.

You can conclude that $L \not\in R$;¹ otherwise, $\overline{L} \in R$ and therefore $\mathrm{HPL} \not\leq_T \overline{L}$.

On the other end, you need that $L \in RE$ (the set of semi-decidable languages) -- otherwise $L \not\leq_T \mathrm{HPL}$.

In combination, you need $L \in RE \setminus R$ which answers your question².

  1. In particular, $L$ can not be finite since all such languages are decidable. The decider just checks a hard-coded table of all words in the language. With the same table you can also decide the complement.
  2. Note how this implies $\overline{L} \not\in R$ which is enough for $HPL \leq_T \overline{L}$.
| cite | improve this answer | |
  • $\begingroup$ Thanks for cogent explanation; it was very helpful. However, I'd like to clarify one aspect of your answer. You wrote that "this implies $\overline L \notin R$," which as I understand leaves open the possibility of it being in $RE$. But since $L \in RE$ and if $\overline L \in RE$ that would mean $L \in R$ which is not possible per the constraints. Therefore is it safe to assume that $\overline L \notin RE$? $\endgroup$ – Brandeis King Aug 24 '16 at 21:53
  • $\begingroup$ @BrandeisKing Yes, that's a further conclusion. :) $\endgroup$ – Raphael Aug 24 '16 at 23:20

You haven't specified your notion of reduction, so I'm assuming a computable oracle reduction. Any language reducible to a computable language is computable. HPL (usually known as HALT) is not computable. Hence HPL cannot be reduced to $\overline{L}$ for any computable $L$.

| cite | improve this answer | |
  • $\begingroup$ Adding that the set of recursive functions/languages is (almost trivially) closed against complement, this does indeed provide the answer. $\endgroup$ – Raphael Aug 24 '16 at 9:05
  • $\begingroup$ @Yuval Thanks for your explanation; however, I don't fully understand the conclusion that "$HALT$ cannot be reduced to $\overline L$ for any computable $L$". By "not computable" do you mean not recursive, but recursively enumerable or not recursively enumerable? $\endgroup$ – Brandeis King Aug 24 '16 at 17:51
  • $\begingroup$ Computable and recursive mean exactly the same thing. $\endgroup$ – Yuval Filmus Aug 24 '16 at 17:52

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.