erators that are subject to a number of relationships, as in the above ex-
ample. The word problem for such a group is to find an algorithm that
when given two words (such as RFR^2 FRF and RFR), will decide whether
they represent the same element of the group. For some groups, this can
be done, but in 1955, Novikov gave an example of a group for which the
word problem was undecidable.^8 The Novikov family has made great con-
tributions to mathematics. Petr Novikov, of word problem fame, had two
sons: Andrei was a distinguished mathematician, and Serge was a very
distinguished mathematician, winning a Fields Medal in 1970.
Incidentally, when Rubik’s Cube first appeared, lots of papers on solu-
tions for it appeared in journals devoted to group theory^9 —for Rubik’s
Cube involves a group of symmetries with generators (rotations around
the various axes) subject to relationships.
Do You Always Get There from Here?
The last of the three problems that has been shown to be undecidable is
known as Goodstein’s theorem. To get a feel for this problem, here’s a
currently unsolved problem, the Collatz conjecture, that has some aspects
in common with it. Many mathematicians feel it may be undecidable, but
it is easy to understand. Paul Erdos, the prolific and peripatetic mathema-
tician whose lifestyle consisted of visiting various universities for short
periods, used to offer monetary prizes for the solutions to interesting
problems. Because Erdos was basically supported by the mathematical
community, living with mathematicians whose universities he visited,
the money he collected for honoraria was used to fund these prizes. They
ranged from $10 up; he offered $500 for a proof (one way or the other) of
the Collatz conjecture. Of the Collatz conjecture, he said “Mathematics is
not yet ready for such problems.”^10
When you first see this problem, it looks like something a nine-year-old
kid dreamed up while doodling with numbers. Pick a number. If it is
even, divide by 2; if it is odd, multiply by 3 and add 1. Keep doing this.
We’ll do an example in which 7 is used as the starting number.
7, 2 2 [ 3 7 1],11[ 22/2],34,17,52,26,13,40,20,10,5,16,8,4,2,1It took a while, but we finally hit the number 1. Here’s the unsolved
problem: Do you always eventually hit the number 1 no matter where you
start? If you can prove it, one way or the other, I think that the money is
part of Erdos’s estate; he died in 1996. The New York Times did a front-
page article on him after he died. He was once humorously described by
his colleague Alfréd Rényi, who said, “A mathematician is a machine for
Even Logic Has Limits 129