As my last post shows, I have the P vs. NP bug, and I have a poor memory.

While I’m not going to claim to have any chance of proving P != NP (since that would make me seem like just another Internet crank), I do think that amateurs can make contributions to the field of theoretical computer science. If modern computer science can be said to have begun in the 1930s with the work of Godel, Church, Turing and others, then the entire field is only 75 years old–just an eyeblink in historical terms. The theory of NP-completeness is only about 35 years old. Many introductory theory of computation textbooks cite the original papers for the main theorems. Can you imagine a Calculus text providing a citation for, say, the Mean Value Theorem? Theoretical computer science is in its infancy and is still taking shape.

Being an amateur, however, does not mean being untrained. To be able to contribute to the field, or even just enjoy it as a hobby, one needs to have training similar to a professional. Because computer science is so young, this is entirely feasible, unlike with most of the other “hard” sciences.

Now about this blog. In part due to my poor memory, and because I’ve been away from the subject for a while, I feel the need to go back and re-study the basics of the theory of computation. It’s hard to learn technical material by one’s self, however. It’s too easy to get bogged down by the formalisms, even when the underlying concepts aren’t necessarily that hard. The last time I undertook this task, I created a discussion group, Computer Science Theory, so I would be able to interact with others as I worked through Michael Sipser’s text, Introduction to the Theory of Computation. This time around, in keeping with the times, I’ve decided to try keeping a blog to track my efforts in understanding this material. I hope that explaining what I’ve learned in this blog will reinforce my own understanding.