One of my favorite books is the astonishingly imaginative Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter. This Pulitzer-Prize-winning book, published in 1979, is an extended meditation upon the underlying connections between the work of the three men mentioned in the title – Johann Sebastian Bach (who needs no introduction), the Dutch graphic artist M.C. Escher, and mathematician Kurt Gödel. Hofstadter, who inherited the prestigious editorship of Scientific American’s Mathematical Games column from the incomparable Martin Gardner, has described his inspiration for the project:
“I realized that to me, Gödel and Escher and Bach were only shadows cast in different directions by some central solid essence. I tried to reconstruct the central object, and came up with this book.”
It is hard to describe the tone and content of the book – it is at times witty and playful (much of the book takes the form of imaginary dialogues, a la Lewis Carrol, between Achilles and the Tortoise, and there is a great deal of word play and hidden puzzles), at times dense and didactic, but always unflaggingly, utterly brilliant. Really, and I mean this, GEB is so startlingly clever and original that at times it quite literally – and I do not ever misuse the word “literally” – took my breath away.
It is hard to say in a few words what the book is about. It is about about recursion, logic, music, art, fractals, DNA, number theory, formal systems, computer science, artificial intelligence, and much, much more, but all with one overarching theme, as described by the author:
“GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter. What is a self, and how can a self come out of stuff that is as selfless as a stone or a puddle?”
Here is a tiny tidbit, from the chapter Figure and Ground, which is about recursively enumerable systems, and positive vs. negative definitions of sets. Can you characterize the following set of integers?
1 3 7 12 18 26 35 45 56 69 …
If you have not read this book, your life and mind are the poorer.
7 Comments
Can you characterize the following set of integers:
8 14 23 34 42 50 57 65 72 79 …
They look like subway stops to me, although 65 should be 66 if thats what it is…
They are the stops on the 1 train — a friend of mine took a network security course at Columbia, and this was used as an example of a numerical sequence which is not reducible to an algorithm —
Sure it is:
1) get on the 1 train at downtown terminus
2) before the train starts, write down the name of the station
3) for each stop, write the name of the station at the end of the list
You just need the 1 train to run the algorithm.
One good nitpick deserves another!
Well, not so fast. An algorithm is defined as “an established, recursive computational procedure for solving a problem in a finite number of steps.” This sequence meets all of the criteria except for one: it is not computational. Even the NSA computers would not be able to find the pattern.
Well, we can argue about what an algorithm is, but it will get pretty tedious. The first definition I saw, though, when I googled the word was “A step-by-step method of accomplishing a task”.
But I can see why the sequence would be useful in the way you describe, and there’s no need to split hairs here. Never mind what I said about nitpicking above.
The “finite number of steps” (which is not, by the way, a necessary attribute of an algorithm) opens the door to a major issue in computer science: the Halting Problem.
I got the definition from dictionary.com — regardless of that, the point my friend’s professor was making is that in setting up network security protocols, there are advantages to picking sequences which aren’t a priori and hence are more difficult for others to infiltrate —
One Trackback
[…] I few days back I inked a post about Douglas Hofstadter’s fascinating book Gödel, Escher, Bach: An Eternal Golden Braid, in which I showed a little item from the chapter Figure and Ground, which is about recursively enumerable systems. The tidbit I offered was a most unusual number series. Here it is again, for those of you who didn’t see it the first time around, or who just passed it by without really thinking about it: […]