A novel degree class arising from computable structures

When two objects look different but are really the same, how can a computer tell? Consider the task of drawing a map of the Austrian railway network. Person A sketches the network starting in the west and finishing in the east, while Person B, living in the eastern part of Austria, might begin in the east and finish in the west. Both drawings show the same information but present it differently; if we were to flip Bs map, we would obtain As. A mathematician would say that the two maps are isomorphic. For finite structures, such as our maps, one can design algorithms that tell whether two structures are isomorphic. There are only finitely many isomorphisms, i.e., maps that witness that the structures are isomorphic, and thus a simple guess-and-check algorithm would find the isomorphism eventually or run through all guesses without success. However, for infinite objects, as usually encountered in mathematics, algorithms that compute isomorphisms generally do not exist. Given two isomorphic structures, how complicated are the isomorphisms between them? Roughly speaking, the simpler the isomorphisms, the more alike the structures look from the point of view of a computer. The computational complexity of isomorphisms is measured using Turing degrees, and one of the central notions in computable structure theory is the degree of categoricity of a computable structure A. It is the least Turing degree that can compute isomorphisms between any two computable structures that are isomorphic to A. A major open problem is to understand exactly which Turing degrees can occur. Can we classify them in terms of other, better-understood degree classes? Recently, we showed that a large class of degrees of categoricity have the same Turing degree as treeable functionsso-called treeable degrees. This provides a new and surprisingly simple partial combinatorial characterization. A treeable function arises as an infinite path through a computable tree so that every other path computes it. Even though there is no single algorithm producing the function, there are still algorithms that represent it indirectly through the tree. While this result gives us hope to find a nice characterization of the degrees of categoricity, it is at this time not very useful as treeable degrees themselves are poorly understood. The aim of this project is to obtain a better understanding of treeable degrees by uncovering their relationships with other degree classes, and through this allow us to verify whether they provide a complete characterization of the degrees of categoricity. In doing so, we shed light on the algorithmic content of the isomorphism relationone of mathematics most central equivalence relations.