How to proof that a language is not recursively enumerable

ignougroup
Problem Detail: How does one prove that some arbitrary language $L$ is not recursively enumerable. I know I can proof that language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all words in the language (and the language would be even recursive if $M$ halts on all inputs). But it is not clear to me how to prove that language in not RE. I was thinking about showing the fact, that such TM could not be constructed for a given language, but proving non-existence is always difficult.

Asked By : Smajl

Answered By : David Richerby

Here are two methods.

Consider the complement

Theorem. If a language $L$ and its complement are both RE, they are both recursive. Proof. Decide whether $win L$ by enumerating $L$ and its complement in parallel and accept/reject as soon as $w$ appears in one of the enumerations. $Box$ So, if you can prove that $L$ is not recursive but its complement is RE, then $L$ is not RE.

Halting problems

Theorem. Let $mathcal{M}$ be the class of Turing machines equipped with an oracle for the ordinary Turing machine halting problem. The halting problem for $mathcal{M}$ is not RE. Proof. Essentially the same as the proof that the ordinary Turing machine halting problem is not recursive. $Box$ So, if you can reduce the halting problem for $mathcal{M}$ to your problem, your problem is not RE.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32226