The Strength of Noninclusions for Teams of Finite Learners (Extended Abstract)

Abstract

In team learning one considers a set of n learning machines and requires that m out of n must be successful. Comparing the power of different teams of learning machines is a major topic of inductive inference. It is centered around the “inclusion problem”: When is an (m, n)-team more powerful than an (m′,n′)-team? In this paper we show that there are noninclusions of different strength for teams of finite learners (i.e., EX0-teams). We measure the strength of a noninclusion [m, n]EX0 ⊈[m′n′]EX0-team. If any such A exists then we may take A = K where K is the halting problem, and for Popperian learners a K-oracle is also necessary. In contrast, for the noninclusion [29,49]EX0&nsube[2,4]EX0 weaker oracles suffice, and we characterize them as exactly those sets which are Turing-equivalent to a complete and consistent extension of Peano Arithmetic.