Team Learning of Computable Languages

A team of learning machines is a multiset of learning machines. A team is said to success- fully learn a concept just in case each member of some nonempty subset, of predetermined size, of the team learns the concept. Team learning of languages may be viewed as a suit- able theoretical model for studying computational limits on the use of multiple heuristics in learning from examples. Team learning of recursively enumerable languages has been studied extensively. How- ever, it may be argued that from a practical point of view all languages of interest are computable. This paper gives theoretical results about team learnability of computable (recursive) languages. These results are mainly about two issues: redundancy and aggrega- tion. The issue of redundancy deals with the impact of increasing the size of a team and increasing the number of machines required to be successful. The issue of aggregation deals with conditions under which a team may be replaced by a single machine without any loss in learning ability. The learning scenarios considered are: (a) Identication in the limit of grammars for computable languages. (b) Identication in the limit of decision procedures for computable languages. (c) Identication in the limit of grammars for indexed families of computable languages. (d) Identication in the limit of grammars for indexed families with a recursively enumer- able class of grammars for the family as the hypothesis space. Scenarios that can be modeled by team learning are also presented.