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.”

Supported by the Deutsche Forschungsgemeinschaft (DFG) under Research Grant no. Am 60/9-2.

Supported by the Grant-in-Aid for Scientific Research in Fundamental Areas from the Japanese Ministry of Education, Science, Sports, and Culture under grant no. 10558047. Part of this work was done while visiting the Laboratoire d’Informatique Algorithmique: Fondements et Applications, Université Paris 7. This author is gratefully indebted to Maurice Nivat for providing financial support and inspiring working conditions.