= ⟨X|R⟩ of a group H, one can recursively enumerate all homomorphisms h: H → G by first enumerating all mappings h†: X → G. Not all of these mappings extend to homomorphisms, but, since h†(R) is finite, it is possible to distinguish between homomorphisms and non-homomorphisms, by using the solution to the word problem in G. "Weeding out" non-homomorphisms gives the required recursive enumeration: h1, h2, ..., hn, ... . If H has solvable word problem, then at least one of these homomorphisms must be an embedding. So given a word w in the generators of H: 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 hn(w) ≠ 1 in G) Let repeatable = FALSE output 0. This describes a recursive function: The function f clearly depends on the presentation P. Considering it to be a function of the two variables, a recursive function has been constructed that takes a finite presentation P for a group H and a word w in the generators of a group G, such that whenever G has soluble word problem: 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 G cannot exist. Algebraic structure and the word problem There are a number of results that relate solvability of the word problem and algebraic structure. The most significant of these is the Boone-Higman theorem: A finitely presented group has solvable word problem if and only if it can be embedded in a simple group that can be embedded in a finitely presented group. It is widely believed that it should be possible to do the construction so that the simple group itself is finitely presented. If so one would expect it to be difficult to prove as the mapping from presentations to simple groups would have to be non-recursive. The following has been proved by Bernhard Neumann and Angus Macintyre: A finitely presented group has solvable word problem if and only if it can be embedded in every algebraically closed group What is remarkable about this is that the algebraically closed groups are so wild that none of them has a recursive presentation. The oldest result relating algebraic structure to solvability of the word problem is Kuznetsov's theorem: A