recursively presented simple group S has solvable word problem. To prove this let ⟨X|R⟩ be a recursive presentation for S. Choose a ∈ S such that a ≠ 1 in S. If w is a word on the generators X of S, then let: There is a recursive function such that: Write: Then because the construction of f was uniform, this is a recursive function of two variables. It follows that: is recursive. By construction: Since S is a simple group, its only quotient groups are itself and the trivial group. Since a ≠ 1 in S, we see a = 1 in Sw if and only if Sw is trivial if and only if w ≠ 1 in S. Therefore: The existence of such a function is sufficient to prove the word problem is solvable for S. This proof does not prove the existence of a uniform algorithm for solving the word problem for this class of groups. The non-uniformity resides in choosing a non-trivial element of the simple group. There is no reason to suppose that there is a recursive function that maps a presentation of a simple groups to a non-trivial element of the group. However, in the case of a finitely presented group we know that not all the generators can be trivial (Any individual generator could be, of course). Using this fact it is possible to modify the proof to show: The word problem is uniformly solvable for the class of finitely presented simple groups. See also Combinatorics on words SQ-universal group Word problem (mathematics) Reachability problem Nested stack automata (have been used to solve the word problem for groups) Notes References Group theory Combinatorics on words Articles with example pseudocode Articles containing proofs Undecidable problems