Remarks and problems about algorithmic descriptions of groups (Q6923217)

The paper is motivated by a theorem by \textit{D.~Groves} and \textit{H.~Wilton} [Groups Geom. Dyn. 3, No. 3, 389--399 (2009; Zbl 1216.20029)], which states that there exists an algorithm that, given as input a presentation for a group \(G\) and a solution to the word problem in \(G\), determines whether or not \(G\) is free. The author develops a systematic framework for studying global decision problems for finitely generated groups beyond the classical setting of finite presentations and proposes to study the lattice of numberings of isomorphism classes of marked groups as the natural environment for these questions. A marked group is a finitely generated group together with an ordered \(k\)-tuple of generators, considered up to marked isomorphism.\N\NThe work proves analogues of the classical Rice and Rice-Shapiro theorems in the setting of groups described by recursive and co-recursive presentations. These results show that semi-decidable properties of such groups correspond to Scott-open subsets of the lattice of marked groups and imply strong undecidability statements for global decision problems. The paper introduces the marked quotient problem and gives an algorithmic characterization of finitely presented groups as those with semi-decidable word problem and marked quotient problem (Theorem~G). It further develops the associated lattice-theoretic and topological structures and connects these with undecidability theorems.