[Solved]: Recursive, Recursively Enumerable and None of the Above

Problem Detail: 

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?

Asked By : Andrew Tomazos

Answered By : David Lewis

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2304

 Ask a Question

 Download Related Notes/Documents