Carnival of Mathematics

I was just thinking to myself that it's been a long time since I've seen a new Carnival of Mathematics, and sure enough when I checked the calendar I found that the 11th edition is now up at Grey Matters. Hmmm, none of the math/cs blogs I read regularly posted any announcements about this; how am I supposed to remember these dates on my own? Maybe everyone is on vacation this week.

Perhaps it's just the summer doldrums, but this edition of the carnival seems a bit thin. There was a little bit of discussion back in the 10th edition about whether it might make sense to split into two separate carnivals: one for math ed and one for college and research level math. However, the current edition is almost all math ed, so perhaps the carnival will just evolve in that direction on its own. (There were also a couple of entries that really left me wondering what the authors were smoking, but that's another matter.)

There was one entry that struck me as being worth mentioning, though. John Armstrong at The Unapologetic Mathematician writes about categorification: the process of recasting a mathematical abstraction into the language of category theory, as a means of solidifying one's understanding of the topic. He gives some simple examples expressing addition and multiplication in terms of set operations, and reinterpreting the results in terms of category theory. As someone who doesn't know anything about category theory, I find this both intriguing and mystifying. He concludes his post with the adage, "If you want to understand something, try to categorify it!" I think that I first need to understand categories, and Armstrong has a series of posts on the basics of category theory that might help me in that regard.

While we're on the topic (sort of), I wonder if it would be worthwhile to try to split off the TCS-related posts from the Carnival of Mathematics into their own carnival? That might sound a little strange seeing as how there were exactly zero computer science posts in this edition, but I'm thinking that having our own carnival would encourage more submissions. Or is the TCS blogosphere so small (and we already read each other's blogs anyway) that having a carnival would be superfluous?

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.

Blogger Twilight Zone

I have in the past thought that, the only features that Blogger was lacking that I really missed were the ability to categorize posts and to set up feeds for the comments. So, when the new version of Blogger came out with these features now supported, I figured my blogging life was complete.

Unfortunately, in a twist of irony reminiscent of a Twilight Zone episode, the new version of Blogger is apparently incompatible with my domain host, so any new blog entries may never show up where you can read them. Likewise, you can post comments if you wish, but it is highly questionable if they will ever appear on the main blog entry.

If the situation doesn't resolve itself soon, I might have to switch over to WordPress (which is something I probably ought to do anyway, but I've been lazy about).

P.S. These changes might cause old posts to reappear in the feed stream -- my apologies in advance for any irritation this causes.

Moving

It's now been more than 3 months since I last updated this blog, which is far too long even given the subject matter of my last post. The reason is that my family and I just moved from Pennsylvania to Florida. For most of the past month my computer has been packed away in shipping cartons, and for the two months prior to that, I was too preoccupied with preparing for the move to do much with the blog.

Our new home town is Tallahassee, and as I get familiar with it, I'll post about any noteworthy things I learn. My most immediate concern has been with downsizing. Our new home has much less storage than the old one (due mainly to the lack of basements in Florida houses), forcing me to get rid of any material possession that didn't get used enough to justify the floor space it occupied. I'm also using the opportunity to sort through boxes of papers and reorganize my files. The effect has been rather liberating. Although it has brought my productivity to a standstill in the short term, I think ultimately this simplifying of my life should help greatly with that whole procrastination business.

Going almost a month without surfing the Web has also proved to liberating. I find, now that I am back online, that a lot of the sites I used to spend time following just don't seem as compelling anymore. I should make use of this opportunity to break myself of a few bad habits. (Note to self: I need to update my template to get rid of that "Next Blog" button at the top of the page.)

I still have a few move-related chores that will be occupying of my time for a while, but I hope to get back to thinking about computation soon. In the meantime, if you know anyone who's looking to buy a home in Erie, Pennsylvania, please send them my way!

Cascading style sheeeeeit

Hello again,

As I mentioned a few posts ago, when I decided to set up this blog on its own domain, one of my goals was to have an accompanying website where I can collect various resources relating to theoretical computer science. There is a limit to how many links you can stuff into the sidebar of a blog.

I initially was using some old html that I had left over from several years ago for the website. The overall structure was frames-based, and it used tables to provide some of the formating. (At the time when I originally wrote it, CSS was not yet in widespread use.) So I decided that before I start adding content to the site, I better rewrite it using current techniques.

