The word problem and the isomorphism problem for groups
John Stillwell · Bulletin of the American Mathematical Society · 1982
If the fundamental problem of mathematics is to decide when two things are the same, then the fundamental problem of group theory is to decide when two groups are isomorphic.This problem was first stated, for finitely presented groups, by Tietze [1908], and proved unsolvable by Adian and Rabin 50 years later.Using their result, Markov[ 1958] proved the unsolvability of the fundamental problem of topology; the homeomorphism problem.Of course, combinatorial group theory and topology grew up together, and their connection via the fundamental group was well known; the bridge between them and logic is the word problem for groups, proved unsolvable by Novikov in 1955.The history of the word problem divides naturally into three eras: 1880-1930, in which combinatorial group theory interacts mainly with topology and the major positive results are obtained; 1930-1955, in which computability theory emerges and, after a great struggle, yields Novikov's unsolvability proof; 1955-1980, in which group theory interacts with logic to simplify the proof.In 1955, the characteristic properties of groups appeared mainly as obstacles to an unsolvability proof-witness the 143 pages of Novikov's paper.It took 25 years to properly understand the group theoretic construction, the HNN extension, which allows group theory and computation to work together.Today it is clear that the negative theorem on the word problem has brought positive benefits to group theory in the form of techniques suitable for giving a clear proof.The main purpose of this paper is to give such a proof, based on that of Cohen and Aanderaa [1980], but with the historical background necessary for full motivation and understanding.I shall therefore discuss the story of the word problem up to Magnus' solution for one-relator groups around 1930, the notion of computation developed by logicians of the 1930's, results on semigroups which foreshadowed those on groups, before treating the development of HNN theory and its contribution to the word and isomorphism problems.The technical details have been concentrated in § §1, 4, 6-8, 11-14, so readers who want an unadulterated proof of unsolvability of the word problem need read only these.1. Review of combinatorial group theory.For logicians, the most natural approach to combinatorial group theory is that of Magnus, used in Magnus