Where to start?

To reiterate from my last post, my goal for this blog is to use it as a sounding board for my studies in the theory of computation. I plan to regurgitate whatever I've been reading, in the hopes that by summarizing and explaining it here, my own understanding will be enhanced. If I do a good enough job at explaining things, perhaps it will be useful to some of you who are reading this. Please feel encouraged to leave comments. I've found in the past that much of my learning occured while attempting to respond to questions from others.

Before I can start on this endeavor, there are a couple of issues I need to deal with. The first is where to start. I sometimes feel that I ought to go back to the very beginning, and start with calculus and linear algebra and related math stuff. I haven't used any of that since leaving college and I've forgotten most of it. As a practical matter, though, I don't want to spend the time it would take to work through all of that. Any bits and pieces that I find that I need, I can relearn as I go along. More specialized areas of math such as logic or graph theory, that appear heavily in certain areas of theoretical computer science, might be worth studying in depth. But I'll wait until I need these before undertaking this. For now, I think I'll begin with an introductory text in the theory of computation. There seem to be literally hundreds of these to choose from, and I'll spend some time looking at the choices in future posts. For now, let me just say that I have a copy of the new edition of Sipser's Introduction to the Theory of Computation, and that will be one of my main resources.

There is another, more basic issue I have to address, and that is how to deal with the technical details of how to communicate with you. Using Blogger should be easy enough, but since I haven't done this before I will need to spend a certain amount of time learning the Blogger interface and refreshing my memory of HTML. Then there is the question of how to handle mathematical notation. For simple equations, I could make do with features of vanilla HTML, like writing &sub for the subset sign ⊂. Clearly this won't work well for more detailed expositions. MathML was designed to handle this sort of situation, and I'll probably spend some time playing with that. My inclination, though, is to use LaTex and save the output as a PDF file which I can post. Since I haven't used LaTex before, this will give me a whole new subject to write about on this blog.

About this blog

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.

Welcome

Last night I figured out how to prove that P != NP. Well, okay, not exactly. I didn't have a "Ureka!" moment where I suddenly understood what technique to use to show P != NP. What did occur to me was a general approach that, with a lot of time and effort, might conceivably lead to a proof. This was while I was lying in bed near to being asleep, which is when a lot of my ideas seem to come to me. My first thought was that I ought to get up out of bed and write down the idea, so I could explore it some more in the morning. Maybe do a Google search and see if anyone else had already published anything related. However, I was awfully tired at the time, and the bed was awfully comfy. Also, my late-night brainstorms have a history of looking nonsensical in the light of day. While I was debating the matter with myself, I fell asleep.

As you have no doubt already guessed, I do not remember what the idea was. Perhaps I'll remember it at some point. More likely, I'll think it up again one day in the future, but won't realize that it's the same brainstorm I had last night. My fear is that this cycle will keep repeating itself, and like the protagonist in the movie Memento I'll be doomed to rediscover the idea over and over without ever being able to remember it. From now on I'm keeping a pad and pen on the nightstand, and writing everything down no matter how silly or insignificant it might seem.