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
Godel 15
Mathematical Logic: A Synopsis
19
Banishing Strange Loops
21
Consistency, Completeness, Hilbert's Program
23
Babbage, Computers, Artificial Intelligence...
24
...and Bach
27
"Godel, 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 Godel'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
Godel-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
Godelian 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
Godel's Theorem and Other Disciplines
696
Introspection and Insanity: A Gödelian Problem
696
Can We Understand Our Own Minds or Brains?
697
Godel'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