CS 5315, Quiz #1

Date: Tuesday, February 15, 2005

1. What is a recursively enumerable (r.e.) set?

Answer:

A set is called recursively enumerable (r.e.) 
if there exists an algorithm that eventually 
produces all the elements of this set.
2. Prove that the union of two r.e. sets is r.e.

Answer: 

Since the set A is r.e., there exist an algorithm a that eventually
generates all the elements of this set. Similarly, 
since the set B is r.e., there exist an algorithm b that eventually
generates all the elements of this set. So produce all the element of
the union, we do the following:
* run a for 1 hour
* run b for 1 hour
* run a for one more hour
* run b for one more hour
etc. Eventually, all elements of A and all elements of B will be
generated. We thus have an algorithm for generating all the elements
from the union. So, the union is indeed r.e.
3. Prove that the intersection of two r.e. sets is r.e.

Answer: 

Similarly to the union case, there exist algorithms a and b that
generate all the elements of the set A (corr., set B). To generate all 
the elements of the intersection, we do the following: 
* run a for 1 hour, print the results into a A list
* run b for 1 hour, print the results into a B list
* compare the two lists and print the common elements
* run a for one more hour, add the results to the A list 
* run b for one more hour, add the results to the B list 
* compare the two lists and print the common elements
etc. Eventually, all common elements of A and B will be
generated. We thus have an algorithm for generating all the elements
from the intersection. So, the intersection is indeed r.e.