The Word Problem in Universal Algebra
In algebra, one often studies infinite algebras which are generated (under the finitary operations of the algebra) by finitely many elements. In this case, the elements of the algebra have a natural system of finite encoding as expressions in terms of the generators and operations. The word problem here is thus to determine, given two such expressions, whether they represent the same element of the algebra.
Roughly speaking, the word problem in an algebra is: given a set of identities E (an equational theory), and two terms x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions?. The act of discovering such equivalences is known as unification. The process of unification requires discovering substitutions to demonstrate equality. Substitutions may be ordered into a partial order, thus, unification is the act of finding a join on a lattice. In this sense, the word problem on a lattice has a solution, namely, the set of all equivalent words is the free lattice.
One of the most deeply studied cases of the word problem is in the theory of semigroups and groups. There are many groups for which the word problem is not decidable, in that there is no Turing machine that can determine the equivalence of any two words in a finite time.
The word problem on ground terms is not decidable.
The word problem on free Heyting algebras is difficult. The only known results are that the free Heyting algebra on one generator is infinite, and that the free complete Heyting algebra on one generator exists (and has one more element than the free Heyting algebra).
Read more about this topic: Word Problem (mathematics)
Famous quotes containing the words the word, word, problem, universal and/or algebra:
“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)
“The word “conservative” is used by the BBC as a portmanteau word of abuse for anyone whose views differ from the insufferable, smug, sanctimonious, naive, guilt-ridden, wet, pink orthodoxy of that sunset home of the third-rate minds of that third-rate decade, the nineteen-sixties.”
—Norman Tebbit (b. 1931)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)
“The universal social pressure upon women to be all alike, and do all the same things, and to be content with identical restrictions, has resulted not only in terrible suffering in the lives of exceptional women, but also in the loss of unmeasured feminine values in special gifts. The Drama of the Woman of Genius has too often been a tragedy of misshapen and perverted power.”
—Anna Garlin Spencer (1851–1931)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)