EXTREMES IN THE DEGREES OF INFERABILITY

Most theories of learning consider inferring a function f from either (1) observations about for, (2) questions about f. We consider a scena rio whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I [A ] is the set of concept classes I- Learnable by an inductive inference machine with oracle A. A and Bare I-equivalent if I[A] = I[B]. The equivalence classes induced are the d egrees of inferability. We prove several results about when these degr ees are trivial, and when the degrees are omniscient (i.e., the set of recursive function is learnable).