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 the word, word and/or problem:
“Powerful, yes, that is the word that I constantly rolled on my tongue; I dreamed of absolute power, the kind that forces to kneel, that forces the enemy to capitulate, finally converting him, and the more the enemy is blind, cruel, sure of himself, buried in his conviction, the more his admission proclaims the royalty of he who has brought on his defeat.”
—Albert Camus (1913–1960)
“And then this word was heard: “Trinch.””
—François Rabelais (1494–1553)
“In the nineteenth century the problem was that God is dead; in the twentieth century the problem is that man is dead.”
—Erich Fromm (1900–1980)