gr.group theory - Recursive presentations

The answer is a simple trick. Essentially no group theory is involved.

Suppose that we are given a group presentation with a set of generators, and relations R_0, R_1, etc. that have been given by a computably enumerable procedure. Let us view each relation as a word in the generators that is to become trivial in the group.

Now, the trick. Introduce a new generator x. Also, add the relation x, which means that x will be the identity. Now, let S_i be the relation (R_i)x^(t_i), where t_i is the time it takes for the word R_i to be enumerated in the enumeration algorithm. That is, we simply pad R_i with an enormous number of x's, depending on how long it takes for R_i to be enumerated into the set of relations. Clearly, S_i and R_i are going to give the same group, once we have said that x is trivial, since the enormous number of copies of x in S_i will all cancel out. But the point is that the presentation of the group with this new presentation becomes computably decidable (rather than merely enumerable), because given a relation, we look at it to see if it has the form Sx^t for some t, then we run the enumeration algorithm for t steps, and see if S has been added. If not, then we reject; if so, then we accept.

One can get rid of the extra generator x simply by using the relation R_0 from the original presentation. This gives a computable set of relations in the same generating set that generates the same group.

The essence of this trick is that every relation is equivalent to a ridiculously long relation, and you make the length long enough so that one can check that it really should be there.