Finding the Automorphism Group of a Finitely Presented Group with Solvable Word Problem I'm not sure if this question is more suited to mathoverflow.
Is there a systematic way to solve for the automorphism group of a finitely presented group with a solvable word problem? Preferably with software. 
Here is my particular example:
$$G_n = \langle r_1, r_2, \dots , r_n \; \vert \;r_i^{n_i}, r_1 r_2 \dots r_n \rangle \quad \text{for some} \quad \{n_i\} \subset\mathbb N$$
This is a type of hyperbolic reflection group generated by a finite number of rotations. They are index $2$ subgroups of coxeter groups.
I've tried using the GAP System for Computational Discrete Algebra to find the automorphism group, but the method AutomorphismGroup doesn't seem to terminate. However, a rewriting system for all such groups can be developed using the kbmag package.
I'm actually interested in the outer automorphisms, as these are nontrivial. I expect the rank of $\mathrm{Out}(G_4)$ to be $2$, and I think I have the explicit form of the generators in this case. 
However, I don't know how to check whether my suspected generators do in fact generate the whole outer automorphism group, and so I seek a way to compute $\mathrm{Out}(G_i)$ for given rotation orders $n_i$. 
 A: I doubt there exist such general algorithms as you ask for.
However, I think this particular outer automorphism group can be identified using some topology. It is very close related to the "pure" mapping class group of the $n$-times punctured sphere $X = S^2 - \{p_1,...,p_n\}$, meaning the group of homeomorphisms preserving each puncture, modulo isotopy. Your group is isomorphic to the fundamental group of the compact 2-orbifold having underlying space $S^2$ and with cone points at $p_1,...,p_n$ having angles $2 \pi / n_1$,...,$2 \pi / n_n$ (subject to disambiguating $n$). In particular every homeomorphism of $X$ that preserves each puncture determines an outer automorphism of your group, and from this you get an injective homomorphism from the pure mapping class group of $X$ to the outer automorphism group of your group. I'm also pretty sure that this injective homomorphism has finite index image (and is in fact an isomorphism if the exponents $n_1,...,n_n$ are pairwise distinct; one needs to prove that the generating set $r_1,...,r_n$ is permuted up to conjugacy, and this is the one place where I am unsure...).
With these ideas, it follows that there are a lot of interesting generators which can be visualized using topology, and then written down very concretely. For instance, there is a circle on the sphere separating the points $p_1,...,p_k$ from the points $p_{k+1},...,p_n$ and representing the group element $t = r_1 \cdots r_k$. Doing a Dehn twist around that circle represents the outer automorphism class of the automorphism fixing $r_1,...,r_k$ and mapping $r_i \to t r_i t^{-1}$ for $i=k+1,...,n$.
I'll say that these ideas are all closely related to the circle of ideas surrounding the Dehn-Nielsen-Baer theorem which says that if $S$ is a compact, connected, oriented surface of genus $\ge 1$ then $\text{Out}(\pi_1 S)$ is isomorphic to the mapping class group of $S$. I believe that much of the Dehn-Nielsen-Baer theorem extends to compact, hyperbolic 2-orbifolds, although finding a reference to this might be difficult.
Added: You also asked about half-twist generators. Again, these can be described pretty much straight from the topological picture. For instance, the group element $t = r_1 r_2$ represents a circle separating $p_1,p_2$ from the rest of the cone points. Assuming the orders of $p_1,p_2$ are equal, a half-twist around that circle is represented by the outer automorphism class of the automorphism $r_1 \to r_1 r_2 \bar r_1$, and $r_2 \to r_1$, and $r_i \to r_i$ for $i=3,...,n$.
A: There are a number of algorithms for automorphism group computations of finite groups. I am not aware of a generic algorithm for infinite groups.
I suspect that for infinite polycyclic groups it might be possible (modulo some potentially nasty number theory) to generalize the methods for finite solvable groups, but that is a research-level problem without a turn-key implementation.
When you call AutomorphismGroup in GAP on a finitely presented group, it will try to test finiteness first, this is probably the non-terminating calculation you observe.
