notes about gödel, escher, bach

what is recursion? 127

nesting and variations on nesting

a recursive definition always defines something in terms of a simpler version of itself

one of the most common ways in which recursion appears in daily life is when you postpone completing a task in favor of a simpler task often of the same type

pushing, popping and stacks 128

basic terminology of recursion in computer science: push, pop and push-down stack introduced in the late 50’s as part of IPL one of the first languages for artificial intelligence

to push means to suspend operations on the task you’re currently working on without forgetting where you are and to take up a new task

to pop is the reverse close operations on one level and resume operations where left off one level deeper

stacks in music 129

we maintain a mental stack of keys and each new modulation pushes a new key into the stack we want to hear the sequence of keys retracted in reverse order until the tonic is reached this is an exaggeration

any reasonably musical person automatically maintains a shallow stack with two keys, the tonic and the pseudotonic

a local resolution should heighten the global tension rather than relieving it because it is a piece of irony tension and resolution are the hearth and soul of music

bottoming out and heterarchies 133

indirect recursion

there can be a whole family of networks which are all tangled up calling each other and themselves

a program which has such a structure in which there is no single “highest level” or “monitor” is called a heterarchy

term due to warren mcculloch

recursion and unpredictability 152

for a set to be recursively enumerable means that it can be generated from a set of starting elements by repeated application of rules of inference

thus the set grows each new element being compounded out of previous elements

this is the essence of recursion defining in terms of simpler versions instead of explicitly

recursive enumeration is a process in which new things emerge from old things by rules

it might seem that some types of recursively defined sequences exhibit increasing complexity of behavior so that the further you go the less predictable they get

language as an activator 628

(original title “the structure of shrdlu by winograd”, 628)

all language use can be though of as a way of activating procedures within the hearer

we can think of any utterance as a program one that indirectly causes a set of operations to be carried out within the hearer’s cognitive system

this program writing is indirect in the sense that we are dealing with an intellingent interpreter who may take a set of actions which are quite different from those the speaker intended

creativity and randomness 673

creativity is the essence of what is not mechanical yet every creative act is mechanical

when programs cease to be transparent to their creators the approach to creativity has begun

the world is a giant heap of randomness we can mirror some of it inside our heads