CS 5315 Homework #10

Date Assigned: Thursday, February 17, 2005

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.