For each $\cal C$ there is a corresponding notion for classes of sets: $P\;\dot\leq_{\cal C}\;Q$ iff for some $\Phi\in{\cal C}$, for all $B\in Q$, $\Phi(B)\in P$. Here the intuition is that solving {\it some} $A\in P$ is the goal which can be accomplished given a solution for {\it some} $B\in Q$.

In each case most attention has been paid to restricted versions --- for example, to relative Turing computability on the recursively enumerable sets. We describe an analogous restriction of Turing computability to $\Pi^0_1$ classes of sets --- membership of a set $A$ in a $\Pi^0_1$ class is determined by an effective condition on all initial segments of $A$. Many familiar problems, such as finding graph colorings and consistent extensions of theories can be naturally viewed as $\Pi^0_1$ classes. We discuss properties of relative Turing computability on $\Pi^0_1$ classes and and suggest some directions for further research.

Robert Recorde Room

Department of Computer Science