If one takes a group presentation then one can ask various questions of it, such as "is this element equal to the identity", "are these elements conjugate" etc. I was wondering if the solution to such a problem in a representation of a group always yields a solution to the problem with respect to the presentation.


For example, if $G$ is a finitely generated group with soluble word problem then one can use the word problem for $G$ to work out if two elements of $\operatorname{Aut}(G)$ are different in finite time (if $\phi: x\_i\mapsto X\_i$ and $\varphi: x\_i\mapsto Y\_i$ then $\phi=\varphi$ if and only if $X\_i=Y\_i$ for all $i\in I$, $|I|<\infty$). However, I am unsure whether this amounts to a solution to the word problem for $\operatorname{Aut}(G)$. This is because in order to solve the word problem for $\operatorname{Aut}(G)\cong\langle X; R\rangle$ this way one would need to know in what way the given presentation *is* $\operatorname{Aut}(G)$; one would need to first know the isomorphism between $\operatorname{Aut}(G)$ and $\langle X; R\rangle$, but...can this always be done?


I am expecting the answer to be "yes, of course, don't be stupid!" but I just can't see how this would hold (although *obviously* it should)!



Decision problems and group representations
Decidability of the word problem for a finitely generated group has nothing to do with a presentation of the group. It is not part of the input. If G is a finitely generated group with solvable word problem and H is a finitely generated group of automorphisms of G, then H has decidable word problem. There exists a Turing machine that knows how the generators of H act on the generators of G (don't ask me which Turing Machine). This machine can implement the algorithm you give.


It is a common misconception that decidability involves something effective. It merely asserts the existence of a Turing machine. This is why a problem with only finitely many inputs is always decidable even though I may not know which Turing machine is the one that says yes in the right cases.


