Combinatorial group theory started with Walther von Dyck, who was a student of Felix Klein. The relevant paper was published in 1882 with a second paper in the following year. His aim was to study discrete groups of isometries of hyperbolic space. The 1882 paper Gruppentheoret5ische Studien contains thefirst appearance of a group presentation as we know it. He assumes (without rigorous justification) the existence of a free group of every finite rank and he gives a result (again not rigorously proved) that every m generator group can be obtained from the free group of rank m by adding relations. He knew intuitively how to tell whether a word in the free group is trivial - make all cancellations of aa^-1 and a^-1a for every generator a appearing in the word.

Heinrich Tietze published the paper Über die topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten in 1908. The topological part of this paper was based on the notion of the fundamental group introduced by Poincaré in 1895. In the 1908 paper Tietze defined the fundamental group of a manifold and showed that it was a topological invariant. To do this he introduced Tietze transformations. He proved that any two finite presentations for the same group can be transformed to each other by applying finitely many Tietze transformations. He wrote:-

One observes at once that it may happen that two groups are isomorphic although they are defined using different systems of generators and defining relations. ... However, neither the general problem of characterising the totality of all abstract ways of generating a given group nor even the special problem of finding a method to decide whether two groups given by their presentations are isomorphic, have been solved.

In 1910 Max Dehn published Über die Topologie des dreidimensionalen Raumes (On the topology of 3-dimensional space). In this paper he considered the problem of when two knots are the same, building on the work of Poincaré. Here he dealt with the fundamental group as a key invariant and this group occursnaturally as given by a presentation. He quickly realised that the knot theory problems were special cases of much more general questions about finitely presented groups. He made the group theory problems explicit in his 1911 paper Über unendliche diskontinuierliche Gruppen. We quote from the paper givingDehn's formulation of the word problem for groups:-

The general discontinuous group is given by n generators and m relations between them, as defined by Dyck (Math. Ann., 20 and 22). The results of those works, however, relate essentially to finite groups. The general theory of groups defined in this way at present appears very undeveloped in the infinite case. Here there are above all three fundamental problems whose solution is very difficult and which will not be possible without a penetrating study of the subject.

1. The Identity Problem [now called the Word Problem]: An element of the group is given as a product of generators. One is required to give a method whereby it may be decided in a finite number of steps whether this element is the identity or not.

2. The Transformation Problem [now called the Conjugacy Problem]: Any two elements S and T of the group are given. A method is sought for deciding the question of whether S and T can be transformed into each other, i.e. whether there is an element U of the group satisfying the relation S = UTU^-1.

3. The Isomorphism Problem: Given two groups, one is to decide whether they are isomorphic or not (and further, whether a given correspondence between the generators of one group and elements of the other is an isomorphism or not).

These problems have very different degrees of difficulty. ... One is already led to them by necessity with work in topology. Each knotted space curve, in order to be completely understood, demands the solution of the three above problems in a special case.

Notice that there is a simple connection between the Conjugacy Problem and the Word Problem. If one can solve the Conjugacy Problem in a particular group then one can solve the Word Problem. For if a word w is conjugate to the identity, then it is equal to the identify of the group. Dehn also proved in this 1911 paper that a finitely presented group can have a subgroup which is not finitely presented. He also solved the isomorphism problem and the conjugacy problem for finitely presented groups with the property that each generator occurs at most twice in each of the defining relations.

In 1912 Dehn studied the word problem and the conjugacy problem for the fundamental groups of orientable closed 2-dimensional manifolds. These are 1-relator groups, that is groups with a presentation with a single defining relation. He showed in Transformationen der Kurven auf zweiseitigen Flächen (1912) that in special cases one could solve the word problem using a direct approach - called Dehn's algorithm today. In this case one could construct a finite list of words in the group generators, u₁ , v₁ , u₂ , v₂ , ... u_n , v_n having the following properties. One has u_i = v_i as elements of the group, v_i is shorter than u_i for each i, and one has the property that if w is any word in the generators which represents the identity element, then at least one of the u_i is a subword of w. When a list with these properties exists one can easily solve the word problem. For, given a word w one looks to see if it contains a u_i . If it does not, then w is not the identity. If it does contain a u_i then replace u_i by v_it o obtain a new word w'. Then continue the process, looking to see if w' contains a u_i . The process must terminate in a finite number of steps, since each time a u_i is replaced by a v_i a shorter word is obtained.

