Home

Formatted Word version

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

Douglas Hofstadter

DETAILED TABLE OF CONTENTS

INTRODUCTION TO THE 20TH ANNIVERSARY EDITION

OVERVIEW          viii

LIST OF ILLUSTRATIONS          xiv

WORDS OF THANKS          xix

PART I: GEB

INTRODUCTION: A MUSICO-LOGICAL OFFERING          3

Author          3
Bach          3
Canons and Fugues          8
An Endlessly Rising Canon          10
Escher          10
Gödel          15
Mathematical Logic: A Synopsis          19
Banishing Strange Loops          21
Consistency, Completeness, Hilbert's Program          23
Babbage, Computers, Artificial Intelligence...           24
...and Bach           27
"Gödel, Escher, Bach"          27

     Three-Part Invention          29

CHAPTER 1: THE MU-PUZZLE          33

Formal Systems          33
Theorems, Axioms, Rules          35
Inside and Outside the System          36
Jumping out of the System          37
M-Mode, I-Mode, U-Mode          38
Decision Procedures          39

     Two-Part Invention          43

CHAPTER 2: MEANING AND FORM IN MATHEMATICS          46

The pq-System          46
The Decision Procedure          47
Bottom-up vs. Top-down          48
Isomorphisms Induce Meaning          49
Meaningless and Meaningful Interpretations          51
Active vs. Passive Meanings          51
Double-Entendre!          52
Formal Systems and Reality          53
Mathematics and Symbol Manipulation          54
The Basic Laws of Arithmetic          55
Ideal Numbers          56
Euclid's Proof          58
Getting Around Infinity          59

     Sonata for Unaccompanied Achilles          61

CHAPTER 3: FIGURE AND GROUND          64

Primes vs. Composites          64
The tq-System          64
Capturing Compositeness          65
Illegally Characterizing Primes          66
Figure and Ground          67
Figure and Ground in Music          70
Recursively Enumerable Sets vs. Recursive Sets          71
Primes as Figure Rather than Ground          73

     Contracrostipunctus          75

CHAPTER 4: CONSISTENCY, COMPLETENESS, AND GEOMETRY          82

Implicit and Explicit Meaning          82
Explicit Meaning of the Contracrostipunctus          82
Implicit Meanings of the Contracrostipunctus          84
Mapping Between the Contracrostipunctus and Gödel's Theorem          85
The Art of the Fugue          86
Problems Caused by Gödel's Result          86
The Modified pq-System and Inconsistency          87
Regaining Consistency          88
The History of Euclidean Geometry          88
The Many Faces of Noneuclid          91
Undefined Terms          92
The Possibility of Multiple Interpretations          94
Varieties of Consistency          94
Hypothetical Worlds and Consistency          95
Embedding of One Formal System in Another          97
Layers of Stability in Visual Perception          97
Is Mathematics the Same in Every Conceivable World?          99
Is Number Theory the Same in All Conceivable Worlds?          100
Completeness          100
How an Interpretation May Make or Break Completeness          102
Incompleteness of Formalized Number Theory          102

     Little Harmonic Labyrinth          103

CHAPTER 5: RECURSIVE STRUCTURES AND PROCESSES          127

What Is Recursion?          127
Pushing, Popping, and Stacks          128
Stacks in Music          129
Recursion in Language          130
Recursive Transition Networks          131
"Bottoming Out" and Heterarchies          133
Expanding Nodes          134
Diagram G and Recursive Sequences          135
A Chaotic Sequence          137
Two Striking Recursive Graphs          138
Recursion at the Lowest Level of Matter          142
Copies and Sameness          146
Programming and Recursion: Modularity, Loops, Procedures          149
Recursion in Chess Programs          150
Recursion and Unpredictability          152

     Canon by Intervallic Augmentation          153

CHAPTER 6: THE LOCATION OF MEANING          158

