Word Problem (mathematics)
In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions? While answering this question may not seem hard, the remarkable (and deep) result that emerges, in many important cases, is that the problem is undecidable.
Many, if not most all, undecidable problems in mathematics can be posed as word problems; see the list of undecidable problems for many examples.
Read more about Word Problem (mathematics): Background and Motivation, The Word Problem in Combinatorial Calculus, The Word Problem in Universal Algebra, See Also
Famous quotes containing the words word and/or problem:
“Fatalism, whose solving word in all crises of behavior is “All striving is vain,” will never reign supreme, for the impulse to take life strivingly is indestructible in the race. Moral creeds which speak to that impulse will be widely successful in spite of inconsistency, vagueness, and shadowy determination of expectancy. Man needs a rule for his will, and will invent one if one be not given him.”
—William James (1842–1910)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)