I mentioned in my last post on computational models that a Turing machine is the pinacle of computational power. There is nothing that can be computed that can’t be computed by a Turing machine. The only limit is the set of rules (the states and transitions) used by the Turing machine.

But there’s one thing we haven’t really broached yet. One problem which none of the machines have been able to solve until now. That problem is generality: the point where a machine dedicated to a specific problem becomes a fully programmable computer.

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.

The general trend of this series of posts is about slowly adding features to the idea of a machine until it becomes as sophisticated as we can make. Last time I mentioned the finite state machine, the simplest possible abstraction of computation.

A finite state machine is nothing but a table of rules. It can only act on an input or not, and there is only one input that it can analyse at a time. This isn’t really as sophisticated as we want. We’d like to have a notion of memory for our computer. We should be able to store results somewhere and change behaviours depending on the contents of our memory.

I said we were going to build some computing machines. For the first example we don’t need to imagine anything, since your house will be full of this type of device. The most basic computing machine we can build doesn’t even need electricity or movement.

It’s hard for most people to think about things abstractly. People understand abstractions only by generalising from specific examples, rather than learning the abstraction first. It’s difficult to say what the idea of a chair is, for example, but if you’ve seen enough examples you can form your opinion. You begin to generalise and so don’t make a fool of yourself when you visit a new restaurant.

Building machines in the garage

Mathematics often seems to be all about dealing only in the abstract. The work of early twentieth century mathematicians was particularly aimed at defining maths purely in abstract terms — to divorce it entirely from notions of measurement and counting. They were ultimately unsuccessful, but it is definitely true that modern mathematics is not about counting sheep or weighing grain.

And yet even real mathematicians hanker after the physical examples, the concrete. Once you have answered a question in general terms, it’s a matter of putting flesh to the ghost. A furniture designer knows what a chair is and what it must have. The excitement comes in creating a new example of a chair that no-one has seen before. The same is true with mathematical ideas.

Defining computation

To compute, simply enough, is to process an input to produce an output. People wondered about the limits of computation: could a process be found to answer any question? Intuitively one would say no, but that won’t advance the field of human understanding. How much is no, and what questions come into the category yes?

Boil the question down to its essentials. There is a process, so in theory there should be a processor — some machine to carry out the task. How about we design this machine? There will be steam and shiny brass knobs, I hope.

So in the next few weeks I hope to write about this machine. We will go through many iterations, adding features and redesigning from scratch. Eventually we should reach the point where every new gizmo we add to it doesn’t actually make it more powerful. Then we will have reached our answer — a processing machine which can compute everything computable.