1

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

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 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. – Carl Mummert Dec 21 '13 at 01:56

1 Answers1

1

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$.

Carl Mummert
  • 81,604
  • Thanks very much. Does $(\mu m)\psi(m)$ here mean the smallest $m$ for which $\psi(m)$ holds? – MJD Dec 21 '13 at 17:37
  • 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. – Carl Mummert Dec 21 '13 at 18:32
  • Thanks again. I'm glad that the answer turned out to be something I wouldn't have been able to figure out by myself. – MJD Dec 21 '13 at 21:36