Word Problem For Groups - Unsolvability of The Uniform Word Problem

Unsolvability of The Uniform Word Problem

The criterion, given above for the solvability of the word problem in a single group can be extended to a criterion for the uniform solvability of the word problem for a class of finitely presented groups by a straightforward argument. The result is:

To solve the uniform word problem for a class K of groups it is sufficient to find a recursive function f(P,w) that takes a finite presentation P for a group G and a word w in the generators of G such that whenever in G ∈ K:

Boone- Rogers Theorem: There is no uniform partial algorithm which solves the word problem in all finitely presented groups with solvable word problem.

In other words the uniform word problem for the class of all finitely presented groups with solvable word problem is unsolvable. This has some interesting consequences. For instance the Higman embedding theorem can be used to construct a group containing an isomorphic copy of every finitely presented group with solvable word problem. It seems natural to ask whether this group can have solvable word problem. But it is a consequence of the Boone-Rogers result that:

Corollary: There is no universal solvable word problem group. That is, if G is a finitely presented group which contains an isomorphic copy of every finitely presented group with solvable word problem, then G itself must have unsolvable word problem.

Remark: Suppose G = ⟨X|R⟩ is a finitely presented group with solvable word problem and H is a finite subset G. Let H* = ⟨H⟩, be the group generated by H. Then the word problem in H* is solvable: given two words h, k in the generators H of H*, write them as words in X and compare them using the solution to the word problem in G. It is easy to think that this demonstrates a uniform solution the word problem for the class K (say) of finitely generated groups that can be embedded in G. If this were the case the non-existence of a universal solvable word problem group would follow easily from Boone-Rogers. However, solution just exhibited for the word problem for groups in K is not uniform. To see this consider a group J = ⟨Y|T⟩ ∈ K, in order to use the above argument to solve the word problem in J, it is first necessary to exhibit a mapping e: Y → G that extends to an embedding e*: J → G. If there were a recursive function that mapped (finitely generated) presentations of groups in K to embeddings into G, then a uniform solution the word problem in K could indeed be constructed. But there is no reason, in general, to suppose that such a recursive function exists. However, it turns out that, using a more sophisicated argument, the word problem in J can be solved without using an embedding e: J → G. Instead an enumeration of homomorphisms is used, and since such enumeration can be constructed uniformly, it results in a uniform solution to the word problem in K.