The basis of one approach to the Theory of Computation is the idea of strings. Strings are nothing more or less that a series of symbols from a set of symbols called an alphabet. For examples, it's common to use predefined alphabets, like the Latin or Greek alphabets, or sets of numbers, like the set of natural numbers less than 10.

Quick aside one: For the less mathed out there, a set is just any group without duplicates. Your intuitive understanding of an alphabet is probably enough to grasp this one firmly. Consider: how useful would an alphabet be if there was more than one "a" in it? Do you mean cat or cat?

Less quick aside two: Okay, what exactly is the point of a Theory of Computation? Why would anyone care? Ask yourself this question: are there any problems that a computer can't solve? Answer: yes. But it's not the "what's at the end of an infinite series of divisions" or anything so Doctor Who as that. There's math that solves those problems perfectly, and computers are quite good at math. So, what is there that a computer can't do? That's the question that a theory of computation should solve. Along the way, we also start to see hints of things that a computer can do, but not very well, and how to quantify how well a computer can solve a problem. Which is important, because how else do you improve your solution? And without that sort of reasoning, we would never, ever, be able to play Counterstrike (the other CS).

Okay, back to strings. A string is a series of symbols from an alphabet. Well an good. What can we do with strings? Well, mostly we assemble them into languages. Drop immediately the notion that I mean C++, Python, Java, or Befunge. A language is a set of strings with this requirement: if a string X is in a language, then no prefix of X is in the language. So, a "language" { a, ab } isn't really a language, because a is a prefix of ab. (On the other hand, { b, ab } is legal. Suffixes are okay, just not prefixes.)

Okay, so now we have languages. What do we do with languages? We accept them.

Actual accepting of languages we'll talk about later. But one might be asking "why?" at this point. Okay, alphabets make strings make languages, and that's great and all, but I'm sure I'm begging the question "Is this leading somewhere other than Nyarly getting his pedantic rocks off?" Well, it comes down to, this guy Alan Turing suggested about sixty years ago that accepting languages was equivalent to solving problems. Or least they were strongly related. It's complicated, and we've got a ways to go, but that's basically what he said, and why it's hard to screw up a theory of comp. course too much. Then the government for which he'd won a war had him imprisioned as a homosexual, but that's another, also fascinating, story.

That's all for this week. Comments welcome.

As an Anonymous Coward replied to me, "NP completeness, Turing Machine, ect[sic]..." gets mentioned a lot on /. But what this coward was brave enough to admit was that he didn't really know anything about these things, although he was interested in CS matters.

Frankly, I think that many Slashdotters speak with a limited understanding of computer science, and to respond to that, I'd like to start using my own understanding as a springboard for a better understanding in general.

I'm leaving comments enabled so that criticism of my "lessons" might help to improve their content.

First lesson begins next journal entry.