We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
A Turing degree d is the degree of categoricity of a computable structure 
${\cal S}$ if d is the least degree capable of computing isomorphisms among arbitrary computable copies of 
${\cal S}$. A degree d is the strong degree of categoricity of 
${\cal S}$ if d is the degree of categoricity of 
${\cal S}$, and there are computable copies 
${\cal A}$ and 
${\cal B}$ of 
${\cal S}$ such that every isomorphism from 
${\cal A}$ onto 
${\cal B}$ computes d. In this paper, we build a c.e. degree d and a computable rigid structure 
${\cal M}$ such that d is the degree of categoricity of 
${\cal M}$, but d is not the strong degree of categoricity of 
${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].
For a computable structure 
${\cal S}$, we introduce the notion of the spectral dimension of 
${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of 
${\cal S}$. We prove that for a nonzero natural number N, there is a computable rigid structure 
${\cal M}$ such that 
$0\prime$ is the degree of categoricity of 
${\cal M}$, and the spectral dimension of 
${\cal M}$ is equal to N.
We study the computable structure theory of linear orders of size 
$\aleph _1 $ within the framework of admissible computability theory. In particular, we characterize which of these linear orders are computably categorical.
We study the computable structure theory of linear orders of size 
$\aleph _1 $ within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.
