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.
©Copyright 1999, Springer-Verlag.