# How to prove that a language is not recursively enumerable

How does one prove that some arbitrary language $$L$$ is not recursively enumerable?

I know I can prove that the 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.

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.

• Thanks for the answer. One more thing: I thought that the language $\{(R(M),w) | M$ halts on input $w\}$ (the set representing the halting problem) is recursively enumerable. How can I use it to prove that a problem is NOT in RE? – Smajl Oct 23 '14 at 10:08
• You seem to have misunderstood, perhaps because of a typo I just fixed. Any kind of machine has its own halting problem: "Does a machine $M$ of that type halt when given input $w$?" The halting problem $H$ for Turing machines is RE; the halting problem for Turing machines that have an oracle for $H$ is not RE. – David Richerby Oct 23 '14 at 10:11
• Ok, perhaps I do not fully understand the concept of the oracle based TM but thanks for the answer! I will take a look at it. – Smajl Oct 23 '14 at 10:13
• @Smajl Wikipedia has a decent page on oracle machines. If that helps, great! If it doesn't, ask another question, as long as you can formulate something reasonably specific. – David Richerby Oct 23 '14 at 10:18
• @DavidRicherby: Are you saying that the halting problem is not r.e.? – A.Schulz Dec 4 '14 at 15:14

Some common techniques include:

We start by picking any $L'$ which is known to be non RE, e.g. we let $L'$ to be the complement of the halting problem. Then we prove the m-reduction $L' \leq_m L$. If we can do that, we can conclude that $L$ is not RE, since otherwise $L'$ would be RE -- contradiction.

The Rice-Shapiro theorem is a very convenient and widely applicable method to establish "non-RE" properties. It is not a silver bullet which always applies, but many common languages are covered by it.

• I just realized that this question is very old, and was only recently bumped to the front page by an edit. Oh well -- I'll leave this answer here anyway... – chi Feb 7 '17 at 15:24
• There's no problem at all with having good new answers to old questions. In particular, we might hope to turn this into a reference question that we can use when people want help with their computation theory exercises. And Stack Exchange as a whole is supposed to be helpful to people who find the site by Googling for help with their own problems, not just the person who asked the original question. – David Richerby Feb 7 '17 at 15:31