Dehn knew that the word problem was difficult and posed an entirely new type of question in mathematics. He wrote:-

Solving the word problem for all groups may be as impossible as solving all mathematical problems.

Dehn solved the word problem for the trefoil knot group in 1914. He used his solution to show that right and left trefoils are distinct. We note, as an aside, that Waldhausen solved the word problem for all knot groups in 1968.

We now want to follow two routes forward, one for free groups and one for 1-relator groups. First note that the word problem in a free group is easily solved. As von Dyck noted, just use free reduction (but more is required for a rigorous proof which we will discuss below).

In 1921 Jakob Nielsen published Om Regning med ikke kommutative Faktoren og dens Anvendelse in Gruppeteorien. In this paper he showed how, given a set of words { u₁ , u₂ , ..., u_m } in a free group, one could construct a set of free generators for the subgroup they generate. In particular, he could deduce that a finitely generated subgroup of a free group was necessarily free. His work was motivated by the study of word problems. He also gave a method for solving the membership problem in free groups, that is an algorithm to determine whether a given word w in a free group was contained in the subgroup generated by { u₁ , u₂ , ..., u_m }.

A general statement of the membership problem was not given until 1958 by Mihailova:

Membership Problem: Let G = < X | R > be a finite presentation, and U a finite set of words { u₁ , u₂ , ..., u_m } in the alphabet X. Let H be the subgroup of G generated by U. Given a word w in the generators X, can one decide whether or not w is in H?

The Membership Problem is also called the generalised word problem when { u₁ , u₂ , ..., u_m } is a subset of X.

Otto Schreier attended a lecture by Kurt Reidemeister in Hamburg in January 1926. In this lecture Reidemeister described how to find a presentation for a normal subgroup of finite index in a finitely presented group. After the seminar, Schreier thought about Reidemeister's method and eventually saw how to extend the method to arbitrary subgroups of possibly infinite index in a countably generated group. With this method he was able to extend Nielsen's result on subgroups of free groups to prove that every subgroup of a free group is free. He published these results in 1927 and at the same time gave a simple rigorous proof of the solution of the word problem in a free group. In this 1927 paper he also introduced the notion of free products with amalgamation.

Nielsen returned to the problem of a free group of countable rank in 1955. He noted that if G = < X | R > and F is the free group on the set X, then one can define a natural homomorphism from F to G. Suppose K is the kernel of this homomorphism, so K is the normal closure of the set of words R in the free group F. Then the word problem for G is equivalent to the problem of deciding which elements of F belong to K. He wrote:-

If K is determined by a given infinite set S = { a₁ , a₂ , .... } of elements generating K, then there exists a function L(n) such that all elements of K of length not exceeding n are contained in the subgroup K_L generated by the subset { a₁ , a₂ , ...., a_L } of S; and for K_L a basis can be constructed in a finite number of steps. However, the dependence of L on n cannot, in general, be determined unless some further information can be gained from the structure of S. It is therefore only for finitely generated groups K that the identification of their elements can be assured unconditionally in a finite number of tests.

In 1926 Emil Artin solved the word problem for braid groups.

Let us now look at 1-relator groups. The solution to the word problem for these groups began with Dehn who stated the Freiheitssatz:

Let G = < A | r = 1 > where r is freely and cyclically reduced. Let U be a subset of A with the property that not every generator appearing in r is in U. Then U freely generates a free subgroup of G.

Dehn wasn't happy with his proof of this result, so, having an excellent research student Wilhelm Magnus, he gave his student the task of giving a rigorous proof. Magnus solved the problem that Dehn had given him in 1930. Schreier had introduced the concept of free products with amalgamation and Magnus used these ideas but didn't base his proof on Schreier's results, rather preferring to reprove the special cases he needed. In the following year Magnus published a paper containing a special case of the word problem for 1-relator groups, then in 1932 he published a complete proof of the solution of the word problem for this class of groups.

We have given several examples of the word problem being proved for certain classes of groups, but said nothing about groups for which the word problem could not be solved. Until the 1950s only positive results could be obtained since totally new methods were needed even to state the problem of finding a group with insoluble word problem with the formal precision needed to give mathematicians a chance to come up with proofs. As Chandler and Magnus state:-

The answer to a decision problem is an algorithm or a general and effective procedure. All one could say about these concepts in the time of Hilbert and Dehn was that one knew one when one saw one.

However, if one only 'knew one when one saw one', how could someone possible prove that no such algorithm existed. It required computability theory and developments in mathematical logic to even make the questions precise, but these areas were to not only provide explicit questions, they also provided solutions to the questions.

