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.