## Tuesday, March 28, 2006

### Playing with mathematical machines

In computer science, one of the tricks that we like to play is to talk about imaginary machines, in order to use them to think about what computing machines can do, and what the limits of mechanical computation are. One of the most fundamental of these is called the Turing machine, after its inventor, the great Alan Turing.

There are actually a few standard variants of the Turing machine, so the particular version that I'm going to talk about might be very slightly different than what you'd see elsewhere; but this is the version I find easiest to understand.

A turing machine is a very simple machine, but it's capable of computing anything that can be computed by any mechanical computing device. A turing machine consists of four real pieces:
1. A set of states, one of which is the initial state - the state that the machine is in when you turn it on.
2. A set of symbols.
3. A transition function from a pair (state,symbol) to a triple (state, symbol, direction). [direction is either "forwards" or "backwards"]
4. An infinitely long "tape" made up of cells, each of which can contain exactly one symbol.
5. A head, which can point to a single cell and read the symbol in that cell, and write a symbol onto the cell replacing whatever is there. The head can also move.
The way that a turing machine works is really simple. You write something onto the tape - that's the input to the machine. You position the head on the very first square of the tape. Then you turn it on. Each step, it looks at the symbol on the cell under the head. Then it calls the transition function on the pair of the current state and the symbol under the head. It gets back a triple: a new state, a symbol, and a direction. It changes its state to the new state, writes the symbol onto the tape, and moves once cell in the indicated direction. And it keeps going.

And that is it. Any program that can be written, anything that can be computed, can be computed with something that simple. Hard to imagine, isn't it?

So let's take a look at a few examples of Turing machines.

Here's a simple turing machine that does subtraction, based on a program for a turing machine simulator I found online. It uses unary numbers: any number n in unary consists of a string on n 1's. So 6 would be "111111", 3 would be "111", etc. It starts with a tape that looks like a subtraction problem: "x-y=", where the X and Y are unary numbers. So, for instance, 6-3 would be put on the tape as "111111-111=". After the machine runs, what's left on the tape is the answer in unary, plus some blank space.

The set of symbols that we can have on the tape are: "1", " " (blank), "-" (minus), and "=". The

The machine needs 4 states, plus a special fifth to indicate that the machine has stopped, called the HALT state.

The state transition function is in the following table:
(State,Symbol) (State,Symbol,Direction)
(1, " ") (1 , " ", forward)
(1, "1") (1 , "1", forward)
(1, "-") (1 , "-", forward)
(1, "=") (2 , " ", back)
(2, "1") (3 , "=", back)
(2, "-") (HALT, " ", back)
(3, "1") (3 , "1", back)
(3, "-") (4 , "-", back)
(4, " ") (4 , " ", back)
(4, "1") (1 , " ", forward)

Now, it looks pretty mysterious looking at that mess. So here's an explanation, and follow the link above to actually watch the program run.
• The machine starts on the leftmost cell, which contains the first digit of the first unary number.
• In state one, it scans forward until it finds a "="; while going forward, it never changes the symbol
on the tape - it writes whatever it read.
• When it finds an "=", it switches to state 2, and reverses direction.
• In state two, it scans backwards one space, and if there's a "1" there, that means it's not
done subtracting, so it erases that one by moving the "=" back one space; and then it shifts to
state 3. If there's a "-" on the cell instead of a "1", that means it's erased all of the digits of
the second number, so it's done, and halts.
• In state three, it scans backwards over the rest of the "1"s in the second number of the tape, until it gets
to the "-" that separates the two numbers. Then it switches to state 4.
• In state 4, it scans back over and blanks until it finds one of the digits of the first number; when it does, it erases it by replacing it with a space, and then it switches back to state 1.
So how is this subtraction? Basically, it's scanning forward, finding the last digit of the second number, erasing it, and then erasing one digit of the first number; and then it repeats until there are no digits left in the second number, at which point it erases the "-" and the "=", so there's nothing left but the answer.

So let's see what it looks like running. Here's a picture of a turing machine executing each step; the floating box is the head; the arrow points at the current tape cell; the number inside the head is the current state.

