Due Date: Tuesday, February 22, 2005
Let A be an oracle. By an A-algorithm, we mean an algorithm that uses A as an oracle. Correspondingly, we can define A-decidable and A-r.e. sets.
1. Prove that if the two sets S and T are A-decidable, their union, intersection, and a complement to S are also A-decidable.
2. Prove that if S and T are A-r.e., then their union and intersection is also A-r.e.