Taming teams with mind changes

摘要

This paper is concerned with the algorithmic learning where the learner is allowed to make a finite but bounded number of mind changes. Briefly, in our learning paradigm, a learner is given examples from a recursive function, which the learner attempts to learn by producing programs to compute that function. We say that a team is successful if at least one member of the team learns the target function. The problem, given two teams with bounded number of mind changes whether, one team can provably learn more than the other team, was first proposed by Smith [C.H. Smith, The power of pluralism for automatic program synthesis, J. Assoc. Comput. Mach. 29 (1982) 1144–1165]. This problem has been open for the last twenty five years. This paper makes progress toward a complete solution of this problem. In the case of error-free learning, this paper closes the gap between the lower and the upper bounds. Finally, in the case of EX learning our result shows that there is no team with a⩾0 mind changes whose learning power is exactly equal to a single learner with bounded b (≠a) number of mind changes. In the case of Popperian learning (PEX) we have a positive answer.