I was recently given feedback on an assignment in Geometric Group Theory that the following proposition is false:
If $G = \langle S \rangle$ is finitely generated and has solvable word problem, then for every word $w \in F(S)$, $d_{S}(e,w)$ is computable
(where $e$ is identity element of $G$ and $F(S)$ is the free group on $S$)
Here's an attempeted proof of the statement, where do I go wrong?
By definition of word metric $d_{S}$, $d_{S}(e,w) = |v|_{S} \leq |w|_{S}$ for some $v \in F(S)$ such that $v =_{G} w$. To find such a $v$, enumerate all words $v \in F(S)$ of length $|v|_{S} \leq |w|_{S}$. Since $S$ is a finite set and $|w|_{S}$ is finite, there are only finitely many such $v$. At each step in the enumeration, use $G$'s solvable word procedure to determine if $v =_{G} w$ (i.e $vw^{-1} =_{G} e$). Terminate the enumeration with the $v$ of shortest length. The length of $v$ is $d_{S}(e,w)$.
If $S$ is not assumed to be finite, one has to be careful in the formulation "$G=\langle S\rangle$ is finitely generated with solvable word problem". If one understands that $G$ has solvable word problem (in the usual sense, w.r.t some/any finite generating subset), then there are trivial counterexamples if it is not assumed that $S$ is finite.
For instance, let $G=\mathbf{Z}$. Let $I$ be a subset of $\mathbf{N}$; define $s(n)=2$ for $n\in I$ and $s(n)=3$ for $n\notin I$. Define $u(n)=n!$ for $n\ge 1$ odd and $u(n)=s(n/2)(n-1)!$ for $n$ even.
So $u(1)=1$, $u(2)\in\{2,3\}$, $u(3)=6$, $u(4)\in\{12,18\}$, $u(5)=120$, etc.
Then $u$ is injective; since $u_1=1$, the image of $u$ generates $\mathbf{Z}$. Let the free group on $\mathbf{N}_{>0}$ map to $\mathbf{Z}$ by the assignment $s_i\mapsto u(i)$. Then the word length of the image of $s_i^2$ is 1 if and only if $n\in I$. In particular, if $I$ is not a recursive subset, then the word length is not computable.
Edit: If one understands that $G$ has solvable word problem with respect to the family $S$, then it slightly more tricky when $S$ is infinite. (When $S$ is finite, the word length is computable, as you proved it.)
But a variant of the previous example works. Let $G$ be an arbitrary infinite f.g. group with solvable word problem (for instance $\mathbf{Z}$). Fix a finitely generated free group $F$ with a surjective homomorphism to $G$, and let $(s_n)_{n\in\mathbf{N}}$ be an arbitrary computable sequence in $F$, starting with the family of free generators. Then the corresponding word problem (determining whether an element of $F_\mathbf{N}$ maps to a trivial element of $G$) is solvable, by computation inside $F$.
On the other hand, we can assume that the image of the family is a recursively enumerable, but non-recursive subset of $G$. In this case, the word length is not computable, since one cannot decide whether the length of an element is 1.