How to proof that a language is not recursively enumerable

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 $w\in 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