Proceedings of the Annual Meeting of the Cognitive Science Society

The functions of finite support have played a ubiquitous role in the study of inductive inference since its inception. In addition to providing a clear and simple example of a leamable class, the functions of finite support are employed in many proofs that distinguish various types and features of learning. Recent results show that this ostensibly simple class requires as much space to leam as any other learnable set and, furthermore, is as intrinsically difficult as any other learnable set. This makes the functions of finite support a candidate for being a canonical learning problem. We argue for this point in the paper and discuss the ramifications.