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