I went to my local bookstore and selected a book on HTML and CSS, and began working through it. The first thing that struck me is that HTML itself is pretty much unchanged from 6 years ago. The other thing is that web design nowadays looks nothing at all like what I was familiar with. Well, I dutifully worked through the examples in the text, created a simple layout with a masthead, sidebar and main body area, and tried it out. It was utterly unreadable. I also found that making (seemingly) minor tweaks to the CSS resulted in drastic changes to the layout, with the sidebar switching sides, the contents disappearing from view, and other generally bad things happening.

Finally, I punted. I copied the CSS from my Blogger template and stripped out most of the Blogger-specific stuff, and used that. Eventually I'll learn how to properly use CSS (I've got a new, better book to read) and redo the site, but for now it's workable, and aesthetically it matches the blog.

Since I was tinkering around with the Blogger template anyway, I also went ahead and added some tweaks to that. Recent comments now appear in the sidebar, and there are trackback links (via Technorati) at the bottom of each post. Now I just have to wait for someone to link to a post so I can try it out. I promise that my next post will deal with something actually connected to theoretical computer science, so there might be some content worth linking to!

Blogging 101

Hi again everyone,

Well, I'm sad to say that I've spent most of my free time for the past week just learning the basics of blogging. The Blogger interface itself is intuitive and you can pretty much just learn it as you use it. But as with other technological innovations, there is a temptation to fritter away one's time by endlessly tweaking the interface. So far I've done only the very basics, by adding some links to my sidebar and registering the blog with Technorati, a company that indexes and tracks links between blogs. Blogger maintains a page called BloggerHacks that includes code you can add to your blog template. One neat thing you can do is to add a 'recent comments' section to your sidebar in a fashion similar to the 'recent posts'. I'll have to implement that one when I have the time. Something else I've come across that I want to add to this blog are trackbacks. A trackback is essentially the inverse of a link — it shows who is linking to your page. Probably no need to hurry on implementing this one, though, since at the moment there probably isn't anyone else linking here at all.

For those of you for whom this is all old hat, please excuse my naiveté. I tried looking in a few books on blogging for the technical details of this stuff, without too much luck. It seems the best way to learn the details is by looking at other people's blogs. One of the best examples I've come across is The Geomblog by Suresh Venkatasubramanian. Lots and lots of technical goodies on Suresh's blog. Of course, I don't want to make it seem like the technical glitz is more important than the actual content of a blog. From the point of view of helping one to learn theoretical computer science, I think the best blog by far is Lance Fortnow's Computational Complexity, which is on the low end of the 'glitz' scale.

One downside of the time I've spent playing around with the blog is that I haven't actually studied any TCS in the past week. I'm starting to feel withdrawal pangs. But reading blogs and randomly following links from blog to blog is extremely addictive, more so I think than for regular Web content.

Here's a real nice goody I came across in my travels: ASCIIMathML is a JavaScript utility that will dynamically transform LaTeX-style math formulas in a web page into MathML markup. This looks like a very promising solution to the problem of how to render mathematics on this blog. I'll be trying this out in a future post. Of course, the reader still needs to have their browser configured properly to display MathML, but presumably someone seeking out a computer science blog would be able to take care of that.

New Home

Just a short post tonight to point out the obvious, which is that this blog now has a new URL and a new name: Learning Computation.

I was thinking about the fact that eventually there may be a lot of images embedded in these posts, and there needs to be a place to store those images (which is something that blogspot doesn't provide). I didn't want the location to be tied to my current ISP or some other domain that is subject to change, so I decided to create a dedicated domain name for the blog. This is amazingly easy and inexpensive to do nowadays. Even so, when it came time to enter the domain name in the application form, I had to pause for a moment and think about the purpose of this blog, and I decided to change its name slightly to broaden its scope.

You may have also noticed the accompanying website. Please excuse the roughness of the design; it should improve greatly over time as I develop it. This is where I plan to put links and other kinds of resources for theoretical computer science. If you know of any great sites that you'd like to see linked there, please pass them along to me. (And thanks, Troy, for the links you've already sent me. I'll be adding them when I have a chance.)

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.