The IMP game: Learnability, approximability and adversarial learning beyond Σ₁

We introduce a problem set-up we call the Iterated Matching Pennies (IMP) game and show that it is a powerful framework for the study of three problems: adversarial learnability, conventional (i.e. non-adversarial) learnability and approximability. Using it, we are able to derive the following theorems. (i) It is possible to learn by example all of σ₁ 1 as well as some supersets; (ii) in adversarial learning (which we describe as a pursuit-evasion game), the pursuer has a winning strategy (in other words, σ₁ can be learned adversarially, but 0 1 not); (iii) some languages in σ₁ cannot be approximated by any language in σ₁. In particular, we show that some languages that are not computable are nevertheless learnable by example. We show corresponding results also for σ_i and 0 i for arbitrary i.