Abstract:
A learner is a function $M$ which, given a finite amount of data about a countable algebraic structure $S$, outputs a conjecture about the isomorphism type of the input structure. A family of structures $K$ is learnable if there exists a learner which for any $S$ from $K$, given larger and larger amounts of $S$-data, eventually correctly identifies the isomorphism type of $S$. In the talk, we discuss two characterizations of learnability: the first one uses the syntax of infinitary logic $L_{\omega_1, \omega}$, and the second one connects learnability with the benchmark combinatorial Borel equivalence relations.