When is One Thing Not Always the Same?          158
Information-Bearers and Information-Revealers          158
Genotype and Phenotype          159
Exotic and Prosaic Isomorphisms          159
Jukeboxes and Triggers          160
DNA and the Necessity of Chemical Context          161
An Unlikely UFO          162
Levels of Understanding of a Message          162
"Imaginary Spacescape"          163
The Heroic Decipherers          164
Three Layers of Any Message          166
Schrödinger's Aperiodic Crystals          167
Languages for the Three Levels          167
The "Jukebox" Theory of Meaning          170
Against the Jukebox Theory          170
Meaning Is Intrinsic If Intelligence is Natural          171
Earth Chauvinism          171
Two Plaques in Space          173
Bach vs. Cage Again          174
How Universal Is DNA's Message?          175

     Chromatic Fantasy, and Feud          177

CHAPTER 7: THE PROPOSITIONAL CALCULUS          181

Words and Symbols          181
Alphabet and First Rule of the Propositional Calculus          181
Well-Formed Strings          181
More Rules of Inference          183
The Fantasy Rule          183
Recursion and the Fantasy Rule          184
The Converse of the Fantasy Rule          185
The Intended Interpretation of the Symbols          186
Rounding Out the List of Rules          187
Justifying the Rules          188
Playing Around with the System          188
Semi-Interpretations          189
Ganto's Ax          189
Is There a Decision Procedure for Theorems?          190
Do We Know the System Is Consistent?          191
The Carroll Dialogue Again          192
Shortcuts and Derived Rules          193
Formalizing Higher Levels           194
Reflections on the Strengths and Weaknesses of the System          195
Proofs vs. Derivations          195
The Handling of Contradictions          196

     Crab Canon          199

CHAPTER 8: TYPOGRAPHICAL NUMBER THEORY          204

The Crab Canon and Indirect Self-Reference          204
What We Want to Be Able to Express in TNT          204
Numerals          205
Variables and Terms          206
Atoms and Propositional Symbols          207
Free Variables and Quantifiers          207
Translating Our Sample Sentences          209
Tricks of the Trade          210
Translation Puzzles for You          212
How to Distinguish True from False?          213
The Rules of Well-Formedness          213
A Few More Translation Exercises          215
A Nontypographical System          215
The Five Axioms and First Rules of TNT          215
The Five Peano Postulates          216
New Rules of TNT: Specification and Generalization          217
The Existential Quantifier          218
Rules of Equality and Successorship          219
Illegal Shortcuts          220
Why Specification and Generalization Are Restricted          220
Something Is Missing          221
[w]-Incomplete Systems and Undecidable Strings          221
Non-Euclidean TNT          222
[w]-Inconsistency Is Not the Same as Inconsistency          223
The Last Rule          223
A Long Derivation          225
Tension and Resolution in TNT          227
Formal Reasoning vs. Informal Reasoning          228
Number Theorists Go out of Business          228
Hilbert's Program          229

     A Mu Offering          231

CHAPTER 9: MUMON AND GÖDEL          246

What is Zen?          246
Zen Master Mumon          246
Zen's Struggle Against Dualism          251
Ism, The Un-Mode, and Unmon          254
Zen and Tumbolia          255
Escher and Zen          255
Hemiolia and Escher          257
Indra's Net          258
Mumon on MU          259
From Mumon to the MU-puzzle          259
Mumon Shows Us How to Solve the MU-puzzle          260
Gödel-Numbering the MIU-System          261
Seeing Things Both Typographically and Arithmetically          262
MIU-Producible Numbers          264
Answering Questions about Producible Numbers by Consulting TNT          265
The Dual Nature of MUMON          266
Codes and Implicit Meaning          267
The Boomerang: Gödel-Numbering TNT          267
TNT-Numbers: A Recursively Enumerable Set of Numbers          269
TNT Tries to Swallow Itself          270
G: A String Which Talks about Itself in Code          271
G's Existence Is What Causes TNT's Incompleteness          271
Mumon Has the Last Word          272

PART II: EGB

     Prelude...           275

CHAPTER 10: LEVELS OF DESCRIPTION, AND COMPUTER SYSTEMS          285

