The recognition problem for the set of perfect squares

Abstract

Lower bounds on the capacity and on the product of capacity and computation time are obtained for machines which recognize the set of squares. The bound on capacity is approached to within a factor of four by a specific machine which carries out a test based on the fact that every non-square is a quadratic non-residue of some rational prime. A machine which carries out a test based on the standard root-extraction algorithm is substantially less efficient in this respect. For neither machine is the bound on the capacity-time product closely approached.