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:
“All roads are blocked to a philosophy which reduces everything to the word “no.” To “no” there is only one answer and that is “yes.” Nihilism has no substance. There is no such thing as nothingness, and zero does not exist. Everything is something. Nothing is nothing. Man lives more by affirmation than by bread.”
—Victor Hugo (1802–1885)
“I used to be a discipline problem, which caused me embarrassment until I realized that being a discipline problem in a racist society is sometimes an honor.”
—Ishmael Reed (b. 1938)