Non Recursively Enumerable Languages

Question

Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?

Answer 1

Every undecidable yet semi-decidable language provides an example: its complement.

That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.

You should know at least one such language from class.

The Halting language, and probably numerous others from exercise problems.

Answer 2

An example of a language which is not recursively enumerable is the language $L$ of all descriptions of Turing machines which don't halt on the empty input. We know that $\overline{L}$ is recursively enumerable (exercise) while $L$ is not recursive (this is Turing's classical result), so it follows that $L$ is not recursively enumerable.

For a deeper look, we have to delve into the arithmetical hierarchy. We can write $L$ symbolically as follows: $$ L = \{ \langle M \rangle : \forall t \text{ $M$ doesn't halt within $t$ steps}\}. $$ The reason for expressing $L$ in this particular way is that the predicate $\phi(\langle M \rangle,t)$ which holds when $M$ doesn't halt within $t$ steps is recursive (exercise). So $$ L = \{ \langle M \rangle : \forall t \phi(\langle M \rangle, t) \}, $$ where $\phi$ is some computable predicate. This puts $L$ in the complexity class $\Pi_1$ (here $1$ means that there is $1$ quantifier alternations, and $\Pi$ means that the first quantifier is $\forall$; in contrast $\overline{L} \in \Sigma_1$, since for $\overline{L}$ the first quantifier is $\exists$). Note that $\Sigma_1$ consists of all recursively enumerable languages, while $\Pi_1$ consists of all co-r.e. languages.

It so happens that $L$ is $\Pi_1$-complete. This means that for every language $A \in \Pi_1$ there is a computable reduction $f$ such that $x \in A$ iff $f(x) \in L$. I outline a proof below. Turing's argument implies that $\Pi_1 \neq \Sigma_1$, and in particular no $\Pi_1$-complete language (or more generally, no $\Pi_1$-hard language) can belong to $\Sigma_1$.

It remains to show that $L$ is $\Pi_1$-complete. Consider any language $A \in \Pi_1$, so $A = \{ x : \forall y \psi(x,y) \}$, where $\psi$ is computable. The function $f$ will construct a Turing machine that runs $\psi(x,y)$ on all values of $y$, and terminates if it finds a value of $y$ for which $\psi(x,y)$ is false. Thus $x \in A$ iff $f(x) \in L$.