On the Uniform Learnability of Approximations to Non-recursive Functions.

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." [ABSTRACT FROM AUTHOR]