On the Uniform Learnability of Approximations to Non-Recursive Functions

Abstract

Blum and Blum (1975) showed that a class $ \mathcal{B} $ of suitable recursive approximations to the halting problem is reliably EX -learnable. These investigations are carried on by showing that $ \mathcal{B} $ is neither in NUM nor robustly EX -learnable. Since the definition of the class $ \mathcal{B} $ is quite natural and does not contain any self-referential coding, $ \mathcal{B} $ serves as an example that the notion of robustness for learning is quite more restrictive than intended. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes $ \mathcal{U} $ ( A ) are still EX -inferable but may fail to be reliably EX -learnable, for example if A is non-high and hypersimple. Additionally, it is proved that $ \mathcal{U} $ ( A ) is neither in NUM nor robustly EX -learnable provided A is part of a recursively inseparable pair, A is simple but not hypersimple or A is neither recursive nor high. These results provide more evidence that there is still some need to find an adequate notion for “naturally learnable function classes.”