TITLE: Douglas Hofstadter on Questions, Proofs, and Passion
AUTHOR: Eugene Wallingford
DATE: March 07, 2012 5:35 PM
In the spring of my sophomore year in college, I was
chatting with the head of the Honors College at my alma
mater. His son, a fellow CS major, had recently read
what he considered a must-read book for every thinking
computer scientist. I went over to library and checked
it out in hardcopy. I thumbed through it, and it was
love at first sight. So I bought the paperback and
spent my summer studying it, line by line.
Gödel, Escher, Bach
seemed to embody everything that excited me about computer
science and artificial intelligence. It made, used, and
deconstructed analogies. It talked about programming
languages, and computer programs as models. Though I
allowed myself to be seduced in grad school by other kinds
of AI, I never felt completely satisfied. My mind and heart
have never really left go of the feeling I had that summer.
Last night, I had the pleasure of seeing Douglas Hofstadter
give the annual Hari Shankar Memorial Lecture here. This
lecture series celebrates the beauty of mathematics and
its accessibility to everyone. Hofstadter said that he was
happy to honored to be asked to give such a public lecture,
speaking primarily to non-mathematicians. Math is real; it
is in the world. It's important, he said, to talk about it
in ways that are accessible to all. His lecture would
share the beauty of
Gödel's Incompleteness Theorem.
Rather than give a dry lecture, he told the story as his
story, putting the important issues and questions into the
context of his own life in math.
As a 14-year-old, he discovered a paperback copy of
in a used bookstore. His father mentioned that one of the
authors, Ernest Nagel, was one of his teachers and friends.
Douglas was immediately fascinated. Gödel used a tool
(mathematics) to study itself. It was "a strange loop".
As a child, he figured out that two twos is four. The natural
next question is, "What is three threes?" But this left him
dissatisfied, because two was still lurking in the question.
What is "three three threes"? It wasn't even clear to him
what that might mean.
But he was asking questions about patterns and and seeking
answers. He was on his way to being a mathematician. How
did he find answers? He understood science to be about
experiments, so he looked for answers by examining a whole
bunch of cases, until he had seen enough to convince himself
that a claim was true.
He did not know yet what a proof was. There are, of course,
many different senses of proof, including informal arguments
and geometric demonstrations. Mathematicians use these, but
they are not what they mean by 'proof'.
So he explored problems and tried to find answers, and
eventually he tried to prove his answers right. He became
passionate about math. He was excited by every new discovery.
(Pi!) In retrospect, his excitement does not surprise him.
It took mathematicians hundreds of years to create and
discover these new ideas. When he learned about them after
the fact, they look like magic.
Hofstadter played with numbers. Squares. Triangular numbers.
Primes. He noticed that 2^3 and 3^2 adjacent to one another
and wondered if any other powers were adjacent.
Mathematicians have faith that there is an answer to questions
like that. It may be 'yes', it may be 'no', but there's an
answer. He said this belief is so integral to the mindset
that he calls this the Mathematician's Credo:
If something is true, it has a proof, and if something has a
proof, then it is true.
As an example, he wrote the beginning of the Fibonacci
series on the chalk board: 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233. The list contains some powers of integers:
1, 8, and 144. Are there more squares? Are there more
powers? Are there infinitely many? How often do they
appear? It turns out that someone recently discovered that
there are no more integer powers in the list. A mathematician
may be surprised that this is true, but she would not be
surprised that, if it is true, there is a proof of it.
Then he gave an open question as an example. Consider this
a familiar problem:
Rule 1 takes us from 1 to 2. Rule 1 takes us to 4. Rule 2
takes us to 1. We've already been there, so that's not very
interesting. But Rule 1 takes us to 8.... And so on.
Hofstadter called the numbers we visited C-numbers.
He then asked a question: Where can we go using these rules?
Can we visit every integer? Which numbers are C-numbers?
Are all integers C-numbers?
The answer is, we don't know. People have used computers to
test all the integers up to a very large number (20 x 2^58)
and found that we can reach every one of them from 1. So
many people conjecture strongly that all integers are
C-numbers. But we don't have a proof, so the purist
mathematician will say only, "We don't know".
At this point in the talk, my mind wanders....
(Wonders?) It would be fun to write a program to answer,
"Is n a C-number?" in
the language for which my students this semester are writing
a compiler. That would make a nice test program. Flair is
a subset of Pascal without any data structures, so there is
an added challenge... A danger of teaching a compilers
course -- any course, really -- is that I would rather write
programs than do almost anything else in the world.
One could ask the same question of the Fibonacci series: Is
every number a Fibonacci number? It is relatively easy to
answer this question with 'no'. The sequence grows larger
in each new entry, so once you skip any number, you know
it's not in the list. C-numbers are tougher. They grow
and shrink. For any given number n, we can search
the tree of values until we find it. But there is no proof
for all n.
As one last bit of preparation, Hofstadter gave an informal
proof of the statement, "There are an infinite number of
prime numbers." The key is that his argument used one
assumption (there are a finite number of primes) to
destroy a necessary consequence of the same
From there, Hofstadter told a compact, relatively simple
Tarski's undefinability theorem
and, at the end, made the bridge to Gödel's theorem.
I won't tell that story here, for a couple of reasons.
First, this entry is already quite long. Second,
Hofstadter himself has already told this story better than
I ever could, in Gödel, Escher, Bach. You
really should read it there.
This story gave him a way to tell us about the importance
of the proof: it drives a wedge between truth and provability.
This undermines the Mathematician's Credo. It also allowed
him to demonstrate his fascination with Gödel's
Proof so many years ago: it uses mathematical logic to
say something interesting, powerful, and surprising about
mathematical logic itself.
Hofstadter opened the floor to questions. An emeritus CS
professor asked his opinion of computer proofs, such as
the famous 1976 proof of the
four color theorem.
That proof depends on a large number of special cases and
requires hundreds of pages of analysis. At first, Hofstadter
said he doesn't have much of an opinion. Of course, such
proofs require new elements of trust, such as trust that the
program is correct and trust that the computer is functioning
correctly. He is okay with that. But then he said that he
finds such proofs to be unsatisfying. Invariably,
they are a form of brute force, and that violates the spirit
of mathematics that excites him. In the end, these proofs
do not help him to understand why something isn true, and
that is the whole point of exploring: to understand why.
This answer struck a chord in me. There are whole swaths
of artificial intelligence that make me feel the same way.
For example, many of my students are fascinated by neural
networks. Sure, it's exciting any time you can build a
system that solves a problem you care about. (Look ma,
no hands!) But these programs are unsatisfying because
they don't give me any insight into the nature of the
problem, or into how humans solve the problem. If I ask
a neural network, "Why did you produce this output for
this input?", I can't expect an answer at a conceptual
level. A vector of weights leaves me cold.
To close the evening, Hofstadter responded to a final
question about the incompleteness theorem. He summarized
Gödel's result in this way: Every interesting formal
system says true things, but it does not say all true
things. He also said that Tarski's result is surprising,
but in a way comforting. If an oracle for T-numbers
existed, then mathematics would be over. And that would
As expected, I enjoyed the evening greatly. Having read
GEB and taken plenty of CS theory courses, I
already knew the proofs themselves, so the technical details
weren't a big deal. What really highlighted the talk for me
was hearing Hofstadter talk about his passions: where they
came from, how he has pursued them, and how these questions
and answers continue to excite him as they do. Listening
to an accomplished person tell stories that make connections
to their lives always makes me happy.
We in computer science need to do more of what people like
Hofstadter do: talk about the beautiful ideas of our discipline
to as many people as we can, in way that is accessible to all.
We need a Sagan or a Hofstadter to
share the beauty.
PHOTOGRAPH 1: a photograph of the cover of my copy of
Gödel, Escher, Bach.
PHOTOGRAPH 2: Douglas Hofstadter in Bologna, Italy, 2002.
- Rule 1: n → 2n
- Rule 2: 3n+1 → n
- Start with 1.