Note on a central lemma for learning theory (Q794446): Difference between revisions

The paper is a contribution to text identification in learning theory. It begins with the enunciation and proof of a classical result - the Blum and Blum Lemma about the existence of finite locking sequences for any learning function f and any language L which f identifies [\textit{L. Blum} and \textit{M. Blum}, Inf. Control 28, 125-155 (1975; Zbl 0375.02028)]. The importance of this Lemma and some of its applications are also presented. Then, the metric \(d(t,s)=\sum_{t_ n\neq s_ n}2^{-n}\) is introduced on \({}^ NN\) (the set of infinite sequences with elements from N), and \((^ NN,d)\) becomes a complete metric space. The Blum and Blum Lemma is reformulated and proved in this context. This result appears now as a consequence of rather general, topological considerations. The usefulness of this approach is then emphasized, by proving other interesting results about other learning paradigms.