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!