In the 1930s Kurt Gödel investigated how symbolic manipulation in formal logic could be simulated by functions on the natural numbers. These functions were built up from simple functions. Independently of Gödel, Alonzo Church was developing the λ-calculus designed to clarify the foundations of mathematics, in particular the meaning of variables. This development was to lead to the study of recursive functions. Stephen Kleene was a doctoral student of Church at Princeton and he was given as a project the task of determining which functions were l-definable. At first Kleene could make no progress at all on this project, then one day he had to visit the dentist to get two wisdom teeth extracted. While sitting in the dentist's chair waiting for this unpleasant experience, inspiration struck and suddenly he saw the route to the solution. Within six months he had complete answers to the problem. In 1933 Church produced what today is called "Church's thesis" which states that l-definability is the precise notion of "computable function". This is not a theorem, it is simply saying that the vague notion of "computable function" can be given the rigorous definition of l-definability. In 1936 Alan Turing produced the notion of a Turing machine and proposed that a "computable function" was one which could be computed by a Turing machine. Quite quickly it was shown that a function was l-definable precisely when it can be computed by a Turing machine, so the two concepts are equivalent. This was enough for almost all mathematicians to accept that these equivalent concepts rigorously embodied the intuitive concept of "computable function".

Given a problem P where P is an infinite set of questions Q_i , we say that P is solved if we can compute the function f : P→ { Y, N } so that f(Q_i) = Y if the answer to Q_i is YES, and f(Q_i) = N if the answer to Q_i is NO. If we can show that no such function f can be computed by a Turing machine, then problem P is insoluble. Before continuing to describe the history, let us define some concepts.

A set S is recursively enumerable if there is an algorithm to list the elements of S, where we use the standard Turing machine model of computation.

A set S is recursive if both S and its complement are recursively enumerable.

All undecidable questions in mathematics are a result of the fact that there exist sets which are recursively enumerable but not recursive. For a finitely presented group all the decision problems we have described above - the word problem, the conjugacy problem, etc - are recursively enumerable but not recursive. By this we mean that, given any finitely presented group, we can set a procedure going which will say YES if the word we give it is equal to the group identity. However, it does not say NO if it isn't, so we sit waiting for a procedure to say YES but if nothing happens then we can't tell if the word is trivial or not. If it were possible to set a second procedure going which said NO if the word we give it is not equal to the group identity then we could set both procedures going and wait for the one to finish. However, since this problem is not recursive, there is no procedure which will say NO. Let us return to the history of the word problem for groups.

In 1938 Church proposed that the word problem for groups should be proved insoluble using the new rigorous definitions of computable. In 1946 and 1947 the first breakthrough was made by Emil Post. Now Post had been unbelievably unlucky. He had produced most of the ideas of Gödel and Church before they did, but his work had not been considered publishable. It is often the case that when someone comes up with a really revolutionary idea, the world is not ready for it and this seems to have been the case here. Post continued, despite the blow of failing to get his work published, and came up with the idea of aTuring machine at about the same time as Turing. However Turing's work was quickly published before Post who, given his bad experience with publishing, was not rushing into print. When Post did publish, five years after Turing, he gave what is today called the Post Correspondence Problem.

Post Correspondence Problem: Given an alphabet A = { a₁ , a₂ , ...., a_n} and an infinite set S of pairs of words ( u_i , v_i), where u_i , v_i are words in A. Determine if any pair in S has the two components equal.

Post proved that the Post Correspondence Problem was insoluble. Church saw Post's paper and suggested to him that he try to prove that the word problem for semigroups was insoluble. He succeeded, and published a proof that the word problem for semigroups was insoluble in 1947. However, again Post was unlucky - A A Markov published a proof of the same result in the same year having worked independently of Post.

If Post's semigroup had been embeddable in a group then the word problem for groups would have been solved in the negative at the same time. However, this was not the case and the word problem for groups remained open. Turing learnt about the word problem for groups after reading Post's paper. He thought about the problem for ten days, then declared he had solved it. He arranged to give a seminar describing the proof, but just before the seminar he found an error. He was left with something, however, he had proved that the word problem is insoluble for cancellative semigroups.

In 1954 Bill Boone published a paper in which he defined the quasi-Magnus problem and proved it insoluble.

