Characterizing language identification in terms of computable numberings

Abstract

Identification of programs for computable functions from their graphs and identification of grammars (r. e. indices) for recursively enumerable languages from positive data are two extensively studied problems in the recursion theoretic framework of inductive inference. In the context of function identification, Freivalds et al. (1984) have shown that only those collections of functions, ℒ, are identifiable in the limit for which there exists a 1-1 computable numbering ψ and a discrimination function d such that (a) for each f ∈ ℒ, the number of indices i such that ψi = f is exactly one and (b) for each f ∈ ℒ, there are only finitely many indices i such that f and ψi, agree on the first d(i) arguments. A similar characterization for language identification in the limit has turned out to be difficult. A partial answer is provided in this paper. Several new techniques are introduced which have found use in other investigations on language identification.