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 Π^{1}_{1}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.
