More Like this

1. Generically computable linear orderings

   https://doi.org/10.1016/j.apal.2025.103612  

   Calvert, Wesley; Cenzer, Douglas; Gonzalez, David; Harizanov, Valentina (May 2025, Annals of Pure and Applied Logic)

   We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the Σβ hierarchy. We focus on linear orderings. We show that at the Σ1 level, all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the Σα+2 level for any α ∈ ωCK 1 the set of linear orderings with generically or coarsely computable copies is Σ1 1-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results, we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy. 

   more » « less
2. Densely computable structures

   https://doi.org/10.1093/logcom/exab057  

   Calvert, Wesley; Cenzer, Douglas; Harizanov, Valentina (September 2021, Journal of Logic and Computation)

   Abstract In recent years, computability theorists have extensively studied generically and coarsely computable sets. This study of approximate computability was originally motivated by asymptotic density problems in combinatorial group theory. We generalize the notions of generic and coarse computability of sets, introduced by Jockusch and Schupp, to arbitrary structures by defining generically and coarsely computable and computably enumerable structures. There are two directions in which these notions could potentially trivialize: either all structures could have a densely computable copy or only those having a computable (or computably enumerable) copy. We show that some particular classes of structures realize each of these extremal conditions, while other classes realize neither of them. To further explore these concepts, we introduce a graded family of elementarity conditions for substructures, in which we require that the dense sets under consideration be ‘strong’ substructures of the original structure. Here, again, for a given class, the notion could trivialize in the same two directions and we show that both are possible. For each class that we investigate, there is some natural number $$n$$ such that requiring $$\varSigma _{n}$$ elementarity of substructures is enough to trivialize the class of generically or densely computable structures, witnessing the essentially structural character of these notions. 

   more » « less
3. Generically computable Abelian groups

   https://doi.org/10.1007/978-3-031-34034-5_3  

   Calvert, W.; Cenzer, D.; Harizanov, V. (June 2023, Unconventional Computation and Natural Computation)

   Genova, D.; Kari, J. (Ed.)

   Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate computability was motivated by asymptotic density problems studied by Gromov in combinatorial group theory. More recently, we have defined notions of generically computable structures, and studied in particular equivalence structures and injection structures. A structure is said to be generically computable if there is a c.e. substructure defined on an asymptotically dense set, where the functions are computable and the relations are computably enumerable. It turned out that every equivalence structure has a generically computable copy, whereas there is a non-trivial characterization of the injection structures with generically computable copies. In this paper, we return to group theory, as we explore the generic computability of Abelian groups. We show that any Abelian p-group has a generically computable copy and that such a group has a Σ2-generically computably enumerable copy if and only it has a computable copy. We also give a partial characterization of the Σ1-generically computably enumerable Abelian p-groups. We also give a non-trivial characterization of the generically computable Abelian groups that are not p-groups. 

   more » « less
4. Computability of topological pressure on compact shift spaces beyond finite type*

   https://doi.org/10.1088/1361-6544/ac7702  

   Burr, Michael; Das, Suddhasattwa; Wolf, Christian; Yang, Yun (June 2022, Nonlinearity)

   We investigate the computability (in the sense of computable analysis) of the topological pressure P_top(ϕ) on compact shift spaces X for continuous potentials ϕ:X→R. This question has recently been studied for subshifts of finite type (SFTs) and their factors (sofic shifts). We develop a framework to address the computability of the topological pressure on general shift spaces and apply this framework to coded shifts. In particular, we prove the computability of the topological pressure for all continuous potentials on S-gap shifts, generalised gap shifts, and particular beta-shifts. We also construct shift spaces which, depending on the potential, exhibit computability and non-computability of the topological pressure. We further prove that the generalised pressure function (X,ϕ) ↦P_top(X,ϕ|_X) is not computable for a large set of shift spaces X and potentials ϕ . In particular, the entropy map X↦h_top(X) is computable at a shift spaceXif and only if X has zero topological entropy. Along the way of developing these computability results, we derive several ergodic-theoretical properties of coded shifts which are of independent interest beyond the realm of computability. 

   more » « less
5. Computability in infinite Galois theory and algorithmically random algebraic fields

   https://doi.org/10.1112/jlms.70017  

   Calvert, Wesley; Harizanov, Valentina; Shlapentokh, Alexandra (November 2024, Journal of the London Mathematical Society)

   Abstract We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of that are random according to our definition. We show that there are noncomputable algebraic fields which are not random. We also partially characterize the index set, relative to an oracle, of the set of random algebraic fields computable relative to that oracle. In order to carry out this investigation of randomness for fields, we develop computability in the context of the infinite Galois theory (where the relevant Galois groups are uncountable), including definitions of computable and computably enumerable Galois groups and computability of Haar measure on the Galois groups. 

   more » « less