We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures.

Abstract We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$ . As a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $ , then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$ , $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $ . We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings.

Abstract We prove that there exists a $\varSigma ^{0}_{1}$ closed subset of $[0,1]$ which is not homeomorphic to any computably compact space. We show that the index set of c.e. subspaces of $[0,1]$ that admit a computably compact presentation is not arithmetical, as witnessed by subsets of $[0,1]$. The index set result is new for computable Polish spaces in general, not only for those realised as c.e. closed subsets of $[0,1]$.

Abstract The complexity classification of computably enumerable equivalence relations (or ceers, for short) has received much attention in the recent literature. A measure of complexity is typically provided by an appropriate notion of a reduction. Given binary relations $R$ and $S$ on natural numbers, a total function $f$ is a reduction from $R$ to $S$ if for arbitrary $x$ and $y$, the conditions $x~R~y$ and $f(x)~S~f(y)$ are always equivalent. If the function $f$ can be chosen primitive recursive, then we say that $R$ is primitively recursively reducible to $S$, denoted by $R \leq _{pr} S$. We investigate the degree structure $(\textbf {Ceers},\leq _{pr})$ of $\leq _{pr}$-degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that $(\textbf {Ceers},\leq _{pr})$ is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of $(\textbf {Ceers},\leq _{pr})$. In particular, we prove that the set of equivalences that have only finitely many classes is definable in $(\textbf {Ceers},\leq _{pr})$. Finally, we show that the structure of $\leq _{pr}$-degrees of computably enumerable preorders has a hereditarily undecidable theory.

Abstract Let $\mathbf{C}^{pr}_{m}$ be the upper semilattice of degrees of computable sets with respect to primitive recursive $m$-reducibility. We prove that the first-order theory of $\mathbf{C}^{pr}_{m}$ is hereditarily undecidable.

Shapiro's notations for natural numbers, and the associated desideratum of acceptability - the property of a notation that all recursive functions are computable in it - is well-known in philosophy of computing. Computable structure theory, however, although capable of fully reconstructing Shapiro's approach, seems to be off philosophers' radar. Based on the case study of natural numbers with standard order, we make initial steps to reconcile these two perspectives. First, we lay the elementary conceptual groundwork for the reconstruction of Shapiro's approach in terms of computable structures and show, on a few examples, how results pertinent to the former can inform our understanding of the latter. Secondly, we prove a new result, inspired by Shapiro's notion of acceptability, but also relevant for computable structure theory. The result explores the relationship between the classical notion of degree spectrum of a computable function on the structure in question - specifically, having all c.e. degrees as a spectrum - and our ability to compute the (image of the) successor from the (image of the) function in any computable copy of the structure. The latter property may be otherwise seen as relativized acceptability of every notation for the structure.

We study algorithmic learning of algebraic structures. In our framework, a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. We prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation E0 of eventual agreement on reals. This motivates a novel research program, that is, using descriptive set theoretic tools to calibrate the (learning) complexity of nonlearnable families. Here, we focus on the learning power of well-known benchmark Borel equivalence relations (i.e., E1, E2, E3, Z0, and Eset).

Intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all $Δ_2$ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright and Harrison-Trainor by showing that the division between computable, c.e. and $Δ_2$ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the $Δ_2$ degrees.

In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if L is a computable linear order of Hausdorff rank n, then for every bi-embeddable copy of it there is an embedding computable in 2n−1 jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let L be a computable linear order of Hausdorff rank n≥1, then 0(2n−2) does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal α such that 0(α) computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knight's pairs of structures theorem.

Abstract The paper works within the framework of punctual computability, which is focused on eliminating unbounded search from constructions in algebra and infinite combinatorics. We study punctual numberings, that is, uniform computations for families S of primitive recursive functions. The punctual reducibility between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We show that any infinite, uniformly primitive recursive family S induces an infinite Rogers pr-semilattice R. We prove that the semilattice R does not have minimal elements, and every nontrivial interval inside R contains an infinite antichain. In addition, every non-greatest element from R is a part of an infinite antichain. We show that the $\Sigma_1$ -fragment of the theory Th(R) is decidable.

Abstract In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.

We investigate computability-theoretic properties of contact algebras. These structures were introduced by Dimov and Vakarelov in [Fundam. Inform. 74 (2006), 209–249] as an axiomatization for the region-based theory of space. We prove that the class of countable contact algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. This means that the class of contact algebras is very rich from the computability-theoretic point of view. As an application of our result, we show that the ∏ 3 -theory of contact algebras is hereditarily undecidable. This is a refinement of the result of Koppelberg, Düntsch, and Winter [Algebra Univers., 68 (2012), 353–366].

Abstract 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.

Abstract 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.

We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure $\mathcal{S}$ , the SC-autostability spectrum of $\mathcal{S}$ is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of $\mathcal{S}$ . The degree of SC-autostability for $\mathcal{S}$ is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above0(α)is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above0(2β+1)is the degree of SC-autostability for some discrete linear order. We prove that the set of all PA-degrees is an SC-autostability spectrum. We also obtain similar results for autostability spectra relative ton-constructivizations.