Infinitary self-reference in learning theory

Abstract

Abstract Kleene's second recursion theorem provides a means for transforming any program p into a program e(p) which first creates a quiescent self-copy and then runs p on that self-copy together with any externally given input. e(p), in effect, has complete (low level), self-knowledge, and p represents how e(p) uses its self-knowledge (and its knowledge of the external world). Infinite regress is not required since e(p) creates its self-copy outside of itself. One mechanism to achieve this creation is a self-replication trick isomorphic to that employed by single-celled organisms. Another is for e(p) to look in a mirror to see which program it is. In 1974 the author published an infinitary generalization of Kleene's theorem which he called the operator recursion theorem. It provides a means for obtaining an (algorithmically) growing collection of programs which, in effect, share a common (also growing) mirror from which they can obtain complete low-level models of themselves and the other programs in the collection. These and other recursion theorems have found many applications in, among other domains, Gold-style computational learning theory. Several examples are presented and explained with the intention to teach the use of infinitary (and other) recursion theorems in learning theory. There is also some discussion about the insights those proofs provide.