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:
“Where are now the warring kings,
Word be-mockers? By the Rood
Where are now the warring kings?
An idle word is now their glory,
By the stammering schoolboy said....”
—William Butler Yeats (1865–1939)
“The disesteem into which moralists have fallen is due at bottom to their failure to see that in an age like this one the function of the moralist is not to exhort men to be good but to elucidate what the good is. The problem of sanctions is secondary.”
—Walter Lippmann (1889–1974)