• Starting at step 1, the machine is in state 1, and it goes forward each step in state 1 until it reaches the equal sign in step 8.
• In step 8, it writes a space (deleting the "="), and starts going backwards, and goes to step 2.
• In step 10, it looks to see if there's a one under the head. If there is, it's not done subtracting yet. So it writes an equal sign down, switches to state 3, and and keeps going backwards.
• Starting at step 11, state three runs until it finds a minus sign, and then switches to state 4. That doesn't take long: it finds the equal right away.
• State 4 skips over spaces until in finds a one: then it erases it, switches to state 1, and starts scanning forwards again. It switches to state 1 right before step 13. At this point, now, instead of having the tape read "4-2", it reads "3-1".
• It repeats the process to get rid of a digit from each of the numbers on the tape in steps 13-21.
• Finally, there are no more digits in the second number - it's been erased. So in steps 22 and 23, states 2 and 3, it erases the "=" and the "-", leaving just the final answer on the tape, and then it halts.
One important thing to notice: this turing machine is hard-wired - it's a machine that does exactly one thing. It can't be changed or reprogrammed, because it doesn't have a program. The state transition table is part of the hardware of the machine. So in a very important sense, this is a very limited machine: each turing machine has a "program" hardcoded into it: it can't be "reprogrammed", because it isn't programmed at all. It's just built with those states, and those actions.

But here's where Turing got really clever. What if you were to build a turing machine which understood turing machines? That is, what if you built a machine which took as input the state transition table for any other turing machine?

That's called a universal Turing machine (UTM). And while it was far from easy for Turing to design one (his first publication of the UTM had an error in it), hackers since then have played around with UTMs, and it turns out to be not that difficult to do (once you've seen how it's done). Last I checked, Minsky had the record for the smallest UTM, using 7 states and four characters. (You can see Minsky's machine at mathworld.) Since then, Wolfram apparently came up with a 2-state 5 character UTM!

• That was a remarkably concise explanation of turing machines, but I still wonder whether the first step is maybe something that needs to be expanded upon. I've tried, several times, to write an introductory piece for the idea of the turing machine but can't.

I suppose I just gotta keep trying. It's one of the most elegant and clever ideas that could possibly exist, and more people deserve to know about it.

If this isn't a strange question, what's your popularity like? Are you getting many hits? I'd like to see sites like yours get more visibility but I wasn't sure how popular you are already. And also been wondering who your visitors are — are they mathematicians and computer scientists that are trying to get a better idea of how to explain the subject to the layman, or are they lay readers?

By  Ithika, at 1:53 PM

• Very neat. I just received a book about theoretical computer science today, so it fits unusually well with what I am currently fiddling with.

I am a PhD chemist, with a moderate math (undergraduate minor) background, some interest in philosophy using symbolic logic, and a lifelong interest in things computer-related. I am a motivated amateur in math and computational things. I come here and learn stuff, or get pointed in interested directions.

By  ScienceDave, at 12:14 AM

• ithika:

I'm averaging somewhat over 400 visits a day, which quite frankly amazes me.

It's kind of hard to tell who the readers are. Based on comments and email I've gotten from readers, I think that most of the readers are people with some sort of scientific background, but not mathematicians. There's definitely a group with really strong math backgrounds, but I think that they're a relatively small portion of the readership.

By  MarkCC, at 8:13 AM

• I am a mathematician, but I only pop in once in a while (usually due to links from Scienceblogs). The math here is far too concrete and real-world for an algebraic geometer like me. :)

By  Davis, at 12:38 PM

• I'm doing an undergrad in cog sci with particular interest in linguistics, AI and neuroscience. Heard a lot about the Turing machine and understand where it stands on the Chomsky Hierarchy and stuff, but this is the first time I've (I think) really grasped what it is. So, I guess this site is aimed at people like me...? Anyway, from what I've seen so far, it beautifully fills a gap that I've been trying to get across just by (often blindly) reading as much as possible.

By  Tris, at 4:28 PM