No label defined (Q4348129)

The field of inductive inference studies the problem of learning in a formal context. Particularly, learning refers to the successful inference of a class of functions from which some finite domain-value pairs are given successively to an inference machine (a total Turing machine) by a teacher. After each new piece of information about the function to be inferred, the learner has to make a guess about the identity of this function. Normally, we do not care about the initial (almost always wrong answers of the machine), but look at the properties of the sequence of answers thus obtained: for example, does it converge to one and the same answer and is this answer correct? In this overview the authors pay attention to a number of variables that may affect the success of an inference machine. For example, what happens if we restrict the number of mind changes the machine is allowed to make in stating its guesses (changing the machine model), what happens if the machine is allowed to ask the teacher about properties of the input given, using some fixed query language (changing the machine model), or what happens if the function guessed differs from the function presented on (in)finitely many input-output pairs (changing the output). In this paper most attention has been given to results about query inference, allowing the learner to ask questions about the function to be inferred and what happens if the learner is also allowed to consult an oracle for help. For the entire collection see [Zbl 0865.00036].