Abstract:
For a Turing degree $\mathbf x$ a computable algebraic structure $\mathcal A$ is relatively $\mathbf x$-computable categorical if there is an $\mathbf x$-computable family of existential formulas defining the automorphism orbits of tuples from $\mathcal A$. We will study the collection of Turing degrees $\mathbf x$ for which a particular computable structure is relatively $\mathbf x$-computable categorical. This consideration also will give a series of unexpected results in the classical recursion theory context.
