Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
I believe that everything you need may be in the corresponding wp article. Is the problem that the examples are too complicated? –  jmad Jun 9 '12 at 23:04
    
For $C$, choose the complement of any language from $B$. –  Raphael Jun 10 '12 at 11:14
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
These are indeed the canonical examples. –  Raphael Jun 10 '12 at 11:13
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.