Gödel, Escher, Bach: An Eternal Golden Braid

Contents

Overview

viii

List of Illustrations

xiv

Words of Thanks

xix

3

Three-Part Invention

29

33

Two-Part Invention

43

Chapter II: Meaning and Form in Mathematics

46

Sonata for Unaccompanied Achilles

61

64

Contracrostipunctus

75

Chapter IV: Consistency, Completeness, and Geometry

82

Little Harmonic Labyrinth

103

Canon by Intervallic Augmentation

153

158

Chromatic Fantasy, And Feud

177

181

Crab Canon

199

A Mu Offering

231

Chapter IX: Mumon and Gödel

246

Prelude ...

275

Chapter X: Levels of Description, and Computer Systems

285

Ant Fugue

311

337

English French German Suit

366

369

Aria with Diverse Variations

391

Chapter XIII: BlooP and FlooP and GlooP

406

Air on G's String

431

Chapter XIV: On Formally Undecidable Propositions of TNT

and Related Systems

438

Birthday Cantatatata ...

461

Chapter XV: Jumping out of the System

465

Edifying Thoughts of a Tobacco Smoker

480

495

The Magn fierab, Indeed

549

Chapter XVII: Church, Turing, Tarski, and Others

559

SHRDLU, Toy of Man's Designing

586

Contrafactus

633

641

Sloth Canon

681

Chapter XX: Strange Loops, Or Tangled Hierarchies

684

Six-Part Ricercar

720

Notes

743

Bibliography

746

Credits

757

Index

759

Overview

Introduction: A Musico-Logical Offering
. The book opens with the story of Bach's Musical Offering. Bach made an impromptu visit to King Frederick the Great of Prussia, and was requested to improvise upon a theme presented by the King. His improvisations formed the basis of that great work. The Musical Offering and its story form a theme upon which I "improvise"

throughout the book, thus making a sort of "Metamusical Offering". Self-reference and the interplay between different levels in Bach are discussed: this leads to a discussion of parallel ideas in Escher's drawings and then Gödel’s Theorem. A brief presentation of the history of logic and paradoxes is given as background for Gödel’s Theorem. This leads to mechanical reasoning and computers, and the debate about whether Artificial Intelligence is possible. I close with an explanation of the origins of the book-particularly the why and wherefore of the Dialogues.

