Learning Classes of Approximations to NonRecursive Functions
Authors: F. Stephan^{*}
and Thomas Zeugmann^{**}
Source: Theoretical Computer Science Vol. 288, Issue 2, 17 September 2002, pp. 309  341. Abstract. Blum and Blum (Inform. and Control 28 (1975) 125155) showed that a class of suitable recursive approximations to the halting problem K is reliably EXlearnable but left it open whether or not is in NUM. By showing to be not in NUM we resolve this old problem. 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 EXinferable but may fail to be reliably EXlearnable, for example if A is nonhigh and hypersimple. Blum and Blum (1975) considered only approximations to K defined by monotone complexity functions. We prove this condition to be necessary for making learnability independent of the underlying complexity measure. The class of all recursive approximations to K generated by all total complexity functions is shown to be not even behaviorally correct learnable for a class of natural complexity measures. On the other hand, there are complexity measures such that is EXlearnable. A similar result is obtained for all classes ^{}. For natural complexity measures, is shown to be not robustly learnable, but again there are complexity measures such that and, more generally, every class is robustly EXlearnable. This result extends the criticism of Jain et al. (J. Comput. System Sci. 62(1) (2001) 178212), since the classes defined by artificial complexity measures turn out to be robustly learnable while those defined by natural complexity measures are not robustly learnable.
^{*}Supported by the Deutsche Forschungsgemeinschaft (DFG) under Heisenberg grant no.Ste 967/11.
^{**}
Supported by the
GrantinAid for Scientific Research in Fundamental Areas from the
Japanese Ministry of Education,
Science, Sports, and Culture under grant no. 10558047.

©Copyright 2002 Elsevier Science B.V.