# Non Recursively Enumerable Languages

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 ?

• I recommend looking an online lecture notes on computability theory. Jan 31 '16 at 9:18
• This is a general reference question. Wikipedia contains examples, and it's quite clear (assuming some mastery of the fundamentals) that the complents of all undecidable yet semi-decidable languages are examples as well. So I don't see how this question should be asked in this form. Community votes, please: is this unclear?
– Raphael
Jan 31 '16 at 11:14
• " What makes a language non recursively enumerable ? " -- what kind of answer are you looking for? They are, or they are not.
– Raphael
Jan 31 '16 at 11:15
• Also asked as a subquestion of: cs.stackexchange.com/questions/12747/… Dec 26 '20 at 11:19

## 2 Answers

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.

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

• Third line: did you mean: while $\bar{L}$ is not recursive
– Upc
Feb 6 '19 at 4:16
• A language is recursive iff its complement is recursive. Feb 6 '19 at 4:47