Upcoming Events

Logic Colloquium

October 07, 2022, 4:10 PM

60 Evans Hall

Dino Rossegger
UC Berkeley and TU Wien

The degrees of categoricity above 0″

The degree of categoricity of a computable structure is the least Turing degree that computes an isomorphism between any two computable isomorphic copies of the structure. It provides a robust measure of complexity for computable structures – if A has degree of categoricity d, then modulo d all its isomorphic copies have the same computational properties. Two of the main goals in this area are to obtain a characterization of the Turing degrees that are degrees of categoricity of computable structure and to see whether all degrees of categoricity are strong, i.e., arise from the isomorphisms between two copies of a structure.

In this talk I will introduce the methods and main results in the area and discuss a recent result of Csima and I that presents a breakthrough in our understanding of degrees of categoricity. We obtained a characterization of the degrees of categoricity above 0″ as what we call the treeable degrees above 0″ and showed that every degree of categoricity above 0″ is strong.