Formatted Word version
Douglas Hofstadter
INTRODUCTION TO THE 20TH ANNIVERSARY EDITION
OVERVIEW viii
LIST OF ILLUSTRATIONS xiv
WORDS OF THANKS xix
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
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
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
Getting Around Infinity 59
Sonata for Unaccompanied Achilles 61
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
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
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
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
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
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
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
Prelude... 275
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
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
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
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
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
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
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
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
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
"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
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)