A Search Meme

David Ng of The World's Fair has been playing with viral marketing and Google bombing, and the experience has given him an idea for a nifty new meme. The way it works is this: Try to come up with 5 different search phrases for which, when entered into Google, your blog is the number one hit. The search phrase can be enclosed in quotes if necessary, but obviously it is even better if it works without the quotes. A commenter at David Ng's post (and by the way, read those comments at your own risk--some of them aren't pretty) suggests scoring the search phrases based on the number of hits. So, the ideal search phrase would have your blog being number one out of something like a million hits returned.

As it turns out, this is much easier to do than it might sound. Looking back at my previous post, Steven Pinker's formula gives an estimate of the number of distinct sentences one can utter, which comes out to be the enormous value of 10²⁰. Given that, it is perhaps not too surprising that we might have some catch phrases that appear more or less uniquely in our writing. (The key to getting the hit counts high at the same time is to have those catch phrases made up of a few words that individually are common.) So without further ado, here are some search phrases that (as of this writing) give this blog as the number one hit:

• intractable yet easy


• theory dilettante


• ultimate collector's ipod


• homage to procrastination


• decay unto death

Each of those searches returns more than 100,000 hits. I'll add one more search string for good measure, even though it only returned a few hundred hits, because it links to one of my favorite posts (and because at heart I'm a nasty person): Bringsjord parody.

So that's it. Consider yourself tagged if you're so inclined, and have fun playing with search strings!

What is your formula?

[Note: I goofed up in describing What is your formula? as an Edge annual question. It's not, and I've updated the post below to correct this.]

Edge Foundation does a yearly thing where they pose a question to an array of scientists and other intellectuals, and collect together all their answers. They have also had occasion to pose a question outside of the normal cycle, when after the 9/11 terrorist attacks they asked, What Now? Earlier this month, as part of a collaboration with the Serpentine Gallery in London, Edge posed another question to their collection of thinkers. The question was What is your formula? Your equation? Your algorithm? and browsing through the answers is a great way to waste an afternoon. Because the replies consisted mainly of diagrams and equations (many of which were hand-drawn), they are displayed as scanned images, which adds a personal touch to the results.

Unfortunately, the format of the question also limited the form the answers could take, most of which express some kind of heuristic relationship rather than a true formula. I did like this entry by psychology professor Danny Kahneman, which seems to explain a lot of popular culture.

As might be expected, the entries by mathematicians tended to have actual formulas in them. I can relate to the sentiment expressed by Nassim Taleb in his entry. Over a typeset page of equations on how to price stock derivatives, he hand-wrote, "I spent a large part of my life working on this equation. I am glad it is over."

Many of the entries were just plain silly. I'll single out this one by cognitive scientist Donald Hoffman, because of his abuse of mathematics. He has a nice diagram illustrating composition of functions that would make any algebra teacher proud, but follows it with a fallacious argument that shows he has not mastered basic logic.

Let me mention one more entry before I stop. Popular math writer Keith Devlin uses an analogy to speculate on how math will be taught in the future, and it looks like he would like to see virtual manipulatives taken to a whole new level.

Be sure to also check out the archive of annual answers to questions. Because they are not constrained by the "formula" format imposed on the current question, the answers are better developed and far more insightful.

Why I Blog

There's a new meme making its way through the blogosphere that I think I will indulge myself with. Although I have not been tagged (as usual) for the "Why do I blog" meme, I have come across it in a few different spots such as Aetiology and A Blog Around The Clock. This meme seems to me to be spreading more slowly than other recent memes, perhaps because the reason why people blog is often self-evident from their blogs themselves. Having said that, I can see at the Blog Meme Tracker that it has been spreading. (One problem with that page is that it doesn't seem to have any facility for adding 'dotted line' links for people like me who weren't officially tagged.)

I actually had a rather specific purpose in mind when I started this blog, so maybe this post will help focus my attention back on that goal. It is said that the best way to test, or reinforce, your understanding of a subject is to explain it to someone else. My hope was that by explaining computability and complexity theory in this blog as I worked through the material, I would force myself to understand the material at a deeper level.

It would also serve a secondary interest I have in pedagogy. One thing I've found while trying to self-instruct from reading textbooks is that often the most frustrating stumbling blocks are the most superficial. I probably spend more time trying to decipher unfamiliar notation than I do with trying to grasp concepts. In fact, although there certainly are some very deep and difficult concepts in TCS, a lot of the material would be quite intuitive if only it was taught in a more concrete fashion. A big part of the problem is that textbooks are not generally meant to be used in isolation; something that might take an hour to parse while reading a text can often be explained away in a minute or two by a knowledgeable teacher in the classroom. So another goal I have with this blog is to explain the things I'm learning in such a concrete fashion that, say, a motivated high-school student could understand it.

