More Like this

1. Generically and coarsely computable isomorphisms

   https://doi.org/10.3233/COM-210382  

   Calvert, Wesley; Cenzer, Douglas; Harizanov, Valentina (December 2022, Computability)

   Brattka, Vasco; Greenberg, Noam; Kalimullin, Iskander; Soskova, Mariya (Ed.)

   Inspired by the study of generic and coarse computability in computability theory, we extend such investigation to the context of computable model theory. In this paper, we continue our study initiated in the previous paper (Journal of Logic and Computation 32 (2022) 581–607) , where we introduced and studied the notions of generically and coarsely computable structures and their generalizations. In this paper, we introduce the notions of generically and coarsely computable isomorphisms, and their weaker variants. We sometimes also require that the isomorphisms preserve the density structure. For example, for any coarsely computable structure A, there is a density preserving coarsely computable isomorphism from A to a computable structure. We demonstrate that each notion of generically and coarsely computable isomorphisms, density preserving or not, gives interesting insights into the structures we consider, focusing on various equivalence structures and injection structures. 

   more » « less
2. 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
3. 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
4. On computable aspects of algebraic and definable closure

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

   Ackerman, Nathanael; Freer, Cameron; Patel, Rehana (December 2020, Journal of Logic and Computation)

   null (Ed.)

   Abstract We investigate the computability of algebraic closure and definable closure with respect to a collection of formulas. We show that for a computable collection of formulas of quantifier rank at most $$n$$, in any given computable structure, both algebraic and definable closure with respect to that collection are $$\varSigma ^0_{n+2}$$ sets. We further show that these bounds are tight. 

   more » « less
5. 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