Abstract

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10