As an aside, I've noticed some other bloggers touching on pedagogical issues recently... Bill Gasarch talks about teaching binary search to 8-year-olds. More ambitiously, Andy Drucker ponders teaching topology to kids. Much more ambitiously, Andy has also been working on simplifying the exposition of the PCP Theorem. This latter item is definitely not for kids. I don't know the PCP Theorem, and by that I mean that I do not even understand the statement of the theorem. (I know there are relatively simple "high level" explanations of the theorem, but I am not convinced that they really get to the meat of the theorem.) This might actually be a good end goal for this blog: If I can learn the PCP theorem, and explain the proof here in terms that a high-school student could follow, then I'll know it's time to quit! (I am assuming this will come after I prove that P ≠ NP.)

I've drifted away from my goals with this blog. The main reason for this, I think, is that my usual mode of discourse is to respond to other people instead of initiating the conversation myself. As a result, I've been spending my on-line time mostly by reading and leaving comments on other blogs. (I don't often provoke responses from others, so I sometimes wonder if anyone ever reads those comments... I have to add a thanks here to Joshua at The Adventures of Tobasco da Gama for the positive acknowledgment!) But blogging is all about initiating the conversation, so this is something I am going to work on. I'm also going to try to stay a little more focused on the goal, instead of getting distracted by all those other shiny objects on the Web.

Now for our little exercise in distributed peer pressure. I'm not sure if I know 5 different people who read this blog, but let me at least tag a couple of people. Let's see... I'm too late for Tyler, but I can still tag Foxy. And Antztein, you're being worse than me with your posting--consider this an excuse to make another entry. I know she won't see this, but since I'm sure she's been thinking about it, I'll tag Kathy Sierra. Okay, Kathy, now you have to post again since you've been tagged. And to anyone else out in the aether reading this, consider yourself tagged too.

Academic Haiku

Jim Gibbon is holding a contest to see who can best describe a piece of academic research in the form of a haiku. You'll need to hurry though, because the deadline for submission is the 21st. (Hat tip to OmniBrain.)

My own submission is as follows:

There exist problems
intractable to decide
yet easy to check

For those of you who don't immediately recognize what that's describing, let's say it's for a yet-to-be-written paper entitled, "On an open problem of Cook".

Book Meme

There is a book meme making its way around the web, which I've come across at See Jane Compute and Afarensis (among other places). I've never been tempted to do one of these meme thingies before. However, the topic for this meme is certainly a worthy one, so here goes...

1) One book that changed your life?

There have been a lot of books that have shaped my life positively in some incremental way. For example, my responses below for items 2 and 4 in this list fit in that category. However, for something that was a catalyst for a more dramatic change, what comes to mind is a book that had a negative effect on me.

I read Hermann Hesse's novel Siddhartha, about the title character's spiritual quest for enlightenment, when I was starting high school. Afterwards, I dropped out of social activities at school and became very introspective. For someone who was introverted to begin with, this was not a productive change (and obviously I somehow missed the whole concept of the middle road). I never did achieve nirvana, but the choices I made back then still continue to shape my life in unintended ways.

2) One book you have read more than once?

For this item I choose Introduction to the Theory of Computation by Michael Sipser, which is arguably the best introductory text available on the theory of computation. While it's known for its easy-to-understand proofs of difficult theorems, what I like best about the book is its breadth of topics. It introduces subjects such as descriptive complexity and interactive proofs that are typically only covered in graduate level texts. I plan on reading this one again soon.

3) One book you would want on a desert island?

I suppose for a desert island one would want something that could take a long time to savor, like, say, the collected works of Shakespeare. On the technical side, something like Penrose's The Road to Reality comes to mind. But for something a bit more basic but with a lot more heart, I would pick Richard Feynman's The Feynman Lectures on Physics. This 3-volume set is based on the lectures that Feynman gave for an introductory physics course he taught at CalTech from 1961 to 1963. Of course, to properly appreciate these lectures, one needs to hear Feynman's own voice. For this, I think I'd prefer the iPod version.

4) One book that made you laugh?

Although it could fit just as well in several of the other categories on this list, Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid is as noteworthy for its sense of humor as for its ideas on logic, AI, and the interconnectedness of knowledge. The dialogues between Achilles and the Tortoise are hilarious.

5) One book that made you cry?

When I was young, I always used to cry at the end of the Charlie Brown Christmas Special, when Charlie Brown thinks that he's killed the Christmas tree. I still have a weakness for sentimental kid's stories, and one very nice one that I've read recently is Kate DiCamillo's latest book, The Miraculous Journey of Edward Tulane. Edward Tulane is a toy rabbit, and the plot conceit for this story is that Edward is a totally passive observer of his life--he is, after all, just a toy, and only moves when his owner makes him move. While it somehow made me think of panpsychism while I was reading it, anyone who has ever felt like a passive participant in life is likely to be taken in by this story. I balled my head off at the end of it.

