Program size restrictions in computational learning

Abstract

A model for a subject S learning its environment E could be described thus: S, placed in E, receives data about E, and simultaneously conjectures a sequence of hypotheses. S is said to learn E just in case the sequence of hypotheses conjectured by S stabilizes to a final hypothesis which correctly represents E. Computational learning theory provides a framework for studying problems of this nature when the subject is a machine. A natural abstraction for the notion of hypothesis is a computer program. The present paper, in the above framework of learning, presents arguments for the final hypothesis to be succinct, and introduces a plethora of formulations of such succinctness. A revelation of this study is that some of the "natural" notions of succinctness may be uninteresting because learning capability of machines under these seemingly natural constraints is dependent on the choice of programming system used to interpret hypotheses. © 1994.