Remarks and problems about algorithmic descriptions of groups
arXiv:2111.01190 · doi:10.1142/S0218196725500328
Abstract
Motivated by a theorem of Groves and Wilton, we propose the study of the lattice of numberings of isomorphism classes of marked groups as a rigorous and comprehensive framework to study global decision problems for finitely generated groups. We establish the Rice and Rice-Shapiro Theorems for recursive presentations, and establish similar results for co-recursive presentations. We give an algorithmic characterization of finitely presentable groups in terms of semi-decidability of two decision problems: the word problem and the marked quotient problem, which we introduce. We explain how this result can be used to define algorithmic generalizations of finite presentations. Finally, we discuss how the Adian-Rabin Theorem provides incomplete answers in several respects.
arXiv comment19 pages
References in corpus (9)
- On the isolated points in the space of groups
- The Isomorphism Problem for Toral Relatively Hyperbolic Groups
- Noncommutative real algebraic geometry of Kazhdan's property (T)
- The triviality problem for profinite completions
- A nilpotent quotient algorithm for L-presented groups
- Group Embeddings with Algorithmic Properties
- Linear groups and computation
- Computability of finite quotients of finitely generated groups
- Some results related to the continuity problem