Learning Branches and Learning to Win Closed Games

Abstract

We introduce two new notions of inductive inference: learning infinite recursive branches of recursive trees and learning winning strategies for closed recursive games. Branch learning can be seen as a natural generalization of learning functions, and learning winning strategies is a new approach to constructively find winning strategies for a special kind of Gale-Stewart games. These two independently motivated concepts turn out to be equivalent. In branch learning there appear new phenomena compared to function learning: e.g. we can show that learning and uniform computation are incomparable. In the setting of learning functions uniform computation is trivial. Another example is that there are two distinct natural definitions for BC-style branch learning which yield different classes. By studying different learning criteria, enumeration and computation of branches, and the effect of using an oracle for the halting problem we get a hierarchy built by the corresponding classes. All presented results also hold for winning strategy learning by the equivalence mentioned above. Additionally, we investigate the notion of counter strategy learning for closed recursive games.