What's an example of a language that is not recursively enumerable and whose complement is also not recursively enumerable?

  • $\begingroup$ Any language that is neither $\Sigma^0_1$ nor $\Pi^0_1$. The set of indices of total computable functions, the set of indices of partial computable functions with a bounded range, etc. $\endgroup$ – Carl Mummert Dec 21 '13 at 1:56

A language is r.e. if and only if it is $\Sigma^0_1$, which is to say if it can be defined with a formula of the form $(\exists t)P(n,t)$ where $P$ is a computable predicate.

So languages whose definition requires several nested quantifiers will not be r.e., and their complement will not be r.e.

A few examples include:

  • The second Turing jump of the empty set, $\emptyset''$. This set is $\Sigma^0_2$. By Post's theorem it is $\Sigma^0_2$ complete, and thus not at any lower level of the arithmetical hierarchy.

  • The set of indices of total Turing machines. This set is $\Pi^0_2$. ("For all $n$ there is a $t$ such that $\phi_e(n)$ halts in $t$ steps".)

  • The set of indices of partial computable functions that have a bounded range. This set is $\Sigma^0_2$. ("There is a $k$ such that for all $n$ and $t$, if $\phi_e(n)$ halts in $t$ steps then the result is less than $k$").

The usual way of proving that these cannot be defined with fewer quantifiers is to show that the truth predicate for that level of the arithmetical hierarchy can be many-one reduced to an instance of the problem at hand.

For example, if $\psi \equiv (\forall n)(\exists m)Q(n,m)$ is an arbitrary $\Pi^0_2$ sentence, where $Q$ is a computable predicate, we can make an index for a partial computable function $g(n) = (\mu m)Q(n,m)$. Then $g$ is total if and only if $\psi$ holds, and an index for $g$ can be computed uniformly from a Godel number for $\psi$.

  • $\begingroup$ Thanks very much. Does $(\mu m)\psi(m)$ here mean the smallest $m$ for which $\psi(m)$ holds? $\endgroup$ – MJD Dec 21 '13 at 17:37
  • $\begingroup$ Yes, $(\mu m)\psi(m)$ is the smallest $m$ for which $\psi(m)$ holds, if there is any such $m$, and $(\mu m)\psi(m)$ is undefined (diverges as a computation) otherwise. So $\mu$ is an unbounded search operator. $\endgroup$ – Carl Mummert Dec 21 '13 at 18:32
  • $\begingroup$ Thanks again. I'm glad that the answer turned out to be something I wouldn't have been able to figure out by myself. $\endgroup$ – MJD Dec 21 '13 at 21:36

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.