Separation of uniform learning classes

Author: Sandra Zilles

Source: Theoretical Computer Science Vol. 313, Issue 2, 17 February 2004, pp. 229-265.

Abstract. Within the scope of inductive inference a recursion theoretic approach is used to model learning behaviour. The fundamental model considered is Gold's identification of recursive functions in the limit. Modifying the corresponding definition has proposed several inference classes, which have been compared regarding the capacities of the relevant learners. The present paper is concerned with a meta-version of this learning model. Given a description of a class of target functions, a uniform learner is supposed to develop a specific successful method for learning the represented class. The same modifications as in the elementary model are considered in the context of uniform learning, especially respecting identification capacities. It turns out that the former separations of inference classes are reflected on the meta-level, in particular finite classes of recursive functions –– which constitute the most simple learning problems in the elementary model –– are evidence of these separations.

©Copyright 2004 Elsevier Science B.V.