Training sequences

AbstractIntuitively, the more a machine knows the more it can learn. This intuition is formalized in a recursion theoretic framework. A formal definition of what it means for a machine to learn a finite sequence of recursive functions is presented. We prove that there are sets of sequences S, and a sequence 〈ƒ1, ƒ2, …, ƒn〉ϵ S such that in order to learn a program for ƒi a machine must necessarily know programs for ƒ1, …, ƒi−1. Also investigated is the simultaneous inference of programs for a finite set of recursive functions