  Machine learning researchers and practitioners steadily enlarge the multitude
of successful learning models. They achieve this through in-depth theoretical
analyses and experiential heuristics. However, there is no known
general-purpose procedure for rigorously evaluating whether newly proposed
models indeed successfully learn from data. We show that such a procedure
cannot exist. For PAC binary classification, uniform and universal online
learning, and exact learning through teacher-learner interactions, learnability
is in general undecidable, both in the sense of independence of the axioms in a
formal system and in the sense of uncomputability. Our proofs proceed via
computable constructions that encode the consistency problem for formal systems
and the halting problem for Turing machines into whether certain function
classes are trivial/finite or highly complex, which we then relate to whether
these classes are learnable via established characterizations of learnability
through complexity measures. Our work shows that undecidability appears in the
theoretical foundations of artificial intelligence: There is no
one-size-fits-all algorithm for deciding whether a machine learning model can
be successful. We cannot in general automatize the process of assessing new
learning models.
