6
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Smajl Oct 23 '14 at 10:08
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 23 '14 at 10:11
  • $\begingroup$ 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. $\endgroup$ – Smajl Oct 23 '14 at 10:13
  • $\begingroup$ @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. $\endgroup$ – David Richerby Oct 23 '14 at 10:18
  • $\begingroup$ @DavidRicherby: Are you saying that the halting problem is not r.e.? $\endgroup$ – A.Schulz Dec 4 '14 at 15:14
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – chi Feb 7 '17 at 15:24
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Feb 7 '17 at 15:31

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.