A word problem is a kind of math problem that supposedly tests how well a person can apply mathematics to real-life situations. A word problem in grammar school might be:

  1. Train A leaves from Austin at 1:00, travelling at 60 miles per hour. Train B leaves from Houston at 1:30 and is travelling at 70 miles per hour. If Austin is 160 miles away from Houston, at what time will the two trains meet? (answer below)

Word problems often give students fits because of the way that math is taught in school (see: rote memorization.) The problem with word problems is that they inevitably rely on assumptions and which may or may not be obvious.

Answer: assuming instant acceleration, the answer is 2:30.

Mathematics (specifically, (computational) group theory and/or mathematical logic) actually has something called the word problem. As any frustrated high school student will testify, the word problem is unsolvable in a very real sense.

The word problem:

Let G=<Γ|R> be a finitely presented group (see generators and relations for groups to understand what this is). Since Γ generates G, any element of G can be represented as

g1k1 g2k2 ... gnkn
where all giΓ and ki≠0 is an integer.

We still haven't mentioned the set of relations R. What R does is make elements of G have more than one representation. For instance, if G=<a,b|ab=ba> is the free abelian group with 2 generators, then ab=ba=a17b-3a2a-18b4=...

The word problem is this: given Γ, R, and 2 words, determine if the 2 words are equivalent, i.e. whether they correspond to the same element of G.

The word problem is known to be recursively enumerable but not recursive: there's a (trivial) algorithm that will halts iff the 2 words are equivalent, but there's no algorithm to tell you (in the general case!) whether or not the 2 words are equivalent.

Log in or register to write something here or to contact authors.