Initially, Gödel, Escher, Bach comes across as a perplexingly well-regarded conspiracy theory text. But reading on, you come to see the magic: all of the conspiracies are actually true. Gödel numbering actually is just like RNA translation, and recursive transition networks really are similar to renormalization of elementary particles. Who knew? GEB author Douglas Hofstadter did, and he wrote a 700-page exploration of the ideas behind Gödel’s incompleteness theorem so that you could too.
GEB has two parts. Part I is an exposition of many interesting and deeply related ideas: formal systems like math and physics acquire meaning by modeling the world; recursion gives these systems power but also enables self-reference; and self-reference ultimately poses a serious problem for these systems. These ideas build to the statement and proof of Godel’s Incompleteness Theorem. Part II, roughly speaking, claims that the ideas of part I have something to do with artificial intelligence and the nature of consciousness.
This “book review” is really an in-depth explainer of the key ideas in GEB part I. That said, I’ll also briefly touch on part II at the end.
Before I start, let me tell you some things that won’t be in this review because you really can’t get them from anywhere but GEB itself.
First, this review will feature very few of Hofstadter’s actual words. The reason is simple: there’s way too many of them. In a previous draft of this review, I tried quoting out of GEB for a few simple things, but it would always turn out like “Hofstadter thinks humans are sometimes different than machines: [300 word quote that somehow essentially involves an analogy about how you think your wife wants you to turn off the TV, but she wants you to start a government-overthrowing revolution] (page 37).”
Second, this review will leave out the fascinating interconnections Hofstadter draws throughout the text. Gödel numbering really is just like RNA translation, I promise, but if you want to know why you’ll have to check out GEB from your local library, sorry.
And third, GEB is really idiosyncratic in a way no one can imitate. The book’s chapters are separated by entertaining Carrollian dialogues which illustrate key ideas that reappear later in the text, imitating the way themes reappear in Bach’s fugues. Hofstadter has an axe to grind with Zen Buddhism, and the first application of a formal logical system he develops in the text is to refute a Zen koan about grinding axes. He also enjoys taking pot shots at composer John Cage for basically no reason.
Overall, I think GEB is a really good book. In fact, I insist that it’s better than you expect even after taking my insistence into account. Eliezer Yudkowsky, on whom GEB was an early influence, once wrote:
Gödel, Escher, Bach by Douglas R. Hofstadter is the most awesome book that I have ever read. If there is one book that emphasizes the tragedy of Death, it is this book, because it’s terrible that so many people have died without reading it.
So, lest you die without learning why Gödel numbering is just like RNA translation familiarizing yourself with GEB, let’s get started. The basic object of study in GEB is what Hofstadter calls a formal system. A formal system consists of:
A collection of allowable characters out of which we can form strings (sequences of characters) A collection of strings called “axioms” A collection of rules, or “inference rules,” for changing some strings into others Huh? Let’s start with a simple, meaningless example called the MIU-system.
The MIU-system:
Allowable characters: M, I, and U. (So strings are things like M, UMM, MIMMIUM, UMIIMUMUUIMIM, etc.) Axioms: MI Rules: Rule I: given a string that ends in an I, you can add a U to the end. Example: from UMI, form UMIU Rule II: given a string of the form Mx where x consists of M’s, I’s, and U’s, you can form the string Mxx Example: from MIU, form MIUIU Rule III: given any string with III appearing somewhere inside, you may replace III with U Example: from MIIII, you can form MUI (by replacing the middle III with U). You can also form MIU (by replacing the ending III with U). Rule IV: given any string with UU appearing inside, you may delete UU Example: from MUUI, form MI
Let’s call a string a theorem if you can produce it from the axiom MI using the inference rules. For example, I claim that MUIIU is a theorem; in support of this I offer the following “proof”:
(1) MI (axiom) (2) MII (using rule II) (3) MIIII (using rule II) (4) MIIIIU (using rule I) (5) MUIU (using rule III) (6) MUIUUIU (using rule II) (7) MUIIU (using rule IV) There you have it – MUIIU is a theorem (as are all of the strings obtained along the way).
Hold on, axioms? theorems? Readers who’ve seen some mathematical logic might see where this is going.
The terminology is chosen to suggest the following. We imagine that the given rules are “rules of logical inference,” analogous to rules in classical logic like “given ‘P’ and ‘if P then Q,’ you may conclude ‘Q’.’” We imagine that the strings of our system are logical statements written in some formal language. And we imagine that the axioms are some logical statements that we assume to be true. So the “proof” above is akin to starting from a known axiom and using the rules of logical inference to deduce some desired theorem, sorta like a proof! Formal systems are a way of mechanistically codifying logical reasoning; one could easily write a program that starts from the axioms and recursively applies the inference rules to produce an ever-growing list of theorems. In fact, this is a very basic model for what automated theorem-provers like Coq do.
After introducing the MIU-system, Hofstadter offers the following puzzle, which I pass on to you:
Question: Is MU a theorem?
Try to figure it out yourself if you’d like, or read on to find the answer later.
In this example, the MIU-system doesn’t seem to reflect the structure of anything we would care about. In contrast, the next example-and-half do: they are meant to model multiplication of natural numbers.
The tq-system:
Allowable characters: t, q, - Axiom: -t-q- Rules: Rule I: given a string xtyqz where x,y,z are strings consisting of only hyphens, you can form x-tyqzy Rule II: given a string xtyqz where x,y,z are strings consisting of only hyphens, you can form xty-qzx Unlike the MIU-system, the tq-system comes with an interpretation which converts strings of the formal system into meaningful statements in some context. In this case, the context is “multiplications,” and the interpretation looks like
t ⇒ times q ⇒ equals
- ⇒ one – ⇒ two and so on. This interpretation turns the axiom -t-q- of the tq-system into the multiplication “one times one equals one” and the theorem –t—q—— (proved below) into the multiplication “two times three equals six.”
Proof: (1) -t-q- (axiom) (2) –t-q– (rule I) (3) –t–q—- (rule II) (4) –t—q—— (rule II)