FROM INDUCTIVE INFERENCE TO ALGORITHMIC LEARNING-THEORY

We present two phenomena which were discovered in pure recursion-theor etic inductive inference, namely inconsistent learning (learning strat egies producing apparently ''senseless'' hypotheses can solve problems unsolvable by ''reasonable'' learning strategies) and learning from g ood examples (''much less'' information can lead to much more learning power). Recently, it has been shown that these phenomena also hold in the world of polynomial-time algorithmic learning. Thus inductive inf erence can be understood and used as a source of potent ideas guiding both research and applications in algorithmic learning theory.