The Word Problem
Given a presentation for a group G, the word problem is the algorithmic problem of deciding, given as input two words in S, whether they represent the same element of G. The word problem is one of three algorithmic problems for groups proposed by Max Dehn in 1911. It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable.(Novikov 1955)
Read more about this topic: Word (group Theory)
Famous quotes containing the words word and/or problem:
“I have been reporting club meetings for four years and I am tired of hearing reviews of the books I was brought up on. I am tired of amateur performances at occasions announced to be for purposes either of enjoyment or improvement. I am tired of suffering under the pretense of acquiring culture. I am tired of hearing the word “culture” used so wantonly. I am tired of essays that let no guilty author escape quotation.”
—Josephine Woodward, U.S. author. As quoted in Everyone Was Brave, ch. 3, by William L. O’Neill (1969)
“The general public is easy. You don’t have to answer to anyone; and as long as you follow the rules of your profession, you needn’t worry about the consequences. But the problem with the powerful and rich is that when they are sick, they really want their doctors to cure them.”
—Molière [Jean Baptiste Poquelin] (1622–1673)