Editing Word problem for groups (section)

==Unsolvability of the uniform word problem==
{{more citations needed section|date=December 2018}}
The criterion given above, for the solvability of the word problem in a single group, can be extended by a straightforward argument. This gives the following criterion for the uniform solvability of the word problem for a class of finitely presented groups:

::To solve the uniform word problem for a class <math>K</math> of groups, it is sufficient to find a recursive function {{tmath|f(P,w)}} that takes a finite presentation <math>P</math> for a group <math>G</math> and a word {{tmath|w}} in the generators of <math>G</math>, such that whenever <math>G \in K</math>:
:::<math>f(P,w) = 
\begin{cases} 
0 &\text{if}\ w\neq1\ \text{in}\ G \\
\text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ G
\end{cases}</math>

:: '''Boone-Rogers Theorem:''' There is no uniform [[partial algorithm]] that 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 <math>G</math> is a finitely presented group that contains an isomorphic copy of every finitely presented group with solvable word problem, then <math>G</math> itself must have unsolvable word problem.

'''Remark:''' Suppose <math>G = \langle X \, | \, R \rangle</math> is a finitely presented group with solvable word problem and <math>H</math> is a finite subset of <math>G</math>. Let <math>H^* = \langle H \rangle</math>, be the group generated by <math>H</math>. Then the word problem in <math>H^*</math> is solvable: given two words <math>h, k</math> in the generators <math>H</math> of <math>H^*</math>, write them as words in <math>X</math> and compare them using the solution to the word problem in <math>G</math>. It is easy to think that this demonstrates a uniform solution of the word problem for the class <math>K</math> (say) of finitely generated groups that can be embedded in <math>G</math>. If this were the case, the non-existence of a universal solvable word problem group would follow easily from Boone-Rogers. However, the solution just exhibited for the word problem for groups in <math>K</math> is not uniform. To see this, consider a group <math>J = \langle Y \, | \, T \rangle \in K</math>; in order to use the above argument to solve the word problem in <math>J</math>, it is first necessary to exhibit a mapping <math>e : Y \to G</math> that extends to an embedding <math>e^* : J \to G</math>. If there were a recursive function that mapped (finitely generated) presentations of groups in <math>K</math> to embeddings into <math>G</math>, then a uniform solution of the word problem in <math>K</math> 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 sophisticated argument, the word problem in <math>J</math> can be solved ''without'' using an embedding <math>e : J \to G</math>. Instead an ''enumeration of homomorphisms'' is used, and since such an enumeration can be constructed uniformly, it results in a uniform solution to the word problem in <math>K</math>.

===Proof that there is no universal solvable word problem group===
Suppose <math>G</math> were a universal solvable word problem group. Given a finite presentation <math>P = \langle X \, | \, R \rangle</math> of a group <math>H</math>, one can recursively enumerate all homomorphisms <math>h : H \to G</math> by first enumerating all mappings <math>h^\dagger : X \to G</math>. Not all of these mappings extend to homomorphisms, but, since <math>h^\dagger(R)</math> is finite, it is possible to distinguish between homomorphisms and non-homomorphisms, by using the solution to the word problem in <math>G</math>. "Weeding out" non-homomorphisms gives the required recursive enumeration: <math>h_1, h_2, \ldots, h_n, \ldots</math>.

If <math>H</math> has solvable word problem, then at least one of these homomorphisms must be an embedding. So given a word <math>w</math> in the generators of <math>H</math>:

::<math>\text{If}\ w\ne 1\ \text{in}\ H,\ h_n(w)\ne 1\ \text{in}\ G\ \text{for some}\ h_n </math>
::<math>\text{If}\ w= 1\ \text{in}\ H,\ h_n(w)= 1\ \text{in}\ G\ \text{for all}\ h_n </math>

Consider the algorithm described by the pseudocode:

 '''Let''' ''n'' = 0
 '''Let''' ''repeatable'' = TRUE
 '''while''' (''repeatable'')
     increase ''n'' by 1
     '''if''' (solution to word problem in ''G'' reveals ''h<sub>n</sub>''(''w'') ≠ 1 in ''G'')
         '''Let''' ''repeatable'' = FALSE
 output 0.

This describes a recursive function:

::<math>f(w) = 
\begin{cases} 
0 &\text{if}\ w\neq1\ \text{in}\ H \\
\text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ H.
\end{cases}</math>

The function <math>f</math> clearly depends on the presentation <math>P</math>. Considering it to be a function of the two variables, a recursive function {{tmath|f(P,w)}} has been constructed that takes a finite presentation <math>P</math> for a group <math>H</math> and a word <math>w</math> in the generators of a group <math>G</math>, such that whenever <math>G</math> has soluble word problem:

::<math>f(P,w) = 
\begin{cases} 
0 &\text{if}\ w\neq1\ \text{in}\ H \\
\text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ H.
\end{cases}</math>

But this uniformly solves the word problem for the class of all finitely presented groups with solvable word problem, contradicting Boone-Rogers. This contradiction proves <math>G</math> cannot exist.