  This paper is about the surprising interaction of a foundational result from
model theory about stability of theories, which seems to be inherently about
the infinite, with algorithmic stability in learning. Specifically, we develop
a complete algorithmic analogue of Shelah's celebrated Unstable Formula
Theorem, with algorithmic properties taking the place of the infinite. This
draws on several new theorems as well as much recent work. In particular we
introduce a new ``Probably Eventually Correct'' learning model, of independent
interest, and characterize Littlestone (stable) classes in terms of this model;
and we describe Littlestone classes via approximations, by analogy to
definability of types in model theory.

Logic;Discrete Mathematics;Machine Learning;Logic in Computer Science;Combinatorics