Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...) }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel. (shrink)

For a computable structure $\mathcal {M}$, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of $\mathcal {M}$. If the spectrum has a least degree, this degree is called the degree of categoricity of $\mathcal {M}$. In this paper we investigate spectra of categoricity for computable rigid structures. In particular, we give examples of rigid structures without degrees of categoricity.

A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis 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}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis 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 numberN, 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 toN. (shrink)

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.

We study punctual categoricity on a cone and intrinsically punctual functions and obtain complete structural characterizations in terms of model-theoretic notions. As a corollary, we answer a question of Bazhenov, Downey, Kalimullin, and Melnikov by showing that relational structures are not punctually universal. We will also apply this characterisation to derive an algebraic characterisation of relatively punctually categorical mono-unary structures.

We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable.

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half a nontrivial relativized K-pair. This leads to a structural dichotomy in the enumeration degrees.

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump. We also show that this result does not hold for the limit ordinal. Moreover, we prove that there is no countable structure with the degree spectrum for.

We show that the Δ0 2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.

We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.

Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...) to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. (shrink)

We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.

We introduce a hierarchy of sets which can be derived from the integers using countable collections. Such families can be coded into countable algebraic structures preserving their algorithmic properties. We prove that for different finite levels of the hierarchy the corresponding algebraic structures have different classes of possible degree spectra.

Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$.