The IMP game: Learnability, approximability and adversarial learning beyond $\Sigma^0_1$
Michael Brand, David L. Dowe · Journal of Logic and Computation · 2016
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 |$\Sigma^0_1 \cup \Pi^0_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, |$\Sigma^0_1$| can be learned adversarially, but |$\Pi^0_1$| not); (iii) some languages in |$\Pi^0_1$| cannot be approximated by any language in |$\Sigma^0_1$|. In particular, we show that some languages that are not computable are nevertheless learnable by example. We show corresponding results also for |$\Sigma^0_i$| and |$\Pi^0_i$| for arbitrary |$i$|.