Three-Part Invention.
Bach wrote fifteen three-part inventions. In this three-part Dialogue, the Tortoise and Achilles-the main fictional protagonists in the Dialogues-are "invented" by Zeno (as in fact they were, to illustrate Zeno's paradoxes of motion). Very short, it simply gives the flavor of the Dialogues to come.

Chapter I: The MU-puzzle.
A simple formal system (the MIL'-system) is presented, and the reader is urged to work out a puzzle to gain familiarity with formal systems in general. A number of fundamental notions are introduced: string, theorem, axiom, rule of inference, derivation, formal system, decision procedure, working inside/outside the system.

Two-Part Invention.
Bach also wrote fifteen two-part inventions. This two-part Dialogue was written not by me, but by Lewis Carroll in 1895. Carroll borrowed Achilles and the Tortoise from Zeno, and I in turn borrowed them from Carroll. The topic is the relation between reasoning, reasoning about reasoning, reasoning about reasoning about reasoning, and so on. It parallels, in a way, Zeno's paradoxes about the impossibility of motion, seeming to show, by using infinite regress, that reasoning is impossible. It is a beautiful paradox, and is referred to several times later in the book.

Chapter II: Meaning and Form in Mathematics.
A new formal system (the pq-system) is presented, even simpler than the MIU-system of Chapter I. Apparently meaningless at first, its symbols are suddenly revealed to possess meaning by virtue of the form of the theorems they appear in. This revelation is the first important insight into meaning: its deep connection to isomorphism. Various issues related to meaning are then discussed, such as truth, proof, symbol manipulation, and the elusive concept, "form".

Sonata for Unaccompanied Achilles
. A Dialogue which imitates the Bach Sonatas for unaccompanied violin. In particular, Achilles is the only speaker, since it is a transcript of one end of a telephone call, at the far end of which is the Tortoise. Their conversation concerns the concepts of "figure" and "ground" in various

contexts- e.g., Escher's art. The Dialogue itself forms an example of the distinction, since Achilles' lines form a "figure", and the Tortoise's lines-implicit in Achilles' lines-form a "ground".

Chapter III: Figure and Ground
. The distinction between figure and ground in art is compared to the distinction between theorems and nontheorems in formal systems. The question "Does a figure necessarily contain the same information as its ground%" leads to the distinction between recursively enumerable sets and recursive sets.

Contracrostipunctus
. This Dialogue is central to the book, for it contains a set of paraphrases of Gödel’s self-referential construction and of his Incompleteness Theorem. One of the paraphrases of the Theorem says, "For each record player there is a record which it cannot play." The Dialogue's title is a cross between the word "acrostic" and the word "contrapunctus", a Latin word which Bach used to denote the many fugues and canons making up his
Art of the Fugue
. Some explicit references to the Art of the Fugue are made. The Dialogue itself conceals some acrostic tricks.

Chapter IV: Consistency, Completeness, and Geometry
. The preceding Dialogue is explicated to the extent it is possible at this stage. This leads back to the question of how and when symbols in a formal system acquire meaning. The history of Euclidean and non-Euclidean geometry is given, as an illustration of the elusive notion of "undefined terms". This leads to ideas about the consistency of different and possibly "rival" geometries. Through this discussion the notion of undefined terms is clarified, and the relation of undefined terms to perception and thought processes is considered.

Little Harmonic Labyrinth
. This is based on the Bach organ piece by the same name. It is a playful introduction to the notion of recursive-i.e., nested structures. It contains stories within stories. The frame story, instead of finishing as expected, is left open, so the reader is left dangling without resolution. One nested story concerns modulation in music-particularly an organ piece which ends in the wrong key, leaving the listener dangling without resolution.

Chapter V: Recursive Structures and Processes
. The idea of recursion is presented in many different contexts: musical patterns, linguistic patterns, geometric structures, mathematical functions, physical theories, computer programs, and others.

Canon by Intervallic Augmentation
. Achilles and the Tortoise try to resolve the question, "Which contains more information-a record, or the phonograph which plays it This odd question arises when the Tortoise describes a single record which, when played on a set of different phonographs, produces two quite different melodies: B-A-C-H and C-A-G-E. It turns out, however, that these melodies are "the same", in a peculiar sense.

Chapter VI: The Location of Meaning.
A broad discussion of how meaning is split among coded message, decoder, and receiver. Examples presented include strands of DNA, undeciphered inscriptions on ancient tablets, and phonograph records sailing out in space. The relationship of intelligence to "absolute" meaning is postulated.

Chromatic Fantasy, And Feud
. A short Dialogue bearing hardly any resemblance, except in title, to Bach's
Chromatic Fantasy and Fugue
. It concerns the proper way to manipulate sentences so as to preserve truth-and in particular the question

of whether there exist rules for the usage of the word "arid". This Dialogue has much in common with the Dialogue by Lewis Carroll.

Chapter VII: The Propositional Calculus.
It is suggested how words such as .,and" can be governed by formal rules. Once again, the ideas of isomorphism and automatic acquisition of meaning by symbols in such a system are brought up. All the examples in this Chapter, incidentally, are "Zentences"-sentences taken from Zen koans. This is purposefully done, somewhat tongue-in-cheek, since Zen koans are deliberately illogical stories.

Crab Canon
. A Dialogue based on a piece by the same name from the
Musical Offering
. Both are so named because crabs (supposedly) walk backwards. The Crab makes his first appearance in this Dialogue. It is perhaps the densest Dialogue in the book in terms of formal trickery and level-play. Gödel, Escher, and Bach are deeply intertwined in this very short Dialogue.

Chapter VIII: Typographical Number Theory
. An extension of the Propositional Calculus called

"TNT" is presented. In TNT, number-theoretical reasoning can be done by rigid symbol manipulation. Differences between formal reasoning and human thought are considered.

A Mu Offering
. This Dialogue foreshadows several new topics in the book. Ostensibly concerned with Zen Buddhism and koans, it is actually a thinly veiled discussion of theoremhood and nontheoremhood, truth and falsity, of strings in number theory. There are fleeting references to molecular biology-particular) the Genetic Code. There is no close affinity to the
Musical
Offering,
other than in the title and the playing of self-referential games.

Chapter IX: Mumon and Gödel.
An attempt is made to talk about the strange ideas of Zen Buddhism. The Zen monk Mumon, who gave well known commentaries on many koans, is a central figure. In a way, Zen ideas bear a metaphorical resemblance to some contemporary ideas in the philosophy of mathematics. After this "Zennery", Gödel’s fundamental idea of Gödel-numbering is introduced, and a first pass through Gödel’s Theorem is made.

Prelude
... This Dialogue attaches to the next one. They are based on preludes and fugues from Bach's
Well-Tempered Clavier
. Achilles and the Tortoise bring a present to the Crab, who has a guest: the Anteater. The present turns out to be a recording of the W.T.C.; it is immediately put on. As they listen to a prelude, they discuss the structure of preludes and fugues, which leads Achilles to ask how to hear a fugue: as a whole, or as a sum of parts? This is the debate between holism and reductionism, which is soon taken up in the Ant Fugue.