6) One book you wish had been written?

I think it would be great to have a book which used Sudoku as a jumping-off point to teach about topics in math and computation. I've mentioned this before. In fact, I might be tempted to try writing something like this myself.

7) One book you wish had never had been written?

Well, after looking at what I've written so far, maybe I should pick Siddhartha. Instead, I'll choose An Introduction to the General Theory of Algorithms by Michael Machtey and Paul Young. This was the text used in the introductory theory of computation course I took in college. It utterly turned me off from the subject, and it wasn't until years later that I realized that this material can actually be exciting.

8) One book you are currently reading?

Explaining Consciousness: The Hard Problem, edited by Jonathan Shear. This book consists of the essay Facing up to the Problem of Consciousness by David Chalmers, along with responses by many other researchers in the field of consciousness. It gives a nice overview of the current thinking on the subject. More about the book can be found here.

9) One book you have been meaning to read?

My "To Read" list is pretty long, and I'll probably never get around to reading many of them. But the next book on my list is Programming the Universe by Seth Lloyd. This book treats information as a fundamental physical property of the universe. The connections between computation (as an abstraction) and physics are deep, and it makes me wish I had studied more physics back when I was in school. Maybe this book will help.

10) Now tag five people.

Well, I'm not sure I buy the tagging part of blog memes. If it's really a meme, then shouldn't it spread on its own without any overt action? Otherwise, you have something more resembling a chain letter. In any event, I'm not sure I know 5 other people who read this blog. So, if you're reading this, considered yourself tagged. But only if you want to be!

The ultimate iPod

Before I say anything else, let me just mention that I've gotten linked to for the first time! (Or at least, this is the first one that I'm aware of.) Woo-hoo! Thanks, Jeff/Ernie.

I received an ad for the following item in my email today:


Now if you've been meaning to get yourself an iPod, and you're a big Harry Potter fan, and you have a nice wad of money burning a hole in your pocket, you might want to check out this item at the Apple Store. (BTW, since these links will undoubtedly break at some point in the future, if you're reading this in the archives months from now, this ad shows the Harry Potter Collector's iPod with the Complete Harry Potter audiobook collection. The iPod has the Hogwarts crest etched on the back.) This ad reminded me of how I'm slowly assembling the ultimate collector's iPod. Let me explain:

A number of years ago I was browsing at my local bookstore and came across Richard Feynman's Six Easy Pieces. After skimming through the book, I bought it, but for some reason I never got around to listening to the lectures and it languished on my bookshelf. Maybe a year later I stumbled across it again and finally put the first lecture in my stereo. I was instantly mesmerized. I thought it was just incredible – if I had heard this while I was still in college, I probably would have changed my major to physics.

For those of you not familiar with it, Six Easy Pieces contains the introductory lectures from the The Feynman Lectures on Physics. These were recorded and transcribed from a two-year beginning physics course that Feynman taught at CalTech from 1961 to 1963. In trying to describe this, it's hard to do justice to the combination of sheer joy and absolute clarity that Feynman brought to the lectures. If you've never heard it before, you owe it to yourself to get ahold of the audio version of Six Easy Pieces and listen to it.

So anyway, after I listened to the introductory lectures, I immediately ran out and bought the (print version) of The Feynman Lectures on Physics. However, I quickly discovered that reading the printed lectures just didn't convey the same emotional impact as listening to Feynman speak. So I looked into getting the audio versions of the lectures and realized that there were a couple of problems. First, it would be very expensive to collect all the audio cassettes for the 100+ lectures. Second, the publisher for whatever reason had bundled the cassettes into sets of 6 which did not follow the ordering of the original course. So to listen to the lectures in order, I would have to buy the whole collection and then shuffle the cassettes around to get them into their proper places.

Well, a couple of things have happened since then. First, the publisher has slowly been converting the analog recordings to digital CD format (for example, here is the first set). They're now bundled into sets of 12, making them (somewhat) more affordable. The other thing that happened was the iPod phenomenon. And this gave me the ideal solution to how to manage all of that audio: I've been dutifully aquiring the lectures as they're released and transfering them onto my iPod. As I do this, I relabel the lectures so that they will appear in their proper sequence. Once all of the lectures have been converted to digital, I will finally be able to listen to them the way that they were originally delivered by Feynman. And the whole package will fit into my shirt pocket!

Once I'm done with this project, I think I'll have the back of my iPod etched with some nice Feynman diagrams to create my own "collector's edition."