Levels of Description          285
Chunking and Chess Skill          285
Similar Levels          287
Computer Systems          287
Instructions and Data          289
Machine Language vs. Assembly language          290
Programs That Translate Programs          291
Higher-Level Languages, Compilers, and Interpreters          292
Bootstrapping          293
Levels on Which to Describe Running Programs          294
Microprogramming and Operating Systems          295
Cushioning the User and Protecting the System          296
Are Computers Super-Flexible or Super-Rigid?          297
Second-Guessing the Programmer          298
AI Advanced Are Language Advances          299
The Paranoid and the Operating System          300
The Border between Software and Hardware          301
Intermediate Levels and the Weather          302
From Tornados to Quarks          303
Superconductivity: A "Paradox" of Renormalization          304
"Sealing-off"          305
The Trade-off between Chunking and Determinism          306
"Computers Can Only Do What You Tell Them to Do"          306
Two Types of System          307
Epiphenomena          308
Mind vs. Brain          309

     ...Ant Fugue           311

CHAPTER 11: BRAINS AND THOUGHTS          337

New Perspectives on Thought          337
Intensionality and Extensionality          337
The Brain's "Ants"          339
Larger Structures in the Brain          340
Mappings between Brains          341
Localization of Brain Processes: An Enigma          342
Specificity in Visual Processing          343
A "Grandmother Cell"?          344
Funneling into Neural Modules          346
Modules Which Mediate Thought Processes          348
Active Symbols          349
Classes and Instances          351
The Prototype Principle          352
The Splitting-off of Instance from Classes          352
The Difficulty of Disentangling Symbols from Each Other          354
Symbols -- Software or Hardware?          356
Liftability of Intelligence          358
Can One Symbol Be Isolated?          359
The Symbols of Insects          360
Class Symbols and Imaginary Worlds          361
Intuitive Laws of Physics          362
Procedural and Declarative Knowledge          363
Visual Imagery          364

     English French German Suite          366

CHAPTER 12: MINDS AND THOUGHTS          369

Can Minds Be Mapped onto Each Other?          369
Comparing Different Semantic Networks          371
Translations of "Jabberwocky"          372
ASU's          373
A Surprise Reversal          374
Centrality and Universality          374
How Much Do Language and Culture Channel Thought?          376
Trips and Itineraries in ASU's          377
Possible, Potential, and Preposterous Pathways          378
Different Styles of Translating Novels          379
High-Level Comparisons between Programs          380
High-Level Comparisons between Brains          382
Potential Beliefs, Potential Symbols          382
Where is the Sense of Self?          384
Subsystems          385
Subsystems and Shared Code          386
The Self-Symbol and Consciousness          387
Our First Encounter with Lucas          388

     Aria with Diverse Variations          391

CHAPTER 13: BlooP AND FlooP AND GlooP          406

Self-Awareness and Chaos          406
Representability and Refrigerators          406
Ganto's Ax in Metamathmatics          407
Finding Order by Choosing the Right Filter          407
Primordial Steps of the Language BlooP          409
Loops and Upper Bounds          410
Conventions of BlooP          410
IF-Statements and Branching          411
Automatic Chunking          412
BlooP Tests          413
BlooP Programs Contain Chains of Procedures          413
Suggested Exercises          415
Expressibility and Representability          417
Primitive Recursive Predicates Are Represented in TNT          417
Are There Functions Which Are Not Primitive Recursive?          418
Pool B, Index Numbers, and Blue Programs          418
The Diagonal Method          420
Cantor's Original Diagonal Argument          421
What Does a Diagonal Argument Prove?          422
The Insidious Repeatability of the Diagonal Argument          423
From BlooP to FlooP          424
Terminating and Nonterminating FlooP Programs          425
Turing's Trickery          425
A Termination Tester Would Be Magical          426
Pool F, Index Numbers, and Green Programs          427
The Termination Tester Gives Us Red Programs          427
GlooP...           428
...Is a Myth           428
The Church-Turing Thesis          429
Terminology: General and Partial Recursive          429
The Power of TNT          430

     Air on G's String          431

CHAPTER 14: ON FORMALLY UNDECIDABLE PROPOSITIONS OF TNT AND RELATED SYSTEMS          438

The Two Ideas of the "Oyster"          438
The First Idea: Proof-Pairs          438
Proof-Pair-ness Is Primitive Recursive...           440
...And Is Therefore Represented in TNT           441
The Power of Proof-Pairs          441
Substitution Leads to the Second Idea          443
Arithmoquining          445
The Last Straw          446
TNT Says "Uncle!"          448
"Yields Nontheoremhood When Arithmoquined"          449
Gödel's Second Theorem          449
TNT Is [w]-Incomplete          450
Two Different Ways to Plug Up the Hole          451
Supernatural Numbers          452
Supernatural Theorems Have Infinitely Long Derivations          454
Supernatural Addition and Multiplication          455
Supernaturals Are Useful...           455
...But Are They Real?           455
Bifurcations in Geometry, and Physicists          456
Bifurcations in Number Theory, and Bankers          457
Bifurcations in Number Theory, and Metamathematicians          458
Hilbert's Tenth Problem and the Tortoise          459

     Birthday Cantatatata...           461

