Before asking my question, let me define my terms.

Let $G$ be a finitely generated group with fixed generating set $A$. Let $\psi\colon (A\cup A^{-1})^{\ast}\to G$ be the canonical projection where $X^*$ denotes the free monoid on a set $X$.

Definition 1.A subgroup $H$ of $G$ has adecidable membership problemif there is a Turing machine which on input a word $w\in (A\cup A^{-1})^{\ast}$ outputs "Yes", if $\psi(w)\in H$, and "No", otherwise.

The *generalized word problem* is said to be decidable for $G$ if each finitely generated subgroup of $G$ has decidable membership problem.

Definition 2.$G$ has decidableuniform generalized word problemif there is a Turing machine which on input words $w_1,\ldots, w_k,w\in (A\cup A^{-1})^{\ast}$ outputs "Yes", if $\psi(w)\in \langle \psi(w_1),\ldots,\psi(w_k)\rangle$, and "No", otherwise.

One easily verifies that decidability of these problems is independent of the chosen finite generating set.

Trivially decidablity of the uniform generalized word problem implies decidability of the generalized word problem. The difference between the two problems is that the uniform generalized word problem asks that there is a computable map that takes a finite subset of $G$ to a Turing machine which decides membership in the subgroup it generates.

My question is:

Does anybody know an example of a group with decidable generalized word problem but undecidable uniform generalized word problem?

In case no example is known, here is a proposed attack that I am not capable of implementing. A finitely generated group is a *Tarski monster* if it is infinite but all its proper subgroups are finite. Olshanskii has constructed such "beasts".

Observation 1.A Tarski monster $G$ has decidable generalized word problem iff it has decidable word problem.

For the non-trivial direction, the Turing machine which always says "Yes" solves the membership problem in $G$. If $H$ is a proper subgroup, there is a Turing machine who knows a finite list of words representing all the elements of $H$ and so it can take an input word and use the word problem for $G$ to decide if the input word belongs to $H$.

Observation 2.A Tarski monster $G$ with decidable word problem has decidable uniform generalized word problem iff one can decide given elements $w_1,\ldots, w_k\in (A\cup A^{-1})^{\ast}$ whether $G=\langle \psi(w_1),\ldots, \psi(w_k)\rangle$.

Indeed, if the uniform generalized word problem is decidable, then one can check whether each letter of the generating set $A$ of $G$ belongs to $\langle \psi(w_1),\ldots, \psi(w_k)\rangle$.

For the converse, given words $w_1,\ldots, w_k,w\in (A\cup A^{-1})^{\ast}$ one first checks whether $\psi(w_1),\ldots,\psi(w_k)$ generates $G$. If so, the Turing machine outputs "Yes". Otherwise, $\psi(w_1),\ldots,\psi(w_k)$ generates a finite subgroup. Using decidability of the word problem, the Turing machine can compute the finite subgroup $\langle \psi(w_1),\ldots, \psi(w_k)\rangle$ (by taking products until nothing new can be obtained) and then use the word problem again to determine if $\psi(w)$ belongs to this subgroup.

Is there a Tarski monster with decidable word problem, but for which on cannot decide whether a given finite set of elements generate it?

**Update**

Derek has shown that Tarski monsters will always have decidable uniform generalized word problem as soon as they have decidable word problem because the word problem already gives that one can decide if a finitely generated subgroup is the whole group. I'm a bit embarrassed I didn't see that. My original question still seems open though.

4more comments