Learning Classes of Approximations to Non-Recursive Functions
Authors: F. Stephan*
and Thomas Zeugmann**
Email: thomas@tcs.uni-luebeck.de
Source: Theoretical Computer Science Vol. 288, Issue 2, 17
September 2002, pp. 309 - 341.
Abstract.
Blum and Blum (Inform. and Control 28 (1975) 125-155) showed that a class
of suitable recursive approximations to the
halting problem K is reliably EX-learnable 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 EX-inferable but
may fail to be reliably EX-learnable, for example if A is non-high 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 EX-learnable. 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 EX-learnable.
This result extends the criticism of Jain et al. (J. Comput. System Sci. 62(1) (2001) 178-212),
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/1-1.
**
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.
|