Computation models 1: Introduction
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.