Why is the word problem hard?
This post is about the word problem. When mathematicians talk about the word problem" we're not talking about elementary math problems expressed in prose, such as If Johnny has three apples, ...."
The word problem in algebra is to decide whether two strings of symbols are equivalent given a set of algebraic rules. I go into a longer description here.
I know that the word problem is hard, but I hadn't given much thought to why it is hard. It has always seemed more like a warning sign than a topic to look into.
Why don't we just ...?"
That won't work because ... is equivalent to the word problem."
In logic terminology, the word problem is undecidable. There can be no algorithm to solve the word problem in general, though there are algorithms for special cases.
So why is the word problem undecidable? As with most (all?) things that have been shown to be undecidable, the word problem is undecidable because the halting problem is undecidable. If there were an algorithm that could solve the word problem in general, you could use it to solve the halting problem. The halting problem is to write a program that can determine whether another arbitrary program will always terminate, and it can be shown that no such program can exist.
The impulse for writing this post came from stumbling across Keith Conrad's expository article Why word problems are hard. His article goes into some of the algebraic background of the problem-free groups, (in)finitely generated groups, etc.-and gives some flavor for why the word problem is harder than it looks. The bottom line is that the word problem is hard because the halting problem is hard, but Conrad's article gives you a little more of an idea what's going on that just citing a logic theorem.
I still don't have a cocktail-party answer for why the word problem is hard. Suppose a bright high school student who had heard of the word problem were at a cocktail party (drinking a Coke, of course) and asked why the word problem is hard. Suppose also that this student had not heard of the halting problem. Would the simplest explanation be to start by explaining the halting problem?
Suppose we change the setting a bit. You're teaching a group theory course and the students know about groups and generators, but not about the halting problem, how might you give them a feel for why the word problem is hard? You might ask them to read Keith Conrad's paper and point out that it shows that simpler problems than the word problem are harder than they seem at first.
Related posts- The word problem
- Probability of commuting
- Groups of semiprime order
- Normal subgroup of" is not transitive