Mathematical Boundaries of Learning.

 

Inductive Inference studies the learning of function in the limit, where the learner M reads the infinite string f(0),f(1),... and outputs in parallel to this process a sequence of hypotheses. M learns f in the limit iff these hypotheses converge syntactically to a program for f. The talk presents this notion and shows what classes of recursive functions can be learned and what not. Furthermore, the notion of learning in the limit is compared with other proposals to model the process of learning and some recent developments in Inductive Inference are presented.