CHAPTER 15: JUMPING OUT OF THE SYSTEM          465

A More Powerful Formal System          465
The Gödel Method Reapplied          466
Multifurcation          467
Essential Incompleteness          468
The Passion According to Lucas          471
Jumping Up a Dimension          473
The Limits of Intelligent Systems          475
There Is No Recursive Rule for Naming Ordinals          476
Other Refutations of Lucas          476
Self-Transcendence -- A Modern Myth          477
Advertisement and Framing Devices          478
Simplicio, Salviati, Sagredo: Why Three?          478
Zen and "Stepping Out"          479

     Edifying Thoughts of a Tobacco Smoker          480

CHAPTER 16: SELF-REF AND SELF-REP          495

Implicitly and Explicitly Self-Referential Sentences          495
A Self-Reproducing Program          498
What Is a Copy?          500
A Self-Reproducing Song          500
Epimenides Straddles the Channel          501
A Program That Prints Out Its Own Gödel Number          502
Gödelian Self-Reference          502
A Self-Rep by Augmentation          503
A Kimian Self-Rep          503
What Is the Original?          503
Typogenetics          504
Strands, Bases, Enzymes          505
Copy Mode and Double Strands          506
Amino Acids          508
Translation and the Typogenetic Code          509
Tertiary Structure of Enzymes          510
Punctuation, Genes, and Ribosomes          512
Puzzle: A Typogenetical Self-Rep          512
The Central Dogma of Typogenetics          513
Strange Loops, TNT, and Real Genetics          514
DNA and Nucleotides          514
Messenger RNA and Ribosomes          517
Amino Acids          518
Ribosomes and Tape Recorders          518
The Genetic Code          519
Tertiary Structure          519
Reductionistic Explanation of Protein Function          520
Transfer RNA and Ribosomes          522
Punctuation and the Reading Frame          524
Recap          525
Levels of Structure and Meaning in Proteins and Music          525
Polyribosomes and Two-Tiered Canons          527
Which Came First -- The Ribosome or the Protein?          528
Protein Function          528
Need for a Sufficiently Strong Support System          529
How DNA Self-Replicates          530
Comparison of DNA's Self-Rep Method with Quining          531
Levels of Meaning of DNA          531
The Central Dogmap          532
Strange Loops in the Central Dogmap          534
The Central Dogmap and the Contracrostipunctus          534
E. Coli vs. T4          537
A Molecular Trojan Horse          538
Recognition, Disguises, Labeling          540
Henkin Sentences and Viruses          541
Implicit vs. Explicit Henkin Sentences          542
Henkin Sentences and Self-Assembly          542
Two Outstanding Problems: Differentiation and Morphogenesis          543
Feedback and Feedforward          544
Repressors and Inducers          544
Feedback and Strange Loops Compared          545
Two Simple Examples of Differentiation          546
Level Mixing in the Cell          546
The Origin of Life          548

     The Magnificrab, Indeed          549

CHAPTER 17: CHURCH, TURING, TARSKI, AND OTHERS          559

Formal and Informal Systems          559
Intuition and the Magnificent Crab          560
The Church-Turing Thesis          561
The Public-Processes Version          562
Srinivasa Ramanujan          562
"Idiots Savants"          567
The Isomorphism Version of the Church-Turing Thesis          567
Representation of Knowledge about the Real World          569
Processes That Are Not So Skimmable          570
Articles of Reductionistic Faith          571
Partial Progress in AI and Brain Simulation?          572
Beauty, the Crab, and the Soul          573
Irrational and Rational Can Coexist on Different Levels          575
More Against Lucas          577
An Underpinning of AI          578
Church's Theorem          579
Tarski's Theorem          580
The Impossibility of the Magnificrab          581
Two Types of Form          581
Meaning Derives from Connections to Cognitive Structures          582
Beauty, Truth, and Form          583
The Neural Substrate of the Epimenides Paradox          584

     SHRDLU, Toy of Man's Designing          586

