Extremes in the degrees of inferability

Abstract Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f . We consider a scenario 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 B are I-equivalent if I [ A ] = I [ B ]. The equivalence classes induced are the degrees of inferability . We prove several results about when these degrees are trivial, and when the degrees are omniscient (i.e., the set of recursive function is learnable).