Control Structures in Hypothesis Spaces: The Influence on Learning

. In any learnability setting, hypotheses are conjectured from some hypothesis space. Studied herein are the effects on learnability of the presence or absence of certain control structures in the hypothesis space. First presented are control structure characterizations of some rather specific but illustrative learnability results. Then presented are the main theorems. Each of these characterizes the invariance of a learning class over hypothesis space V (and a little more about V ) as: V has suitable instances of all denotational control structures. 1 Introduction In any learnability setting, hypotheses are conjectured from some hypothesis space, for example, in [OSW86] from general purpose programming systems, in [ZL95, Wie78] from subrecursive systems, and in [Qui92] from very simple classes of classificatory decision trees. 3 Much is known theoretically about the restrictions on learning power resulting from restricted hypothesis spaces [ZL95]. In the present paper we begin to..