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).


1 Answer 1


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).

As a more natural examples you can take McKenzie-Thompson group that simulates all recursive functions or Valiev's (Boone-Collins) universal group that simulates all Turing machines, see comments below.

  • $\begingroup$ The free modular lattice is more like what I had in mind. I probably should have explicitly disallowed amalgamation and HNN extensions over subgroups with undecidable membership problem. $\endgroup$ Nov 18, 2011 at 0:11
  • 1
    $\begingroup$ In some sense one can view the construction of McKenzie and Thompson as "natural" because they essentially find groups with unsolvable word problem inside some "natural" group, so the "natural" group has undecidable word problem also. Also one can view the universal example of Valiev or Boone-Collins (with a few defining relations) as "natural". Their definitions do not involve any Turing machines or recursive functions. $\endgroup$
    – user6976
    Nov 18, 2011 at 1:18
  • $\begingroup$ Is the McKenzie-Thompson group easy to describe? $\endgroup$ Nov 18, 2011 at 3:04
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Nov 18, 2011 at 4:02
  • 1
    $\begingroup$ Sounds like a candidate to be natural. I prefer an example encoding all of recursive function theory, which is a natural notion, than encoding Turing machine commands. $\endgroup$ Nov 18, 2011 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.