PAC-learning is Undecidable
  The problem of attempting to learn the mapping between data and labels is the
crux of any machine learning task. It is, therefore, of interest to the machine
learning community on practical as well as theoretical counts to consider the
existence of a test or criterion for deciding the feasibility of attempting to
learn. We investigate the existence of such a criterion in the setting of
PAC-learning, basing the feasibility solely on whether the mapping to be learnt
lends itself to approximation by a given class of hypothesis functions. We show
that no such criterion exists, exposing a fundamental limitation in the
decidability of learning. In other words, we prove that testing for
PAC-learnability is undecidable in the Turing sense. We also briefly discuss
some of the probable implications of this result to the current practice of
machine learning.
