Tuesday, May 15, 2007

GEB Week 0: Introduction, strange loops

Okay--I'm not exactly Oprah and this isn't going to be like that. With that said, let's start discussion of GEB for the Google Summer of Code 2007. If you don't already have a copy, you still have time to pick it up from amazon or your local library, used book store, obscured dusty shelf in closet, roommate, russian site of questionable legality, etc.

For this week, you should try to read the introduction and the first dialogue, "Three-Part Invention". You should also try to read Chapters 1-3 for next week, if you want to stay completely up to speed (I'm grouping dialogues with the chapters they follow, so that reading for Chapter 1 "includes" the dialogue "Two-Part Invention"). However, like its subject matter, the process of reading GEB is not completely straightforward. Don't worry too much about sticking to the schedule; the book club is primarily about finding motivation to read and think critically about new ideas on a consistent basis this summer.

In the introduction, Hofstadter gives us a first taste of strange loops, a "phenomena [which] occurs whenever, by moving upwards (or downwards) through the levels of some hierarchical system, we unexpectedly find ourselves right back where we started." A simple yet fascinating example of this concept is demonstrated with Bach's "Endlessly Rising Canon," a piece of music which changes key upwards repeatedly until reaching the starting key, implying an infinite progression. The author also demonstrates strange loops in several of Escher's pieces, such as his famous waterfall, fed by a perplexing aqueduct which defies either gravity or reason.

Since I'm currently reading a book of rigorous number theory for the first time, I am reminded of the Peano axioms, which define the natural numbers by induction. How about a quine, a program which outputs itself?

How many strange loops can we list?

Update: Corrected reading assignment for next week.


Alexandre said...

How about this little gem? Of course, there is a the whole class of paradox, like "This sentence has two erors." Or from GEB itself (p. 21):

This following sentence is false.
The preceding sentence is true.

Here one in Python:
>>> a=[]
>>> a.append(a)
>>> a

Or even shorter:

a = lambda: a

And finally, my personal favorite:

Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.

Brian Jorgensen said...

I enjoyed that page, except for the conclusion: "The moral is obvious. You can't trust code that you did not totally create yourself." Ouch.

Surely PyPy is a strange loop. What about recursive acronyms, such as GNU's Not Unix?

Here's a good one from the Strange Loop wikipedia page:

A sketch on Late Night with Conan O'Brien once had Conan (seemingly spontaneously) become upset with a cue-card holder and tell him to leave the set; immediately, the cue-card holder was shown, holding a card with Conan's "you'd better leave" line written on it.

What other strange loops can we identify in meatspace?

Martin Harrigan said...

This may be more of a paradox than a strange loop, but I like it all the same.

In short: what is the first 'non-interesting' number? Does that fact make the number interesting?

Wikipedia also keeps a list of notable numbers but that has its own paradox.