Using the perceptron algorithm to find consistent hypotheses

The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.