Combining Models of Approximation with Partial Learning

In Golds framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object infinitely often. Since infinitely many of the learners hypotheses may be incorrect, it is not obvious whether a partial learner can be modifed to approximate the target object. Fulk and Jain (Approximate inference and scientific method. Information and Computation 114(2):179--191, 1994) introduced a model of approximate learning of recursive functions. The present work extends their research and solves an open problem of Fulk and Jain by showing that there is a learner which approximates and partially identifies every recursive function by outputting a sequence of hypotheses which, in addition, are also almost all finite variants of the target function. The subsequent study is dedicated to the question how these findings generalise to the learning of r.e. languages from positive data. Here three variants of approximate learning will be introduced and investigated with respect to the question whether they can be combined with partial learning. Following the line of Fulk and Jains research, further investigations provide conditions under which partial language learners can eventually output only finite variants of the target language. The combinabilities of other partial learning criteria will also be briefly studied.

Partial functions and domination

The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive function {psi} such that for every partial recursive function {phi} and almost every x in the domain of {phi} there is a y in the domain of {psi} with y<= x and {psi}(y) > {phi}(x). While there is a full {pi}01-class of nonrecursive sets where no set is pdominant, there is no {pi}01-class containing only pdominant sets. No weakly 2-generic set is pdominant while there are pdominant 1-generic sets below K. The halves of Chaitins {Omega} are pdominant. No set which is low for Martin-Lof random is pdominant. There is a low r.e. set which is pdominant and a high r.e. set which is not pdominant.