On the Uniform Learnability of Approximations to Non-Recursive Functions Authors: Frank Stephan* and Thomas Zeugmann** Source: Algorithmic Learning Theory, 10th International Conference, ALT'99, Tokyo, Japan, December 1999, Proceedings, (Osamu Watanabe and Takashi Yokomori, Eds.), Lecture Notes in Artificial Intelligence 1720, pp. 276 - 290, Springer-Verlag 1999. Abstract. Blum and Blum (1975) showed that a class of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that is neither in NUM nor robustly EX-learnable. Since the definition of the class is quite natural and does not contain any self-referential coding, 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 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 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. ©Copyright 1999, Springer-Verlag.