Learning via queries

Abstract

Traditional work in inductive inference has been to model a learner receiving data about a function f and trying to learn the function. The data is usually just the values f (0), f (1),…. The scenario is modeled so that the learner is also allowed to ask questions about the data (e.g., (∀ χ) [χ> 17 → f ( χ ) = 0]?). An important parameter is the language that the lerner may use to formulate queries. We show that for most languages a learner can learn more by asking questions than by passively receiving data. Mathematical tools used include the solution to Hilbert's tenth problem, the decidability of Presuburger arithmetic, and ω-automata.