Reflections on Gödel, Escher, Bach
Intro
Let me quote a popular Douban review from more than a decade ago. Reducing the book to this one line does mythologize it a little too much, but it still conveys something of its impact:
There are only two kinds of people in the world: those who have read this book, and those who have not.
To my mind, there are two main reasons readers find it so special:
- Its form is extraordinarily elegant and entertaining. Hofstadter deliberately borrows techniques from fugues and canons in the writing itself, producing something like logical poetry—or, if you prefer, wordplay.
- It crosses an astonishing range of disciplines, yet brings them into remarkable harmony. Starting from Gödel’s strangling of formal systems, it somehow finds a resonant chord with Bach’s orderly music and Escher’s subtle drawings. How could such unity not make you feel that you had caught a glimpse of the truth about the world?
Here is a brief thematic review. Much of the book consists of smaller, scattered ideas, though, so I will inevitably leave a great deal out.
Formal Systems and Gödel’s Incompleteness Theorems
- Gödel’s first incompleteness theorem: in any consistent formal system that contains the Peano axioms, one can construct true propositions that cannot be proved within the system. The system therefore cannot derive every true proposition: it is incomplete.
- Gödel’s second incompleteness theorem: any consistent formal system that contains the Peano axioms cannot prove its own consistency.
A formal system consists of specified symbols and rules. The most important example in this book is TNT, with expressions such as \(\forall a:(0+a)=a\).
A formal system has no meaning in itself. Form and meaning should be entirely separate. If we can assign meaning to a formal system, that is only because there is an isomorphism between the system’s behavior and the meaning we want to assign to it.
The most familiar example may be Euclidean geometry. Ideally, Euclid’s “points” and “lines” should be purely formal symbols, distinguished from points and lines in the real world. Euclidean geometry can describe reality because its points and lines are, in some sense, isomorphic to real ones. The formal system of geometry should therefore allow derivations independent of reality. Having the courage to pursue conclusions that seem to contradict reality leads us to drop the fifth postulate and arrive at Lobachevskian and Riemannian geometry.
A simpler example is the formal expression \(- - -q - p - -\). We can say that it means “three equals one plus two,” or “three minus one equals two,” or any other meaning for which we can imagine an isomorphism.
The Peano axioms were Peano’s attempt to formalize the natural numbers we had always been using through a handful of axioms. Like Euclid, he proposed five postulates. To distinguish the formal concepts from their familiar meanings, we can give them other names. The axioms then look roughly like this:
- The Monster is a creature.
- Every creature has a successor, which is also a creature.
- The Monster is not the successor of any creature.
- Different creatures have different successors.
- If a proposition is true of the Monster, and its being true of a creature implies that it is true of that creature’s successor, then it is true of all creatures.
Thus, when Gödel’s theorem refers to a system containing Peano arithmetic, it means a system at least as powerful as the formal system we use to describe natural numbers. The two theorems can therefore be restated as:
- First theorem: in a system of number theory, one can construct true propositions that cannot be proved. The system cannot derive all truths and is therefore incomplete.
- Second theorem: a system of number theory cannot prove its own consistency.
For the first theorem, Gödel therefore only needs to show that there is a statement \(G\) within the formal system for which we cannot prove whether it is a theorem—that is, a provable true proposition. What \(G\) should actually say is, “\(G\) is not a TNT theorem”: essentially a formal-system version of the liar paradox.
But how can such a \(G\) be constructed? The statement relies on self-reference, so the key is to construct that self-reference. In an informal statement such as “This statement of mine is false,” the words “this statement of mine” refer back to the statement itself. But that reference depends on a great deal of external information. We know what those words refer to because the surrounding context supplies that knowledge. What we need here is absolute self-reference.
To achieve it, we use Gödel numbering: encode all the symbols in the formal system as numbers, then describe the rules for manipulating those symbols through arithmetic rules. This extra layer of numbering lets us talk, inside the formal system, about the system’s own theorems.
We can also see a more general pattern in \(G\): a formula has itself substituted into itself. We can name this operation “Quine.” Since what we actually substitute is the formula’s own Gödel number—its arithmetized representation—we can write it as \(ARITHMOQUINE\{a’, a’’\}\), where \(a’’\) is the result of substituting the Gödel number of \(a’\) into itself.
We also need a predicate \(TNT-PROOF-PAIR\{a, a’\}\), meaning that the derivation \(a\) produces the theorem \(a’\) in TNT. In other words, \(a’\) is a TNT theorem, with its derivation explicitly supplied.
We can now write the following string: \[\sim \exists a: \exists a’:<TNT-PROOF-PAIR \{a,a’\} \land ARITHMOQUINE\{a’’, a’\}>\] It says that there are no \(a\) and \(a’\) such that \(a’\) is a TNT string obtained as the result of a proof pair and is also the result of Quining. In other words, no string in the formal system is the result of that Quine operation. The author calls this the \(G\)-string.
Finally, arithmoquine the \(G\)-string to obtain $G$: \[\sim \exists a: \exists a’:<TNT-PROOF-PAIR \{a,a’\} \land ARITHMOQUINE\{SSSSSSSS…0, a’\}>\] This says that there are no \(a\) and \(a’\) such that \(a’\) is a TNT string obtained as the result of a proof pair and is also the result of Quining the \(G\)-string. That is:
- The result of Quining the \(G\)-string is not a string in the formal system.
- But we know that the result of Quining the \(G\)-string is precisely this string, \(G\).
So \(G\) is the string we were looking for: one that says, “I am not a theorem.” The central trick is Quining. It is the Quine operation within the string that creates the self-referential contradiction: we describe Quining inside the statement, and we also Quine the statement itself.
That proves Gödel’s theorem. The existence of \(G\) is the root of the formal system’s inability to be complete.
And so:
- The dream of so many mathematicians over more than two thousand years falls apart. We now know that provability is forever weaker than truth: no formal system can prove every truth. Hilbert’s grand early-twentieth-century project of formalizing mathematics is undone as well.
- Human cognition, itself a sufficiently powerful formal system, also has limits. Our minds cannot simultaneously accommodate a statement’s being both true and false.
- Stepping outside the system is impossible: methods within a system cannot establish the system itself, as in Gödel’s second theorem.
Isomorphic Formal Systems in Mathematical Logic and Molecular Biology
Hofstadter sees a strong resemblance between biological heredity and the TNT formal system described above.
We know the broad outline of how genetic material works: mRNA copies information from DNA through transcription, then travels to ribosomes in the cytoplasm. The ribosomes use nearby tRNAs carrying amino acids to produce proteins according to the mRNA’s information, a process called translation. Here, tRNA acts as a mapping that lets the ribosome obtain amino acids from codons. DNA specifies only the protein’s primary structure; after synthesis, the protein folds itself into a complex shape, its tertiary structure.
Yet transcription and translation themselves require enzymes made from their own products—proteins—and an enzyme’s function is determined mainly by its shape, its tertiary structure. Meanwhile, to decode DNA’s intrinsic message, the ribosome needs the tRNA mapping, and tRNA is itself produced from DNA.
This gives us an entanglement. The recursion seems as though it ought to prevent the system from working, which is clearly not what happens. We can see its correspondence with TNT in this photograph from the book:
The most striking feature is the large loop that can be repeated indefinitely. At this point, the formal system can operate across many different levels. DNA can replicate itself at some higher level, or levels, within this loop; TNT can talk about itself at some level within it. Perhaps the central secret of intelligence and life lies in this pattern that crosses an unlimited number of levels.
Escher and Bach
Several of the book’s central concepts—paradox, self-reference, recursion, and stepping outside a level—are clearly visible in Escher’s work.
In Relativity, determining the meaning of a formal system involves importing external meaning to fix the meanings of its internal undefined terms. Stairs provide a relatively clear external meaning, which we borrow to interpret the rest of the picture. Unlike a well-defined formal system such as the qp-system, however, the undefined elements beyond the stairs do not resolve into an intelligible system.
Dragon could be seen as a visualization of Gödel’s second theorem. As a two-dimensional dragon, it keeps trying to pass out through a plane, but however hard it tries, it remains forever inside the two-dimensional system. Transcending the system may be something that can never be done.
There are many other examples. Print Gallery seems almost to describe how \(G\) is constructed, while Drawing Hands makes us forget Escher’s own hand outside the system.
Bach’s frequently used technique of canon constructs a whole piece from a theme and copies distributed across different voices. These are not identical copies, but they retain much of the original information: a kind of isomorphism. His fugal masterpiece The Musical Offering is rather like a meta-fugue, speaking about itself through self-reference on many different levels. In BWV 591, he rapidly changes the tonal center, disorienting the listener to create a very distinctive experience. This demonstrates how limited the stack we can maintain in our heads really is, revealing something of how the brain processes music.
Bach and Escher also form a direct isomorphism in their works on the crab canon. Their similarly named works use very similar techniques: Bach overlays a theme with its retrograde form, while Escher tiles the image with crabs facing forward and backward.
Human and Artificial Intelligence
One of the book’s central questions is how human intelligence works. Another is whether genuine artificial intelligence is possible, and how it might be possible. Hofstadter does not give especially definite answers to either, but offers many conjectures.
The brain can be understood as an extremely complex, multilayered formal system. Its lower levels consist of neuronal networks, which, through chemical signals, give rise to genuine intelligence at higher levels. Across those levels, the same thing can have many different isomorphic representations.
But is a brain necessary for intelligence? If we use electronic components to simulate its neuronal networks, and higher-level software to simulate its successive layers of symbols, could we create artificial intelligence genuinely indistinguishable from human intelligence? Or, if we understood how each level worked, could we separate the brain’s software from its hardware? Could we port all of a person’s thoughts into another brain whose underlying structure was also a neuronal network? If human intelligence is portable—or extractable—and the brain’s underlying structure can be simulated electronically, then artificial intelligence must be possible.
How, then, does free will arise? How does the formal system of human intelligence step beyond its own design rules to produce a sense of self? Hofstadter suggests that the self is itself a concept at some symbolic level. Once this concept appears, it takes charge of external stimuli. Internally, it consists of a tangle of symbols from many different levels, into which those stimuli are submerged. At that point, the program can no longer precisely control the details of every action inside the system; it can only direct the system as a whole through a kind of intuition. With intuition, self-awareness and various kinds of meaning may emerge within the formal system. We might then regard it as a genuinely intelligent agent. After that, the other qualities we associate with such an agent—creativity, personal wishes, and so on—can emerge from the same interwoven formal system.