## Abstract

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} 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, σ_{1} can be learned adversarially, but 0 1 not); (iii) some languages in σ_{1} cannot be approximated by any language in σ_{1}. 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.

Original language | English |
---|---|

Pages (from-to) | 2171-2192 |

Number of pages | 22 |

Journal | Journal of Logic and Computation |

Volume | 27 |

Issue number | 7 |

DOIs | |

Publication status | Published - 1 Oct 2017 |

## Keywords

- adversarial learning
- approximability
- approximation
- decidable
- elusive model paradox
- halting
- halting problem
- learnability
- matching pennies
- Nash equilibrium
- recursively enumerable
- red herring sequence
- Turing machine