Upon thinking about [this question](https://mathoverflow.net/questions/20308), I have a feeling that there is an interesting general problem like that, but I cannot verbalise it. Here is an approximation.


The question is: given a finitely generated group $G$ and a finite set $S\subset G$, we want to find out whether the subgroup generated by $S$ is the whole group. Is there an algorithm deciding this?


One has to specify how $G$ and $S$ are presented to a machine. As for $S$, its elements are given as words in some generating set for $G$. The question how to represent a group is more delicate. Obviously not by a set of relations, since the identity problem is undecidable. There are two ways I see.


1) Let's say that $G$ is *nice* if there is an algorithm deciding the above problem for this group only. For example, $\mathbb Z^n$ is nice, [edit:] free groups are nice, and probably many others. Are all groups nice? What about some reasonable classes, like lattices in Lie groups?


2) This one is the best approximation of my intuitive picture of a question. Suppose we have an algorithm $A$ deciding the identity problem in $G$. (This algorithm tells us whether two elements of $G$, presented as words, are equal.) Or maybe it's an oracle rather than algorithm, I don't feel the difference. Can we decide the above problem using $A$?


**Update.** It turns out that even $F\_6\times F\_6$ is not nice in the above sense (see John Stillwell's answer). This kills the second part too. The only question that remains unanswered is the one with the least motivation behind it: Is "generating problem" solvable in lattices of Lie groups?



Is it decidable whether a given set generates the whole group?
The answer to the title question is that the problem is unsolvable. See p. 194 of Lyndon and Schupp's *Combinatorial Group Theory*, where it is called the "generating problem." It is unsolvable even when $G$ is the direct product of free groups of rank at least 6.


