Relative computability for sets of sets

Peter G. Hinman

(University of Michigan)

There are many notions of relative computability for sets of natural numbers: $A\leq_{\cal C}B$ iff there is a $\cal C$-algorithm $\Phi$ which computes $A$ using oracle $B$: $A=\Phi(B)$. Here $\cal C$ may be Turing (recursive), poly-time, etc. Intuitively, $A$ is a problem (is $m\in A$?) which we can solve using $B$.

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.
Tuesday 16th October 2001, 14:00
Robert Recorde Room
Department of Computer Science