Classifying Structures by Learning

The notion of classification formalises the idea of resemblance between mathematical objects. To classify a class of structures means to identify its members up to an equivalence relation, usually using some knowledge about structural, algebraic or algorithmic properties of the considered objects. In computable structure theory, there are several well-established approaches to classify classes of structures. In the project we suggest a new direction meant to classify infinite structures on-the-fly, i.e., while seeing only finite pieces of objects under consideration. Suppose, we have a finite or infinite collection of infinite mathematical objects. Suppose furthermore, we receive information about one of these objects step by step. At each step we get a new finite piece of knowledge about the structure. The goal is to say which of the objects we are receiving after making only after finitely many steps , i.e., without waiting to see each and every bit of the structure. We classify, or learn, the class, if after finitely many steps we correctly identify the observed structure. This task is not trivial even in the case when we only have two structures in the class: there are 2-element classes that are not learnable and there are 2-element classes that are learnable. To formalise the framework and to solve the arising questions, we combine the notions, approaches and methods from computable structure theory and algorithmic learning theory. Depending on how we set various parameters, such as the source of information, convergence behaviour, underlying equivalence relation, etc. we get different notions of classification, or learning. The main goal of the project is to characterise these notions of classification on-the-fly depending on the chosen parameters. We also want to find natural examples of classes of structures learnable and not learnable in a chosen sense. We want to separate the notions by finding classes learnable according to one framework but not according to another. Furthermore, we want to understand how much computational power we need to classify different classes according to our notions.