Computability

Invited Speakers

• Ekaterina Fokina, Vienna University of Technology.
  Classification problem for effective structures

In this talk we will review several approaches to study the complexity of classifying effective structures up to isomorphism or another equivalence relation. Calculating the complexity of the set E(K) of pairs of indices corresponding to equivalent computable structures from a fixed class K is one of the approaches. One can use 1-dimensional or 2-dimensional versions of m-reducibility to establish the complexity of such index sets. According to this approach, a class is nicely classifiable if the set E(K) has hyperarithmetical complexity (provided the class K itself is hyperarithmetical). Another approach is to classify structures on-the-fly. We call a class classifiable in this sense if we can uniquely (up to a fixed equivalence relation) identify each structure from the class after observing a finite piece of the structure.

• Lucca San Mauro, Sapienza University of Rome
  Classifying equivalence relations on the natural numbers

This is joint work with Uri Andrews.

The study of the complexity of equivalence relations has been a major thread of research in diverse areas of logic. A reduction of an equivalence relation E on a domain X to an equivalence relation F on a domain Y is a function f : X → Y which induces an injection on the quotient sets,  X/E → Y/F . In the literature, there are two main definitions for this reducibility:

1. In descriptive set theory, Borel reducibility is defined by assuming that X and Y are Polish spaces and f is Borel.
2. In computability theory, computable reducibility is defined by assuming that X and Y coincide with the set of natural numbers and f is computable. 

Despite the clear analogy between the two notions, for a long time the study of Borel and computable reducibility were conducted independently. Yet, a theory of computable reductions which blends ideas from both computability theory and descriptive set theory is rapidly emerging. In this talk, we will discuss differences and similarities between the Borel and the computable settings as we provide computable, or computably enumerable, analogs of fundamental concepts from the Borel theory (such as dichotomy results, orbit equivalence relations, and the Friedman-Stanley jump).