Finding non-trivial elements and splittings in groups. (Q716463): Difference between revisions

The article deals with the recursive (un)solvability of various problems for finitely presented groups, that is the (non-)existence of algorithms performing specific constructions. The motivating question is that of the existence of a partial algorithm which, on input of a finite presentation of a non-trivial group \(G\), outputs a word in the generators non-trivial in \(G\). A weak form of the motivating question is negatively answered in Theorem 4.2: \(k>0\) being fixed, there is no such algorithm yielding a word of length \(\leq k\). Similarly, it is proved in Theorem 5.5 that there is no algorithm which, on input of a finite presentation of a group which is the free product of two non-trivial finitely presentable subgroups, outputs finite presentations for the factors; and in Theorem 6.6 that there is no algorithm which, on input of finite presentations of two non-trivial groups \(G\) and \(H\), outputs a partial map from the generators of \(G\) to \(H\) which extends to a group embedding. The key step to all results is a recursion-theoretic elaboration on a construction for the Adian-Rabin Theorem by \textit{C. McA. Gordon}, [Lond. Math. Soc. Lect. Note Ser. 204, 105-110 (1995; Zbl 0843.20027)].