PAC learning, VC dimension, and the arithmetic hierarchy.

We compute that the index set of PAC-learnable concept classes is m-complete $${\Sigma^{0}_{3}}$$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable $${\Pi^{0}_{1}}$$ classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability is equivalent to finite VC dimension. [ABSTRACT FROM AUTHOR]