Andrew Lewis
(University of Leeds)
The Complexity of Computable Categoricity

I will report on recent work with Downey, Kach, Lempp, Montalban and Turetsky. A computable structure is computably categorical if there is a computable isomorphism from the structure to any computable copy. It has been a longstanding question to decide the complexity of the index set of computably categorical structures, i.e. to establish what oracle is required to decide which computable structures are computably categorical. We have shown that the index set is Π11-complete, demonstrating that computable categoricity has no simple syntactic characterization. As a consequence of our proof, we exhibit, for every computable ordinal α, a computable structure that is computably categorical but not relatively Δ0α-categorical.