Submission date:

Abstract:

We make the case that the so called “global decision problems” should not be investigated solely for groups described by finite presentations. We propose to use descriptions that be algorithms that perform some given tasks, and that encode the considered groups. We motivate this by establishing undecidability results for groups described by recursive presentations, strong enough to prevent an interesting theory of decision problems based on generic recursive presentations to be developed. More importantly, we give an algorithmic characterization of finitely presented groups, in terms of existence of a “marked quotient algorithm” which recognizes the quotients of the considered group. This new point of view leads us to proposing several open questions and directions of research, and much of this paper consists in exposing problems that arise from our first results. Finally, note that we set our study in the category of marked groups, we explain why this is beneficial, and give open questions that arise from the study of decision problems for marked groups.

Mathematics Subject Classification: 20F10, 03D40, 20F05

Keywords and phrases:

Full text arXiv 2111.01190: pdf, ps.