Fred Wilson argues on his blog today that Computer Science education should begin in middle school. While I agree that there should be CS classes in middle school, I would go even further than Wilson. These classes should start in elementary school, probably around third or fourth grade. Wilson's post references an article in today's New York Times that talks about improving CS education in high school. But Wilson argues for starting it even earlier. He says, "I remember the first time I wrote some code, hit compile, then run, and the computer did something I had instructed it to do. It was as Janice says "magic". I was smitten and have remained so almost forty years later." I couldn't agree more, but for me it happened much earlier (and I didn't have to compile, since it was interpreted BASIC :)).
When I was in elementary school, my parents enrolled me in after-school computer classes with an area math teacher who offered the classes in his house, on the side. (Those classes and that math teacher have since become somewhat infamous, but that's a whole other story, and I only had good experiences there.) In the classes we learned to write very simple programs in BASIC on the Commodore PET.
We weren't building search engines, but we were learning the basics of logic and syntax, two concepts that not only help introduce computer science but also come in handy for lots of other pursuits as well. (I was really good at Latin when I started learning that later on. Coincidence?) We also learned Logo both in these classes and in elementary school, and I'll never forget those ideas as well.
I'm no expert in education, but I think that you can introduce these ideas very early in a child's life. My 3 year old is already very good at working little gadgets (she was playing games and videos on my iPhone even before she turned 3). Kids are ready to absorb this kind of stuff as long as we provide it to them. If we start to teach them these things earlier in their lives, imagine what they'll do by the time they're in college.