CHAPTER 18: ARTIFICIAL INTELLIGENCE: RETROSPECTS          594

Turing          594
The Turing Test          595
Turing Anticipates Objections          597
"Parry Encounters the Doctor"          599
A Brief History of AI          600
Mechanical Translation          603
Computer Chess          603
Samuel's Checker Program          604
When Is a Program Original?          606
Who Composes Computer Music?          607
Theorem Proving and Problem Reduction          609
Shandy and the Bone          611
Changing the Problem Space          611
The I-Mode and the M-Mode Again          613
Applying AI to Mathematics          614
The Crux of AI: Representation of Knowledge          615
DNA and Proteins Help Give Some Perspective          616
Modularity of Knowledge          617
Representing Knowledge in a Logical Formalism          618
Deductive vs. Analogical Awareness          619
From Computer Haiku to an RTN-Grammar          619
From RTN's to ATN's          621
A Little Turing Test          621
Images of What Thought Is          623
Higher-Level Grammars...           625
Grammars for Music?          626
Winograd's Program SHRDLU          627
The Structure of SHRDLU          628
PLANNER Facilitates Problem Reduction          629
Syntax and Semantics          630

     Contrafactus          633

CHAPTER 19: ARTIFICIAL INTELLIGENCE: PROSPECTS          641

"Almost" Situations and Subjunctives          641
Layers of Stability          643
Frames and Nested Contexts          644
Bongard Problems          646
Preprocessing Selects a Mini-Vocabulary          647
High-Level Descriptions          647
Templates and Sameness-Detectors          650
A Heterarchical Program          651
The Concept Network          653
Slippage and Tentativity          654
Meta-Descriptions          656
Flexibility is Important          657
Focusing and Filtering          657
Science and the World of Bongard Problems          659
Connections to Other Types of Thought          661
Message-Passing Languages, Frames, and Symbols          662
Enzymes and AI          663
Fission and Fusion          664
Epigenesis of the Crab Canon          665
Conceptual Skeletons and Conceptual Mapping          668
Recombinant Ideas          668
Abstractions, Skeletons, Analogies          669
Multiple Representations          670
Ports of Access          670
Forced Matching          671
Recap          672
Creativity and Randomness          673
Picking up Patterns on All Levels          674
The Flexibility of Language          674
Intelligence and Emotions          675
AI Has Far to Go          676
Ten Questions and Speculations          676

     Sloth Canon          681

CHAPTER 20: STRANGE LOOPS, OR TANGLED HIERARCHIES          684

Can Machines Possess Originality?          684
Below Every Tangled Hierarchy Lies An Inviolate Level          686
A Self-Modifying Game          687
The Authorship Triangle Again          688
Escher's Drawing Hands          689
Brain and Mind: A Neural Tangle Supporting a Symbol Tangle          691
Strange Loops in Government          692
Tangles Involving Science and the Occult          693
The Nature of Evidence          694
Seeing Oneself          695
Gödel's Theorem and Other Disciplines          696
Introspection and Insanity: A Gödelian Problem          696
Can We Understand Our Own Minds or Brains?          697
Gödel's Theorem and Personal Nonexistence          698
Science and Dualism          698
Symbol vs. Object in Modern Music and Art          699
Magritte's Semantic Illusions          700
The "Code" of Modern Art          703
Ism Once Again          704
Understanding the Mind          706
Accidental Inexplicability of Intelligence?          707
Undecidability Is Inseparable from a High-Level Viewpoint          707
Consciousness as an Intrinsically High-Level Phenomenon          708
Strange Loops as the Crux of Consciousness          709
The Self-Symbol and Free Will          710
A Gödel Vortex Where All Levels Cross          713
An Escher Vortex Where All Levels Cross          715
A Bach Vortex Where All Levels Cross          717

     Six-Part Ricercar          720

 

NOTES          743

BIBLIOGRAPHY          746

CREDITS          757

INDEX          759

ABOUT THE AUTHOR          778


Detailed TOC extracted by Michael Hoffman, Egodeath.com

Home (ego death and self-control cybernetics)