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

Contents

Overview

viii

List

of

Illustrations

xiv

Words

of

Thanks

xix

Part I: GEB

Introduction: A Musico-Logical Offering

Three-Part

Invention

Chapter

I:

The

MU-puzzle

Two-Part

Invention

Chapter II: Meaning and Form in Mathematics

Sonata for Unaccompanied Achilles

Chapter III: Figure and Ground

Contracrostipunctus

Chapter IV: Consistency, Completeness, and Geometry

Little

Harmonic

Labyrinth

Chapter V: Recursive Structures and Processes

Canon by Intervallic Augmentation

Chapter VI: The Location of Meaning

Chromatic Fantasy, And Feud

Chapter VII: The Propositional Calculus

Crab

Canon

Chapter VIII: Typographical Number Theory

A

Mu

Offering 231

Chapter IX: Mumon and Gdel

Contents

II

Part II EGB

Prelude

...

Chapter X: Levels of Description, and Computer Systems

Ant

Fugue

Chapter

XI:

Brains

and

Thoughts

English

French

German

Suit

Chapter

XII:

Minds

and

Thoughts

Aria

with

Diverse

Variations

Chapter XIII: BlooP and FlooP and GlooP

Air

on

G's

String

Chapter XIV: On Formally Undecidable Propositions of TNT

and Related Systems

Birthday

Cantatatata

... 461

Chapter XV: Jumping out of the System

Edifying Thoughts of a Tobacco Smoker

Chapter

XVI:

Self-Ref

and

Self-Rep

The

Magn

fierab,

Indeed

Chapter XVII: Church, Turing, Tarski, and Others

SHRDLU, Toy of Man's Designing

Chapter XVIII: Artificial Intelligence: Retrospects

Contrafactus

Chapter XIX: Artificial Intelligence: Prospects

Sloth

Canon

Chapter XX: Strange Loops, Or Tangled Hierarchies

Six-Part

Ricercar

Notes

Bibliography

Credits

Index

Contents

III

Overview

Part I: GEB

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 Gdels Theorem. A brief presentation of the history of logic and paradoxes is given as background for Gdels 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

Overview

IV

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 Gdels 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.