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.
```