TITLE: Douglas Hofstadter on Questions, Proofs, and Passion AUTHOR: Eugene Wallingford DATE: March 07, 2012 5:35 PM DESC: ----- BODY: 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 Gödel's Proof 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 variation of a familiar problem:

Rule 1: n → 2n
Rule 2: 3n+1 → n
Start with 1.

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 Flair, 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 (p₁*p₂*...*p_k+1 is prime). From there, Hofstadter told a compact, relatively simple version of 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 be depressing. 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. Source: Wikimedia Commons. -----