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 ?
-
1$\begingroup$ I recommend looking an online lecture notes on computability theory. $\endgroup$– Yuval FilmusJan 31, 2016 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, 2016 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, 2016 at 11:15
-
$\begingroup$ Also asked as a subquestion of: cs.stackexchange.com/questions/12747/… $\endgroup$– Ciro Santilli Путлер Капут 六四事Dec 26, 2020 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$.
-
$\begingroup$ Third line: did you mean: while $\bar{L}$ is not recursive $\endgroup$– UpcFeb 6, 2019 at 4:16
-
$\begingroup$ A language is recursive iff its complement is recursive. $\endgroup$ Feb 6, 2019 at 4:47