Recursion theoretic characterizations of language learning

An attempt is made to build "bridges " between machine language learning and recursive function theory. Formal language learning classes are charac terized in terms of recursion theoretic notions like standardizing operations and recursively enumerable classes. Connections between Gold's seminal notion of identification, referred to as TxtEx-identification, and standardizing operations are investigated. It is shown that the class of languages that can be TxtEx-identified is properly contained in the class of languages that are limit-effectively standardizable. A restricted form of standardizability, which has the same power as TxtEx identification, is presented. The notion of TxtEx-identification is relaxed (by providing additional information about the language being learned), so that the classes of languages that can be identified by this new criterion are exactly the same as the classes of languages that are limit-effectively standardizable. A connection between the above criteria and r.e. class of languages is also investigated. It is shown that for the class of languages identified by the above criteria, there exists a computable numbering that has exactly one index for infinite languages in the class and a finite number of indices for the finite languages in the class. Motivation for these characterizations are derived from the work of Freivalds. Kinber, and Wiehagen on the inference of programs for recursive functions from their graphs. However, new notions have to be invented to characterize language learning, and proofs are considerably more difficult.