Word (group Theory) - The Word Problem

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:

    “We have the words in our pockets,
    obscure directions. The old ones
    have taken away the light of their presence....”
    —Denise Levertov (b. 1923)

    “Under the one word “house” are included the schoolhouse, the almshouse, the jail, the tavern, the dwellinghouse; and the meanest shed or cave in which men live contains elements of all these. But nowhere on the earth stands the entire and perfect house.”
    —Henry David Thoreau (1817–1862)

    “... your problem is your role models were models.”
    —Jane Wagner (b. 1935)