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

g_{1}^{k1}
g_{2}^{k2}
...
g_{n}^{kn}

where all g

_{i}∈Γ and k

_{i}≠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=a^{17}b^{-3}a^{2}a^{-18}b^{4}=...

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.