Enlarging learnable classes

We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.

Authors

• Sanjay Jain
• Timo Kötzing
• Frank Stephan

Keywords

• Inductive inference
• Learning in the limit
• Total recursive functions
• Non-union theorem