Return to the home page for Patrick Kellogg

When Douglas Hofstadter's book "Godel, Escher, Bach: An Eternal Golden Braid" won the Pulitzer Prize in 1980, it was recognized by many readers as an unusual, outstanding book. Other science books have won the Pulitzer before, like Carl Sagan's "Dragons of Eden" or Tracy Kidder's "The Soul of a New Machine". So, having a technical computer science book with in the Non-Fiction category was nothing new. However, there has never been a Pulitzer prize-winning book before (or since) that has combined artificial intelligence, classical music, Buddhism, "Alice in Wonderland", human genetics, and Aesop's fables. And that is just in the first 50 pages of the 777 page book!

To get a feel of "Godel, Escher, Bach" (GEB), here is an excerpt of one of the "dialogues" in the book:

Contracrostipunctus

(Achilles has come to visit his friend and jogging companion, the Tortoise, at his home.)

Achilles: Heavens, you certainly have an admirable boomerang collection!

Tortoise: Oh, pshaw. No better than that of any other Tortoise. And now, would you like to step into the parlor?

Achilles: Fine. (Walks to the corner of the room.) I see you also have a large collection of records. What sort of music do you enjoy?

Tortoise: Sebastian Bach isn't so bad, in my opinion. But these days, I must say, I am developing more of an interest in a rather specialized sort of music.

Achilles: Tell me, what kind of music is that?

Tortoise: A type of music which you are most unlikely to have heard of. I call it "music to break phonographs by".

Achilles: Tell me about your weird music.

Tortoise: Well, you see, the Crab came over to visit one day, (and he had a) record called "I Cannot Be Played on Record Player 1" (and) he put it on. But unfortunately, after only a few notes, the record player began vibrating rather severely, and then with a loud "pop", broke into a large number of fairly small pieces, scattered all about the room... (Hofstadter 1979, pp. 75-76)

Even more odd, GEB alternates these dialogues with long pedantic chapters with titles like "Typographical Number Theory" or "On Formally Undecidable Propositions of TNT and Related Systems." Either you love the book's humorous-but-scholarly tone, or you will hate it. In any case, 1999 marks the 20th anniversary of the publication of "Godel, Escher, Bach", and all computer science students should try to understand why it is an important book in the AI canon.

Hoftstadter makes many points in his book (almost too many), but the main theme is a comparison of three artists: Kurt Godel, M.C. Escher, and Johann Sebastian Bach. Escher, you may know, was a 20th century artist who specialized in an exact form of modern art that was rich in perspective and three dimensional space. One of his favorite tricks was to do "tessellations" or tilings of a shape, and then slowly transform it into another shape as the drawing progressed. Hofstadter makes the analogy that Bach did the same thing in his music - transforming and rotating a melody line until it no longer resembled the original song. Bach often wrote musical "fugues", which wrapped the instruments around each other much like the children's song "Row, Row, Row Your Boat" and other "rounds".

But how could those two artists be similar to Kurt Godel, a 20th century mathematician? Well, in 1930, Kurt Godel discovered his Completeness Theorem, which "showed that, for any first-order logic, any sentence that is entailed by another set of sentences can be proved from that set". (Russell and Norvig p. 277). In other words, mathematical statements can be "built up" from other statements, similar to the way that (A < B) and (B < C) implies that (A < C). This was good news for mathematicians who wanted to create a "formal logic" that encapsulated all of the rules of mathematics in a single set of statements. For example, given the basic understanding of geometry, a math computer could re-discover the principles of calculus, linear algebra, or differential equations. We could just leave the computer running all night, and let it invent whole new realms of science!

However, the flip side of Godel's argument is an Incompleteness Theorem (GIT) that says "all consistent axiomatic formulations of number theory include undecidable propositions". (Hofstadter 1979, p. 17) This statement says that even if our hypothetical math computer was running for millions of years, there is an infinite set of statements that it would never discover. Worse, even if given a statement, the math computer couldn't even decide if it was true or false! GIT is related to Alan Turing's "halting problem", since both rely on infinite loops and recursion as a form of proof. So, Kurt Godel is a lot like M.C. Escher, and Bach, because he also used "circles within circles" to make his fundamental discoveries. Thus, the title of Hofstadter's book.

Today, the idea of a unified formal logic has fallen out of favor. Few computer scientists are currently trying to build up intricate rules using smaller statements. Perhaps they are worried that according to GIT, they will "leave something out", and some fundamental part of intelligence will be missing. Several AI critics, including Hubert Dreyfus and J.R. Lucas, said that any rule-based computer will fail to be intelligent, because Godel prove that there will always be thoughts that it can't think about or comprehend.

