viruses is equivalent to the halting problem; no such program can be
written.^7What Is, or Might Be, Undecidable
I’m not sure what the future holds in this area, but I am sure of what
mathematicians would like to see. Just as stock market traders would
like to hear a bell ring at a market bottom, mathematicians would like a
quick way to determine whether a problem on which they are working is
undecidable. Regrettably, Gödel’s theorem does not come with an algo-
rithm that tells them precisely which propositions are undecidable. The
example Gödel constructed of an undecidable proposition is mathemati-
cally useless; it involves formulas whose Gödel number satisfies that
formula. The Gödel number of a formula is referenced in the footnotes,
but there is not a single mathematically important formula in arithmetic
that incorporates the Gödel number of that formula. What mathemati-
cians would really like is a tag attached to such outstanding problems as
the Goldbach conjecture, which says either, “Don’t bother—this proposi-
tion is undecidable,” or “Keep at it, you might get somewhere.” It seems
highly unlikely that anyone will ever find a way to tag all propositions;
the history of the field (think of the unsolvability of the halting problem)
is that it is far more likely to be shown that no such way to tag proposi-
tions exists.
However, some extremely interesting problems have been shown to be
undecidable. Unfortunately, there have been relatively few—nowhere
near enough to reach some sort of general conclusion as to the type of prob-
lem that is undecidable. By far the most important was Cohen’s dem-
onstration that the continuum hypothesis was undecidable within
Zermelo-Fraenkel set theory (with the axiom of choice) if that theory
were consistent. There have been at least two other interesting problems
that have been shown to be undecidable—and one is related to a cur-
rently unsolved problem that is intriguing and easy to understand.
The Word Problem—No, We’re Not Discussing Scrabble
In chapter 5, the group of symmetries of an equilateral triangle was
found to consist of combinations of two basic motions: a 120-degree
counterclockwise rotation, labeled R, and a move in which the top vertex
is unchanged but the bottom two are interchanged, called a f lip and la-
beled F.Even Logic Has Limits 127