Finitely presentable subgroups and algorithms
Maurice Chiodo · arXiv (Cornell University) · 2011
We show that there is a finitely presented group G for which there is no algorithm that takes a finitely presentable subgroup H of G, an abstract finite presentation Q for H, and constructs an isomorphism between Q and H. To do this, we show that there is a finitely presented group with solvable word problem (namely, the Baumslag-Solitar group BS(2,3)) for which there is no algorithm that takes a recursive presentation of that same group, and solves the word problem in the recursive presentation. Our main result suggests, but does not prove, that there is a genuine difference between strong effective coherence and weak effective coherence.