# Can there exist a natural' finitely generated group with an undecidable word problem?

There are naturally occurring groups that have undecidable algorithmic problems. For instance, $F_2\times F_2$ has undecidable generalized word problem (membership problem for subgroups) and there is a semidirect product $\Bbb Z^4\rtimes F_4$ with undecidable conjugacy problem. But to the best of my knowledge every finitely generated group with an undecidable word problem is directly constructed from a Turing machine variant or a non-recursive, recursively enumerable set.

Can there exist a naturally occurring finitely generated group with an undecidable word problem?

Of course this problem is not well-defined because natural' is not well defined in this setting. It should somehow mean things built up from well studied classes of groups (hyperbolic groups, polycyclic groups, solvable groups, linear groups) via natural operations, e.g., extensions, amalgamations, maybe direct limit (I am not sure I like allowing this last option since some strange groups are direct limits of hyperbolic groups).

-

If you take a subgroup $H$ of $F_2\times F_2$ with undecidable membership problem and take the HNN extension of $F_2\times F_2$ where the stable letter commutes with $H$, you get a (finitely presented) group with undecidable word problem. I do not know how natural it is since $H$ encodes a Turing machine. The only known "natural" example of universal algebras with undecidable word problem are free modular lattices (Freese, 1980).
It is a Thompson group $V$ plus several functions that simulate standard recursive procedures (add 1, composition, etc.). Then words correspond to recursive functions. You can look at the paper or at the more recent Birget, Jean-Camille Circuits, the groups of Richard Thompson, and coNP-completeness. Internat. J. Algebra Comput. 16 (2006), no. 1, 35–90. – Mark Sapir Nov 18 '11 at 4:02