Trees and learning

摘要

We characterize FIN-, EX- and BC-learning, as well as the corresponding notions of team learning, in terms of isolated branches on effectively given sequences of trees. The more restrictive models of FIN-learning and strong-monotonic BC-learning are characterized in terms of isolated branches on a single tree. Furthermore, we discuss learning with additional information where the learner receives an index for a strongly recursive tree such that the function to be learned is isolated on this tree. We show that EX-learning with this type of additional information is strictly more powerful than EX-learning.