Gödel, Escher, Bach Wiki


The idea of recursion is presented in many different contexts: musical patterns, linguistic patterns, geometric structures, mathematical functions, physical theories, computer programs, and others. (p. ix)

While you read[]


Some questions are adapted from Curry and Kelleher's lecture notes.

  1. We have provide lots of examples of recursion, self-similar fractals, and so on. Come up with some other contexts in which recursion appears.
  2. Use the RTN on p. 134 to come up with some "fancy nouns".
    a. What path do you go down to implement the linguistic structure of the nursery rhyme "The House that Jack Built"? Leave off the "This is", because this isn't a machine for making complete sentences. For reference, it goes, in part:
    [This is] the dog that worried the cat that chased the rat that ate the cheese that lay in the house that Jack built.
    b. What path do you go down to make a phrase where all the verbs pile up at the end, as the German language is known for?
  3. On p. 137, Hofstadter describes the sequence known as "G-flip", where you flip diagram G from left to right and re-number the nodes.
    a. Draw a few levels of G-flip. What is the algebraic expression that defines it?
    b. Draw a few levels of H-flip. What is the algebraic expression that defines it?
  4. The tortoise icon indicates hard problems. What does the diagram of the "married" functions F and M look like?
  5. To what extent are Feynman diagrams a formal system?
  6. What type of isomorphism links all the butterflies in Escher’s Butterflies on page 148?
  7. What is the connection between recursion and isomorphism? What does Hofstadter say the connection is?
  8. What is the essence of modularity in programming?
  9. Discuss the following quote: “Modularity exists, of course, in hi-fi systems, furniture, living cells, human society — wherever there is a hierarchical organization.” (p. 150)
  10. Did "Hofstadter's Law" (p. 152) actually apply to a computer program becoming the world chess champion?
  11. How does human intelligence make use of recursion, according to Hofstadter?
  12. The tortoise icon indicates hard problems. How does human intelligence make use of recursion, according to someone relevant besides Hofstadter?


Recursive Structures and Processes[]

Curry and Kelleher's course had an excellent handout called Recursive Structures and Processes, describing recursion in modern computer programming, which is particularly relevant to this chapter. If you already program six recursive functions before lunch, you don't need it, but if the idea is new to you, it can be pretty helpful.

RTNs and CFGs[]

The "Recursive Transition Networks" in this chapter are isomorphic to a more commonly known system known as a ➟ context-free grammar or CFG.

CFGs were proposed (by ➟ Noam Chomsky) as a model of human languages, but he eventually found CFGs insufficient for that purpose. (We still don't know a formalism that actually represents an entire human language as it's actually used.) They are an excellent model of many computer languages.

Most of the grammatical structures in human languages can be described by a CFG, and therefore could be diagrammed as a Recursive Transition Network with lots of diagrams in it, but there are always exceptions. The only human language I've seen thoroughly described by a CFG is the restricted language of ➟ Aviation English).


(This section is for adding your thoughts about the chapter. Sign what you write with your user name. Others may edit this section for length later. More free-form, unedited discussion can take place in the comment section below.)

  • Escher's title "Fish and Scales" is a pun on the word "scale". I hadn't noticed until now. --rspeer