How I became a theory dilettante

In a recent blog entry, Lance Fortnow describes how he became a theorist. It seems that he started out in college as an engineering student, but switched to math because he was turned off by the, uh, pragmatism of engineering. But it was an introductory TCS course by Juris Hartmanis that really set him down the theory path. In a response on his blog, Suresh describes how he came to TCS by way of AI.

During my first couple of years of college, I tried a number of different subjects including engineering, but ended up in math because I couldn't really decide on a particular discipline. I figured that with a math background, I would be able to do pretty much anything after I left school. I had always had an interest in computers and programming, but more along the lines of numerical analysis than TCS. Computing was a tool for carrying out mathematics and not the other way around.

I did take an introductory TCS class in my junior or senior year that was offered by the math department. (The CS program at my school was run through the engineering department, so this was something apart from that.) Unfortunately, the course killed any interest I had in TCS. The text we used was An Introduction to the General Theory of Algorithms by Michael Machtey and Paul Young, which has a very abstract, recursion-theoretical feel to it. Although the text did include an introduction to complexity theory, our course was pretty much limited to computability. The subject seemed to me to be totally detached from any practical applications for programming. It was pretty dreadful.

I was, however, interested in AI after reading Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid. But the more I read up on AI, the more it seemed hopelessly unable to explain what intelligence (or consciousness) was, and that it would probably stay that way during my lifetime. So after a while I lost interest in AI as well. (By the way, I no longer feel this way about AI. I am very excited by the approach outlined in Jeff Hawkins' book On Intelligence.)

After graduating, I eventually wound up working as a programmer for an insurance company. But I missed the collegiate environment, and one day I noticed an ad by University Video Communications for a series of videotaped lectures on various topics in computer science. I ordered "The Shortest Network Problem" by Ronald Graham, and was immediately hooked on the question of P vs. NP. In the lecture, Dr. Graham gave as a reference the Garey and Johnson text Computers and Intractability: A Guide to the Theory of NP-Completeness, which I ran out and purchased from my local bookstore.

Now, studying this kind of material on one's own is not particularly easy, and I probably wouldn't have gotten very far with it had it not been for the other big influence at that time: the Internet and the World Wide Web. Being able to interact with others over the net, as well as being able to access scores of TCS web sites has made an incalculable difference in learning this subject.

I need to mention one other important influence. There are hundreds of introductory theory of computing textbooks out there, many of which are excellent. But it is hard for me to imagine learning this material from anything other than Michael Sipser's Introduction to the Theory of Computation. This book has made learning TCS fun.

That is where the story ends, which is why the title to this entry reads the way it does. For now this is just a hobby for me. Perhaps one day that will change, and then I can write about "how I became a theorist".