Fun for Geeks

Some of you may have been wondering what L’s dad has been up to over that last month. Well, he’s been busy trying to survive another semester of grad school, one that’s quickly turning out to be more demanding than any he’s experienced so far. One of the courses he is taking this semester is called ‘Math Logic I’. It is, to use a variation of a common expression, kicking his backside.

Much of the material covered in this course overlaps material that is traditionally taught in the Math Department and the Computer Science Department. So far we’ve been exploring, in very abstract terms, what might be the limits on what a machine could compute. The results of this inquiry have interesting philosophical implications. I’ll spare you the philosophy lecture. What I will do, however, is share a bit about the part of the course I have enjoyed so far.

So far, we’ve discussed two very primitive sorts of machines: Turing Machines and Abaci (‘abaci’ is the plural of ‘abacus’). These machines can be thought of as primitive calculators; they can be programmed to execute various computations on numerical inputs. A Turing Machine can be thought of in the following way.

Imagine that you have a really long tape, one that is divided into squares of equal size (not unlike a roll of toilet-paper) and stretched out on the ground. Now suppose you have a little box on wheels that can move up and down the length of the tape one square at a time. Inside the box is a really little man with a pencil, an eraser, and a book of instructions. The instructions in the book read like the following: move one square to the left; if the square is blank, write a stroke; then go to instruction x. The box can only move one square at a time. The man in the box can only manipulate what’s on the tape in one of two ways: he can write a stroke on a square and he can erase a stroke that is on a square.

Now imagine you are given the task of writing up the instruction book for the little man. Different sets of instructions will make the machine do different things. Suppose you give the man in the box the following instruction: move one square to the right; if the square is blank, write a stroke and repeat the instruction; if the square has a stroke, repeat the instruction. This sort of instruction would make the machine write an infinitely long block of strokes–barring break-downs and the end of the world–extending off into the distance to the right. Other instructions are more practical. Suppose you wanted to make a Turing Machine that would calculate addition for you. You would write up some intructions for the man such that, when you made two blocks of strokes on the tape beforehand, the machine would go to work on the two blocks of strokes and, when the machine stopped working, the single block of strokes remaining on the tape would be the sum of the two blocks of strokes you wrote on the tape at the outset. Suppose you wanted to add 2 and 3. Before you started the machine, the tape would look like ‘_,_,I,I,_,I,I,I,_,_’. If you wrote up your instructions properly, when the machine stopped the tape would look like ‘_,_,I,I,I,I,I,_,_’. You could write up separate instructions for every two numbers you wanted to add, but that would be extremely time consuming. You would probably just be better off doing the calculations yourself. But if you could write some instructions such that, no matter what two numbers you “wrote on the tape” beforehand, the machine would calculate their sum for you, you would have a time-saving device.

As part of my homework for this course I’ve had to write detailed, explicit instructions for Turing Machines. I’ve written instructions for various Turing Machines: one that doubles the number of strokes on the tape, one that adds two numbers together, one that subtracts two numbers, and others. An abacus is a slightly different machine, one that has Random Access Memory. Again, I won’t bore you with the details. If you’re interested, ask me about it sometime. Working on designing these sorts of machines has been fun. If only the rest of the material in the course was as much fun.