## Wednesday, June 29, 2011

### How Computer Programs Work (When They Work!)

Just about everything, from telephones to toothbrushes, has a computer in it these days. Exercise bikes can be programmed to simulate flat beaches and mountainous climbs. (I assume sex toys will soon have similar features, if they don't already.) Coffee makers require rebooting, and microphones can automatically fix your off-pitch singing. Computers win at chess and Jeopardy. Can American Idol be far behind?

So what makes these machines so smart?

Actually they're not smart at all. Computers can only do a few very simple things. All the rest is a combination of those things, as arranged by some clever programmers. And the programs tend to involve a few stock ways of solving problems. Some of the basic problem-solving techniques are:

Repetition - Computers can do the same thing over and over again, very fast, without getting bored (as far as we know.) If you left a piece of candy in one box in a room full of thousands of boxes, the computer would be perfectly happy to look in each box, one after another, until it found the candy.

Condition Testing - If our computer is checking every one of the thousands of boxes in the room, and it finds the candy in the second box, we probably want it to stop looking. For that, the computer's program would contain an instruction like: If you find the candy, then stop. Of course, once you have the candy, you may not care whether the computer keeps on looking or not, and the computer will be perfectly content to keep checking boxes forever, or until it needs a software upgrade.

Recursion - Suppose that in this room of boxes, you might have boxes inside of other boxes, and boxes inside of boxes inside of boxes, etc. Think of a program called CheckBox as a set of instructions:
1. Look inside box
2. If the candy is inside, then stop.
3. Otherwise, if more boxes are inside, do CheckBox on each of those boxes.
In other words, the CheckBox program calls itself if it finds a box inside another box. That will work for boxes inside boxes inside boxes inside ... etc. up to any level. This is a very useful idea for problems that can be broken down into smaller problems, each of which is like a smaller version of the original problem.

Of course, if a person were doing the searching, and found boxes inside boxes, they would automatically look inside without being told. (Then again, computers don't have to be told not to eat a KFC Double Down sandwich.)

Parallelism - The part of a computer that actually computes is called the central processing unit (CPU) or simply processor. More recently, it's called a core, as in dual core, quad core, etc. Lots of modern computers have multiple cores, which means they can do several things at one time. So one smart way to solve a problem is to split it up so that each processor can be working on part of the problem.

It's like having several people search through that room full of boxes you've got. Naturally they'll find the candy more quickly ... but only if they're not all checking the same boxes! You have to make sure each one knows which boxes to check. It would also be nice if the one that finds the candy tells the others to stop looking.

There are lots of variations and combinations of each of these techniques, but these are the basics. Just about every computer program can be viewed as a sequence of these techniques. At some future date, when I really have nothing better to say, I'll discuss some of the kinds of problems programs solve, and how they use these techniques.