On the other hand, Marvin Misky complains about the lack of "bottom-up" approaches to AI:

"In the early 1980s it became clear (especially to Douglas Lenat, who was conceiving of his CYC project) that to make much further progress we were going to need a conceptual database adequate for understanding the most unusual things that happen in the world^E Unfortunately, in my view, most AI researchers interpreted the scaling-up obstacles in a different way^Eall those years slipped by, with no other project than CYC underway" (Minsky, p. 27)
Maybe Misky can find courage in the recent work of Rodney Brooks at MIT, or Mike Eisenberg's "cricket" project here at the University of Colorado. Using some new ideas about artificial life and genetic programming, a new breed of researchers is trying to start from small, basic parts. Perhaps some of the ideas of formal logic will become popular again, GIT or not.

The idea of using Godel to try and invalidate artificial intelligence has also lost its merit in the last decade. Herbert A. Simon says, "Philosophical speculation abut what computers can't do, buttressed by logical arguments about Godel's proof and intentions, are reminiscent of the philosophical farmer who, when confronted for the first time with a giraffe, declared confidently that 'there ain't no such animal'." (Simon, 1995). I feel that Artificial Intelligence seems to have moved on from theory to practice. Perhaps, back in the early 60's, researchers were hindered by the lack of processing power, and so confined their AI work to theoretical discussions and speculation. Today, I think that researchers are just trying to see what works, and now have the ability to throw computing cycles and memory and the problem.

Hofstadter, too, seems to have moved on. His latest books make little mention of Kurt Godel, Escher, or Bach. However, he is still interested in the fundamentals of AI: game theory, searching algorithms, recusrsion, and human cognition. In his latest book, "Le Ton beau de Marot", he discusses the problem of computer translation - in his case, trying to translate the works of a French poet who used so many puns and jokes that his poems don't make sense when literally translated to English.

Of course, there is much more to "Godel, Escher, Bach" than I have described, including an interesting analysis of genetic engineering, and the four bases that make up human DNA (adenine, guanine, cytosine, and thymine - or AGCT). And, naturally, Hofstadter keeps using odd stories, bizarre creatures, puns, and in-jokes to make his point. For example, in several places, he makes up anagrams using the words AGCT, BACH, "crab" and "John Cage". So, in the spirit of the anniversary of "Godel, Escher, Bach", I'll finish this article with a mixed-up sentence of my own: "I BEG you to GET the GIBE of GEB and GIT." Got it?

Bibliography

Dreyfus, Hubert L. "What Computers Still Can't Do: A Critique of Artificial Intelligence" MIT Press ISBN 0262540673, 1992. Gero, John S. Sudweeks, Fay "Artificial Intelligence in Design '94" Kluwer Academic ISBN 0-7923-2995-5, July 1004.
Hofstadter, Douglas "Gvdel, Escher, Bach: An Eternal Golden Braid" Vintage Books ISBN 0-394-74502-7, April, 1979.
Hofstadter, Douglas "Metamagical Themas: Questing for the Essence of Mind and Pattern" Vintage Books ISBN 0-394-74502-7, April1979.
Hofstadter, Douglas "Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought" Basic Books ISBN 0-465-05154-5, 1995.
Hofstadter, Douglas "Le Ton beau de Marot: In Praise of the Music of Language" Basic Books ISBN 0-465-08643-8, 1997.
Minsky, Marvin "A Conversation With Marvin Minsky" Communications of the ACM magazine article, July 1994, Vol. 37, No. 7 pp. 23-29.
Russell, Stuart J. and Peter Norvig "Artificial Intelligence: A Modern Approach" Prentice Hall ISBN 0-13-103805-2, 1995.
Simon, Herbert A. "AI Is an Empirical Science" The World & I magazine article, July 1995 pp. 326-327.

Links

http://www.student.nada.kth.se/~d90-mst/geb/ Large list of GEB Links page by Merten Stenius
http://www.barnesandnoble.com/subjects/science/review1.asp Review of "Godel, Escher, Bach" by Barnes and Noble
http://www.nada.kth.se/~kai/lectures/geb.html A lecture by Kai-Mikael Jaa-Aro on a chapter of GEB. This excerpt gives a good idea of the tone of the book
http://www.forum2.org/tal/books/geb.html A long review by Tal Cohen
http://pages.prognet.com/jeremyc/html/hofstadter.html Another review
http://www.arch.su.edu.au/AID94/keynote.html The Third International Conference on Artificial Intelligence in Design where Douglas Hofstadter was the keynote speaker
http://www.cs.indiana.edu/dept/faclist/dughof.html Douglas Hofstadter's homepage at the University of Indiana