Quasi-Magnus problem: Let a group G be given by a finite presentation < A | R > . Decide whether a word w in the alphabet A is equal, as an element of G, to a word u in A whose exponents are all positive (i.e. no inverses of generators appear in the word u).

Boone was a doctoral student of Church, and this result appeared in Boone's Ph.D. dissertation of 1952. By 1956 Boone had proved that the word problem for groups was insoluble. However, Petr Sergeevich Novikov had been working on the problem and announced in 1952 that he had a proof of the insolubility of the word problem for groups. Few believed him for although he was a well known mathematician he was 51 years of age and had published mostly in mathematical physics up to that time. Dehn did not live long enough to see his fundamental question solved. He died in 1952 shortly before Novikov announced his results. At that stage, however, Novikov did not publish a proof so Boone was happy to continue with his own eventually successful attempts.

However, a different approach was to prove highly significant. Graham Higman, Bernhard Neumann and Hanna Neumann introduced what is now called an HNN extension in 1949. Higman made a major breakthrough using HNN extensions. First a definition:

A finitely generated group G is recursively presented if it has a presentation < A | R > where R is a recursively enumerable set of words.

Higman proved the Higman embedding theorem in 1961:

Higman embedding theorem: A finitely generated group H can be embedded in a finitely presented group if and only if H is recursively presented.

This leads to a very different proof of the insolubility of the word problem. Take H(S) = < a, b, c, d | a^-ibaⁱ = c^-idcⁱ, i ∈ S > where S is a recursively enumerable set which is not recursive. Then H(S) is the free product of the free group < a, b > with the free group < c, d > with the subgroups < a^-ibaⁱ | i in S > and <c^-idcⁱ | i ∈ S > amalgamated. Then a^-ibaⁱc^-id^-1cⁱ = 1 in H(S) if and only if i is in S. But this is not decidable. Hence H(S) has insoluble word problem. Finally use Higman embedding to embed H(S) in a finitely presented groups G(S) to obtain a finitely presented group with an insoluble word problem.

We note that Higman also used his embedding theorem to prove that there exists a finitely presented group U such that given any finitely presented group G then G is isomorphic to subgroup of U.

Sergei Ivanovich Adian, a student of Petr Sergeevich Novikov, proved a whole range of decision problems in 1957 and 1958 based on the idea of a Markov property.

Markov Property: An abstract property P of finitely presented groups is a Markov property if there are two finitely presented groups G(+) and G(-) such that

(a) G(+) has property P

(b) if G(-) is embedded in a finitely presented group G, then G does not have property P.

For example 'finite' is a Markov property - take G(+) to be the cyclic group of order 2 and G(-) to be the infinite cyclic group.

A abstract property P of finitely presented groups is recursively recognisable if, given an arbitrary finite presentation, it is computable (with a Turing machine) whether or not the group with this presentation has the property P. In other words there is an algorithm to determine whether the group with a given presentation satisfies property P.

Adian proved the following theorem in 1957:

Theorem: 
If P is a Markov property of finitely presented groups, then P is not recursively recognisable.

This gives the following corollary:

Corollary: 
The following properties of finitely presented groups are not recursively recognisable, namely being

(i) the trivial group;
(ii) finite;
(iii) abelian;
(iv) nilpotent;
(v) soluble;
(vi) free;
(vii) torsion free;
(viii) residually finite;
(ix) having soluble word problem;
(x) simple.

We note that although given a finite group presentation we cannot recursively recognisable whether the group is simple, if we know that a given presentation defines a simple group then that group has soluble word problem.

One also obtains as a corollary to Adian's theorem that the isomorphism problem is insoluble, since one cannot determine whether a group is isomorphic to the trivial group.

In 1959 Gilbert Baumslag, Bill Boone and Bernhard Neumann proved the following theorem:

Theorem: 
There is a finite presented group G such that there is no algorithm to determine whether or not a word in the given generators represents

(i) an element of the centre of G;
(ii) an element which commutes with a given element;
(iii) an nth power, where n > 1 is fixed;
(iv) an element with finitely many conjugates;
(v) a commutator;
(vi) an element of finite order.

Finally let us note that Mihailova introduced the membership problem in 1958 and proved:

Theorem: 
Let F be a free group of rank 2 and let G be the direct product of F with itself. Then G has a subgroup L for which the membership problem is insoluble.

Miller, in 1971, took the study of G = F × F further proving that one cannot decide whether L = G. Also he proved that G has a subgroup L with insoluble conjugacy problem. This gives groups with soluble word problem but insoluble conjugacy problem