Recursive, Recursively Enumerable and None of the Above

Question

Let

• $A = \mathrm{R}$ be the set of all languages that are recursive,
• $B = \mathrm{RE} \setminus \mathrm{R}$ be the set of all languages that are recursively enumerable but not recursive and
• $C = \overline{\mathrm{RE}}$ be the set of all languages that are not recursively enumerable.

It is clear that for example $\mathrm{CFL} \subseteq A$.

What is a simple example of a member of set B?

What is a simple example of a member of set C?

In general, how do you classify a language as either A, B or C?

Answer 1

You can choose the language of the halting problem

$\qquad \displaystyle B_1 = \{\langle T \rangle \mid T \text{ halts on } \langle T \rangle\} \in B$

and its complement

$\qquad \displaystyle C_1 = \overline{B_1} \in C$.

This is fairly standard material. The proof for $B_1$ not being recursive is the well-known diagonalization. Proving $B_1$ to be RE (recursively enumerable) is a tad tricky, involving interleaved simulation of multiple TMs, but is widely documented. If $C_1$ were RE, then $B_1$ being RE would imply that both are recursive; hence $C_1$ is not RE. This illustrates some of the techniques for such proofs in general.

Answer 2

To add to David Lewis's answer, I will answer the final part of your question. To show that a language L is in A (this set is usually denoted as R) there are (at least) 3 popular techniques:

1. Show there exists a turing machine M that halts on all input (this means it will always stop) and that accepts a word $w$ if and only if $w \in L$. This is the definition of R.
2. Show a Turing reduction from L to any other language K that is known to be in R. Intuitively this means that L is easier then K, and if K is recursive so is L.
3. Show that L is in B (usually denoted as RE) and co-RE (All the languages K s.t. $K^c \in$ RE). This will show that L is in R because R = RE $\cap$ co-RE.

To show that a language L is in B (RE) you can either:

1. Show there exists a turing machine M that halts and accepts on every w $\in$ L. This is the defenition of RE. Notice that unlike in A1, you don't care if M halts or keeps running forever on any w $\notin$ L, as long as it doesn't accept it.
2. Show a Turing reduction from L to any other language K that is known to be in RE.

To show that a language L is in co-RE you need to show that $L^c\in RE$. Again, this is from the defenition of co-RE.

An important fact is that the set C you defined is not equal to co-RE. There are languages that are neither in RE or in co-RE.