Computability-theoretic investigation of algorithmic complexity of isomorphisms between countable structures is a key topic in computable structure theory since Fröhlich and Shepherdson, Mal'cev, and Metakides and Nerode. A computable structure is called computably categorical if for every computable isomorphic , there is a computable isomorphism from onto . By relativizing the notion of computable categoricity to a Turing degree d, we obtain the notion of d-computable categoricity. For the case when d is , we also speak about -categoricity, for . More generally, is relatively -categorical if for every isomorphic , there is an isomorphism that is relative to the atomic diagram of . Equivalently, is relatively -categorical if and only if has a computably enumerable Scott family of computable (infinitary) formulas. Relative -categoricity implies -categoricity, but not vice versa.
In this paper, we present an example of a computable Fraïssé limit that is computably categorical (that is, -categorical) but not relatively computably categorical. We also present examples of -categorical but not relatively -cate- gorical structures in natural classes such as trees of finite and infinite heights, and homogeneous, completely decomposable, abelian groups. It is known that for structures from these classes computable categoricity and relative computable categoricity coincide.
The categoricity spectrum of a computable structure is the set of all Turing degrees d such that is d-computably categorical. The degree of categoricity of is the least degree in the categoricity spectrum of , if such a degree exists. It provides the exact level of categoricity of the structure. In this paper, we compute degrees of categoricity for relatively -categorical abelian p-groups and for relatively -categorical Boolean algebras.