Machine inductive inference and language identification

It is shown that for some classes of recursive languages, from the characteristic function of any L in ℒ an approximate decision procedure for L with no more than n+1 mistakes can be (uniformly effectively) inferred in the limit; whereas, in general, a grammar with no less than n mistakes cannot be inferred.

Abstract

We show that for some classes ℒ of recursive languages, from the characteristic function of any L in ℒ an approximate decision procedure for L with no more than n+1 mistakes can be (uniformly effectively) inferred in the limit; whereas, in general, a grammar (generation procedure) with no more than n mistakes cannot; for some classes an infinite sequence of perfectly correct decision procedures can be inferred in the limit, but single grammars with finitely many mistakes cannot; and for some classes an infinite sequence of decision procedures each with no more than n+1 mistakes can be inferred, but an infinite sequence of grammars each with no more than n mistakes cannot. This is true even though decision procedures generally contain more information than grammars. We also consider inference of grammars for r.e. languages from arbitrary texts, i.e., enumerations of the languages. We show that for any class of languages ℒ, if some, machine, from arbitrary texts for any L in ℒ, can infer in the limit an approximate grammar for L with no more than 2·n mistakes, then some machine can infer in the limit, for each language in ℒ, an infinite sequence of grammars each with no more than n mistakes. This reduction from 2·n to n is best possible. From these and other results we obtain and compare several natural, inference hierarchies. Lastly we show that if we restrict ourselves to recursive texts, there is a machine which, for any r.e. language, infers in the limit an infinite sequence of grammars each with only finitely many mistakes. We employ recursion theoretic methods including infinitary and ordinary recursion theorems.