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
This content will become publicly available on June 1, 2024
Generically computable Abelian groups
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
- Award ID(s):
- 2152095
- NSF-PAR ID:
- 10427607
- Editor(s):
- Genova, D.; Kari, J.
- Date Published:
- Journal Name:
- Unconventional Computation and Natural Computation
- Volume:
- LNCS 14003
- ISSN:
- 03029743
- Page Range / eLocation ID:
- 32–45
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
(3+1)D topological phases of matter can host a broad class of non-trivial topological defects of codimension-1, 2, and 3, of which the well-known point charges and flux loops are special cases. The complete algebraic structure of these defects defines a higher category, and can be viewed as an emergent higher symmetry. This plays a crucial role both in the classification of phases of matter and the possible fault-tolerant logical operations in topological quantum error-correcting codes. In this paper, we study several examples of such higher codimension defects from distinct perspectives. We mainly study a class of invertible codimension-2 topological defects, which we refer to as twist strings. We provide a number of general constructions for twist strings, in terms of gauging lower dimensional invertible phases, layer constructions, and condensation defects. We study some special examples in the context of \mathbb{Z}_2 ℤ 2 gauge theory with fermionic charges, in \mathbb{Z}_2 \times \mathbb{Z}_2 ℤ 2 × ℤ 2 gauge theory with bosonic charges, and also in non-Abelian discrete gauge theories based on dihedral ( D_n D n ) and alternating ( A_6 A 6 ) groups. The intersection between twist strings and Abelian flux loops sources Abelian point charges, which defines an H^4 H 4 cohomology class that characterizes part of an underlying 3-group symmetry of the topological order. The equations involving background gauge fields for the 3-group symmetry have been explicitly written down for various cases. We also study examples of twist strings interacting with non-Abelian flux loops (defining part of a non-invertible higher symmetry), examples of non-invertible codimension-2 defects, and examples of the interplay of codimension-2 defects with codimension-1 defects. We also find an example of geometric, not fully topological, twist strings in (3+1)D A_6 A 6 gauge theory.more » « less
-
We prove a number of results to the effect that generic quantum graphs (defined via operator systems as in the work of Duan-Severini-Winter / Weaver) have few symmetries: for a Zariski-dense open set of tuples ( X 1 , ⋯ , X d ) (X_1,\cdots ,X_d) of traceless self-adjoint operators in the n × n n\times n matrix algebra the corresponding operator system has trivial automorphism group, in the largest possible range for the parameters: 2 ≤ d ≤ n 2 − 3 2\le d\le n^2-3 . Moreover, the automorphism group is generically abelian in the larger parameter range 1 ≤ d ≤ n 2 − 2 1\le d\le n^2-2 . This then implies that for those respective parameters the corresponding random-quantum-graph model built on the GUE ensembles of X i X_i ’s (mimicking the Erdős-Rényi G ( n , p ) G(n,p) model) has trivial/abelian automorphism group almost surely.more » « less
-
more » « less
Many problems in programming language theory and formal methods are undecidable, so they cannot be solved precisely. Practical techniques for dealing with undecidable problems are often based on decidable approximations. Undecidability implies that those approximations are always imprecise. Typically, practitioners use heuristics and
ad hoc reasoning to identify imprecision issues and improve approximations, but there is a lack of computability-theoretic foundations about whether those efforts can succeed.This paper shows a surprising interplay between undecidability and decidable approximations: there exists a class of undecidable problems, such that it is computable to transform any decidable approximation to a witness input demonstrating its imprecision. We call those undecidable problems
witnessable problems . For example, if a program propertyP is witnessable, then there exists a computable functionf P , such thatf P takes as input the code of any program analyzer targetingP and produces an input programw on which the program analyzer is imprecise. An even more surprising fact is that the class of witnessable problems includes almost all undecidable problems in programming language theory and formal methods. Specifically, we prove the diagonal halting problemK is witnessable, and the class of witnessable problems is closed under complements and many-one reductions. In particular, all “non-trivial semantic properties of programs” mentioned in Rice’s theorem are witnessable. We also explicitly construct a problem in the non-witnessable (and undecidable) class and show that both classes have cardinality 2ℵ0.Our results offer a new perspective on the understanding of undecidability: for witnessable problems, although it is impossible to solve them precisely, it is always possible to improve any decidable approximation to make it closer to the precise solution. This fact formally demonstrates that research efforts on such approximations are promising and shows there exist universal ways to identify precision issues of program analyzers, program verifiers, SMT solvers, etc., because their essences are decidable approximations of witnessable problems.
