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 a decidable membership problem if 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 decidable uniform generalized word problem if 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.
Best Answer
I think the answer to your final question is no. Given a finite set of generators of a subgroup $H$ of a Tarski Monster $G$, systematically evaluate words in those generators. You can use your solution to the word problem to check equality in $G$ between words. Either you will eventually produce a finite set of group elements which is closed under multiplication by the generators of $H$ and their inverses, in which case $H$ is finite, or else you will eventually find all of the generators of $G$, in which case $H=G$.