CS 5315, Quiz 1, Thursday, March 12, 2009

1. Is the union of a r.e. set and a decidable set always r.e.? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample.

2. Is the union of a r.e. set and a decidable set always decidable? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample.

3. Prove that halting problem is no decidable.

4. Prove, from scratch, that the relation a <= b is primitive recursive.

4a. Prove that the relation a <= b is mu-recursive.