Synthesizing learners tolerating computable noisy data

An index for an r.e. class of languages (by definition) generates a sequenc e of grammars defining the class. An index for an indexed family of recursi ve languages (by definition) generates a sequence of decision procedures de fining nr the Family. F. Stephan's model of noisy data is employed, in whic h, roughly, correct data crops up infinitely often and incorrect data only finitely often. In a computable universe, all data sequences. even noisy on es, are computable. New to the present paper is the restriction that noisy data sequences be, nonetheless, computable. This restriction is interesting since we may live in a computable universe. Studied, then, is the synthesi s from indices for r.e. classes and for indexed families of recursive langu ages of various kinds of noise-tolerant language-learners for the correspon ding classes or families indexed, where the noisy input data sequences are restricted to being computable. Many positive results, as well as some nega tive results, are presented regarding the existence of such synthesizers. T he main positive result is: grammars for each indexed family can be learned behaviorally correctly from computable, noisy, positive data. The proof of another positive synthesis result yields, as a pleasant corollary, a stric t subset-principle or telltale style characterization, for the computable n oise-tolerant behaviorally correct learnability of grammars From positive a nd negative data, of the corresponding families indexed. (C) 2001 Academic Press.