Categoricity spectra for rigid structures (Q5963198)

Let \(\mathbf d\) be a Turing degree. We say that a computable structure is \(\mathbf d\)-categorical if each its computable isomorphic copy is isomorphic to it via a \(\mathbf d\)-computable isomorphism. The least such degree, if existing, is called the degree of categoricity of this structure. The authors prove that there exists a computable rigid structure with no degree of categoricity and that for every c.e. nonzero degree \(\mathbf x\), there exists an \(\mathbf x\)-computably categorical structure with no degree of categoricity.