Computational models 4(a): Turing machines
In my last post on computational models I finished with a question. I had introduced the concept of a finite state machine, and then a pushdown automaton - essentially a finite state machine with a simple memory. The memory was represented as a ‘stack’, where only the top item was visible.
My questions was - does adding more stacks to a system make it more powerful? Is there something which a two-stack machine can do which a one-stack machine can’t? The answer to that question is a resounding Yes. So let’s investigate the limitations of a one-stack machine and how two stacks help us overcome them.
Two stack automata
I mentioned previously that a pushdown automaton can record values in its stack for later. When the automaton reads some input it has a choice: to store it on the stack for later, or discard it immediately. If data is stored then it is available for later use, but not forever. To get to things stored further down in the stack then stuff on the top has to be moved elsewhere. Alas, there is no elsewhere, so it must be discarded.
This is the problem of a one stack machine. It’s like a book that erases itself if you flip back through the pages. We have no way of going over the same data repeatedly, only once. So the answer is to ‘pop’ data off one stack and ‘push’ it onto a secondary stack. If we want to get it back again, we can push it back to the main stack.
Now, with two stacks, we have sequential access to all the values in memory. We can examine the contents of one stack by repeatedly pulling values off and putting them on the other. We can shuttle values left and right at will and we don’t ever have to discard any. And that is a big advantage.
Two stacks, or one long tape
Imagine a state machine that, instead of accessing values on a stack like the pushdown automaton, could read and write values onto lengths of tape, sectioned off into squares. Imagine that each square held a symbol which could be somehow overwritten by the machine. It’s a bit like a tape player, with a read/write head and the ability to step to the left or right through the tape.
This is not really any different from a two-stack pushdown automaton. We only have to imagine that all the tape on the left side of the machine is in one stack, and all the tape on the other side is in the other stack.
This notion of a machine which reads and writes tape was conceived as a thought experiment by Alan Turing in the 1930s. Consequently it is known as a Turing machine. His machine was designed completely on paper. It is not a real machine, but it’s very close to one.
The Turing machine in action
The Turing machine is conceived as a state machine with a tape head. The ‘program’ is built into the machine, in the rules which the state machine embodies. The input is written on the tape to start with. The very first square of the tape is inserted into the machine and the calculation started. The tape head moves left and right, reading and writing values. The tape has a definite left edge but not definite right edge - the thought experiment stipulated that the Turing machine shouldn’t run out of space to store values.
A Turing machine performs calculations by reading input from the tape and writing intermediate and final results to the tape. When it is finished it will enter a ‘halt’ state, and stop. At this point whatever is written on the tape is the result of the calculation.
Nothing more powerful
Believe it or not, we have reached the end of the road. To answer the second of last week’s questions - adding any more than two stacks doesn’t gain more power. Everything which can be calculated can be calculated with a Turing machine.
I’ll just let you think about that for a second. A Turing machine with two tape heads and two tapes is equivalent to the bog-standard machine. One with hundreds of tapes (imagine a whole sheet of squared paper) is equivalent to a ordinary Turing machine. In fact, one with infinite tape in both directions is no more powerful. All these fancy things can be emulated on a normal Turing machine.
As a quick example, look at a machine with two read/write heads and two tapes. Well, each square on a standard tape could in fact be split into two, instead of using two separate tapes. Then we could read both squares with one tape head. We could program the machine to read both squares before deciding what to do next. So the only difference between a 1 and 2 tape machine is the complexity of the rules that work it.
A Turing machine is easier to imagine than any other of the computational models mentioned so far. Partly, I suppose, because of the precise description from Turing’s original proof, but also because they so closely resemble real computers. So much so that you can play with a simulated Turing machine which allows you to paint squares. Have a play. I’ll be back soon to talk about some really crazy stuff…