Recursive and Recursively Enumerable Sets

The two theorems worth knowing

These are proved properly in chapter 70. They are stated here because they are the form the examination asks for, and because the first one explains the second.

Theorem 1. Every recursive set is recursively enumerable.

Immediate: a machine that always halts with an answer is in particular a machine that accepts exactly the members, so the definition of recursively enumerable is satisfied without changing anything.

Theorem 2. A set is recursive if and only if both it and its complement are recursively enumerable.

The forward half is easy: if the set is recursive, swap the accept and reject outcomes of its machine and the complement is recursive too, hence recursively enumerable by theorem 1.

The backward half is the useful one and the construction is worth remembering. Suppose L has a machine M and the complement of L has a machine N, each accepting its own set and possibly running for ever otherwise. Build a machine that runs M and N side by side, one step of each in turn. Any input is in L or in the complement of L, so one of the two must accept eventually. If M accepts, accept. If N accepts, reject. So the combined machine always halts with the right answer, and L is recursive.

Running two machines in turn rather than one after the other is the whole trick, and it has a name: dovetailing. It matters because running M to completion first is exactly what does not work, since M may never finish.

The consequence that gets examined. If L is recursively enumerable and its complement is not, then L is not recursive. That is how chapter 75 shows a second problem undecidable once the first has been done, and it is why the complement is worth asking about at all.

Which class each type of grammar lands in

This is the connection to chapter 26 and the reason MU puts the label here.

So the top of the Chomsky hierarchy is exactly the recursively enumerable sets, and the three lower classes are all recursive. The recursive sets sit strictly between the context sensitive and the recursively enumerable ones: every context sensitive language is recursive, not every recursive language is context sensitive, and not every recursively enumerable language is recursive.

That gives a five level picture rather than the four of chapter 26, and it is worth drawing once:

with every containment proper.

A worked example of the difference

The example is a problem rather than a machine, because the machines are Module 2's.

A recursive set. The set of strings over {a, b} with equally many a and b. Given a string, count the a, count the b, compare. That procedure always finishes, in one pass, so the set is recursive.

A recursively enumerable set that is not recursive. The set of pairs consisting of a program and an input on which that program eventually stops. A machine can enumerate this set: run every program on every input a few steps at a time, dovetailing as above, and print each pair as soon as its program stops. Every pair where the program does stop is printed eventually. But no machine can decide the set, because deciding it would require saying no for a program that has not stopped yet and never will, and chapter 74 proves that impossible.

So the difference between the two definitions is the difference between a program you can wait on and a question you can answer.

Enumerating in order, which is a third notion

Worth knowing because it explains the word enumerable and because it makes theorem 2 obvious.

A recursively enumerable set can be listed in some order. A set that can be listed in increasing order, by length and then alphabetically, turns out to be exactly a recursive set. The reason is short: to decide whether w is in the set, list the set in order until you reach w or pass it. If the set is listed in order you must eventually do one or the other, so the procedure halts. And conversely a recursive set can be listed in order by testing every string in canonical order and printing the ones that pass.

So the three notions line up:

Distinctions

What it does NOT mean

Recursive here has nothing to do with a function calling itself. It means decidable. The collision of vocabulary is historical.

Recursively enumerable does not mean you can list the non members. That is the complement, and the theorem above says having both lists makes the set recursive. Most recursively enumerable sets do not have both.

A machine that runs for ever has not rejected. It has not answered. Treating a long run as a no is exactly the mistake the definitions exist to prevent.

Not recursive does not mean not describable. The halting set is perfectly describable in one English sentence. It is not decidable, which is a different thing.

Enumerable does not mean finite. Most of these sets are infinite; enumerable is about being listable, which chapter 7 called countable.

Quick revision

• Recursively enumerable, also semi decidable: a machine accepts every member and never accepts a non member,

but may run for ever on a non member.

• Recursive, also decidable: a machine accepts every member, rejects every non member, and always halts.
• Every recursive set is recursively enumerable. The converse fails, and chapter 74 provides the witness.
• A set is recursive if and only if it and its complement are both recursively enumerable, proved by running

the two machines side by side, which is called dovetailing.

• So if a set is recursively enumerable and its complement is not, the set is not recursive.
• Type 0 grammars generate exactly the recursively enumerable languages; types 1, 2 and 3 all generate

recursive ones.

• The full chain, all containments proper: regular, context free, context sensitive, recursive, recursively

enumerable.

• Listable in some order means recursively enumerable; listable in increasing order means recursive.

Test yourself

1. Give the two definitions and the one difference between them. Recursively enumerable: a machine accepts exactly the members, and on a non member may reject or run for ever. Recursive: the same, except that it must always halt, so a non member is always rejected. The difference is whether the machine is permitted not to answer.

2. State and prove that a recursive set is recursively enumerable. A recursive set has a machine that always halts and accepts exactly its members. That machine already satisfies the definition of recursively enumerable, since accepting exactly the members is all that is required. No construction is needed.

3. State the complement theorem and sketch the construction. A set is recursive exactly when it and its complement are both recursively enumerable. Given machines M for the set and N for the complement, run one step of each alternately; every input is in one or the other, so one must accept eventually, and the combined machine answers accordingly and always halts.

4. Why is running M to completion before starting N wrong? Because M may never complete on an input outside the set, in which case N is never started and the combined machine never answers, which is exactly the failure the theorem is meant to avoid.

5. Which class of languages does a type 0 grammar generate, and which classes are recursive? Type 0 generates exactly the recursively enumerable languages. The regular, context free and context sensitive classes are all recursive, and each is properly contained in the next.

6. A student says a set is not recursively enumerable because their machine ran for an hour without answering. Correct them. A long run is not evidence of anything. The definition of recursively enumerable permits the machine to run for ever on a non member, and the definition of recursive requires a proof that the machine always halts, not an observation that it usually does.