Extremes in the degrees of inferability (Q1319507): Difference between revisions

Formal learning theory tries to describe which classes of theories are learnable under which information presentation conditions, using a learning system with given capacities. Theories are often represented by functions. Then the question is how to infer a function \(f\) from observations about the behavior of \(f\). Usually these observations include the answers obtained from a teacher answering questions about the function. In this paper, the authors study in a more general setting the inference capacities of inference machines that also might consult colleagues, not necessarily teachers, about \(f\). Such colleagues function as oracles for the inference machine. Then the question is how to discriminate between those oracles. Two oracles are called equivalent (w.r.t. a given inference machine) if they allow the same functions to the mastered by the machine. Then some results are proven if two extreme equivalence classes are examined: What are the oracles that are of no help to the machine? And which oracles allow the learner to infer the set of all recursive functions?