Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
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. –  Benjamin Steinberg Nov 18 '11 at 0:11
    
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. –  Mark Sapir Nov 18 '11 at 1:18
    
Is the McKenzie-Thompson group easy to describe? –  Benjamin Steinberg Nov 18 '11 at 3:04
    
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
    
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. –  Benjamin Steinberg Nov 18 '11 at 15:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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