4
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ I recommend looking an online lecture notes on computability theory. $\endgroup$ – Yuval Filmus Jan 31 '16 at 9:18
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Jan 31 '16 at 11:14
  • 1
    $\begingroup$ " What makes a language non recursively enumerable ? " -- what kind of answer are you looking for? They are, or they are not. $\endgroup$ – Raphael Jan 31 '16 at 11:15
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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.