History
Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, (Dehn 1911), together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2, (Dehn 1912). Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.
It was shown by Pyotr Novikov in 1955 that there exists a finitely generated (in fact, a finitely presented) group G such that the word problem for G is undecidable. It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by William Boone in 1958.
The word problem was one of the first examples of an unsolvable problem to be found not in mathematical logic or the theory of algorithms, but in one of the central branches of classical mathematics, algebra. As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well.
It is important to realize that the word problem is in fact solvable for many groups G. For example, polycyclic groups have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the Todd–Coxeter algorithm and the Knuth–Bendix completion algorithm. On the other hand the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has unsolvable word problem. For instance Dehn's algorithm does not solve the word problem for the fundamental group of the torus. However this group is the direct product of two infinite cyclic groups and so has solvable word problem.
Read more about this topic: Word Problem For Groups
Famous quotes containing the word history:
“It may be well to remember that the highest level of moral aspiration recorded in history was reached by a few ancient Jews—Micah, Isaiah, and the rest—who took no count whatever of what might not happen to them after death. It is not obvious to me why the same point should not by and by be reached by the Gentiles.”
—Thomas Henry Huxley (1825–95)
“The history of literature—take the net result of Tiraboshi, Warton, or Schlegel,—is a sum of a very few ideas, and of very few original tales,—all the rest being variation of these.”
—Ralph Waldo Emerson (1803–1882)
“The foregoing generations beheld God and nature face to face; we, through their eyes. Why should not we also enjoy an original relation to the universe? Why should not we have a poetry and philosophy of insight and not of tradition, and a religion by revelation to us, and not the history of theirs?”
—Ralph Waldo Emerson (1803–1882)