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
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,
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
not relatively Δ0α-categorical.