Learnability of Enumerable Classes of Recursive Functions from ``Typical'' Examples

Author: Jochen Nessel.

Source: Lecture Notes in Artificial Intelligence Vol. 1720, 1999, 264 - 275.

The paper investigates whether it is possible to learn every enumerable classes of recursive functions from ``typical'' examples. ``Typical'' means, there is a computable family of finite sets, such that for each function in the class there is one set of examples that can be used in any suitable hypothesis space for this class of functions. As it will turn out, there are enumerable classes of recursive functions that are not learnable from ``typical'' examples. The learnable classes are characterized.

The results are proved within an abstract model of learning from examples, introduced by Freivalds, Kinber and Wiehagen. Finally, the results are interpreted and possible connections of this theoretical work to the situation in real life classrooms are pointed out.

©Copyright 1999 Springer-Verlag