there is a partial recursive function fP such that: More informally, there is an algorithm that halts if u=v, but does not do so otherwise. It follows that to solve the word problem for P it is sufficient to construct a recursive function g such that: However u=v in G if and only if in G. It follows that to solve the word problem for P it is sufficient to construct a recursive function h such that: Example The following will be proved as an example of the use of this technique: Theorem: A finitely presented residually finite group has solvable word problem. Proof: Suppose G = ⟨X|R⟩ is a finitely presented, residually finite group. Let S be the group of all permutations of N, the natural numbers, that fixes all but finitely many numbers then: S is locally finite and contains a copy of every finite group. The word problem in S is solvable by calculating products of permutations. There is a recursive enumeration of all mappings of the finite set X into S. Since G is residually finite, if w is a word in the generators X of G then in G if and only of some mapping of X into S induces a homomorphism such that in S. Given these facts, algorithm defined by the following pseudocode: For every mapping of X into S If every relator in R is satisfied in S If w ≠ 1 in S return 0 End if End if End for defines a recursive function h such that: This shows that G has solvable 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 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 K of groups, it is sufficient to find a recursive function that takes a finite presentation P for a group G and a word in the generators of G, such that whenever G ∈ K: 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.