Bits & Bobs

The title of ‘father of computing’ is usually assigned to Alan Turing. Before him Babbage had sketched ideas for his Analytical Engine, but had not proved anything about its operation. Alonzo Church had created his Lambda Calculus formalism, but the computation (beta reduction) still had to be performed by hand. It was Turing who considered a physical machine for performing computation, studied the machine mathematically and then build some.

Turing’s approach was to think of a mechanical Mathematician. He thought, what is it that Mathematicians actually do when they perform Mathematics? Well they sit in front of a piece of paper containing some Maths, for example it might be the statement of a problem like:

x + 2 * 5y = 12y = −3x?

Turing argued that a machine would find it easier to read such things if, rather than having a variety of notation styles, the symbols used could be written neatly instead; for example by writing one symbol in each square on some squared paper.

x + 2 * 5 y = 1 2
y = - 3
x ?

Next he said that we don’t really need a 2D sheet of squared paper, we can do it in 1D if we have some symbol for a new line, like ;. Thus our Maths becomes:

x + 2 * 5 y = 1 2 ; y = - 3 ; x ? ;

Now, which symbols should we use? If we want to build a machine then we want as few as possible, to keep things simple. Turing noted that rather than giving everything a unique symbol, they could be given labels based on a number of simpler symbols, like writing “10” instead of “x” for example. Thus we can say “10” means “x”, “11” means “y”, “12” means “+”, “13” means “*“,”14” means “=”, “15” means “;”, “16” means “?” and “17” means “-”. Now our problem looks like:

10 12 2 13 5 11 14 1 2 15 11 14 17 3 15 10 16 15

Now it’s getting confusing: we’ve got things like 1 2 as well as 12, how can we tell the difference? We do it by making every number 8 digits long, filling any unused digits with 0. This gives

00000010 00000012 00000002 00000013 00000005 00000011 00000014 00000001 00000002 00000015 00000011 00000014 00000017 00000003 00000015 00000010 00000016 00000015

Now that everything is written using only numbers, all in a straight line, in groups of 8, it’s looking much more likely that a machine will be able to read it mechanically, since it only needs to know how to read 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. In fact, we don’t even need to use all of these, since it’s entirely possible to write numbers with only 0 and 1, which is called binary (as opposed to digital) Maths. So we can rewrite the above problem converting each 8-digit-long digital number into an 8-bit-long binary number:

00001010 00001100 00000010 00001101 00000101 00001011 00001110 00000001 00000010 00001111 00001011 00001110 00010001 00000011 00001111 00001010 00010000 00001111

Of course, I’m also using spaces () to make it clear where one number ends and the next begins. Since they’re all 8 bits long I don’t need to do this, so our final, simplified problem is written as:

000010100000110000000010000011010000010100001011000011100000000100000010000011110000101100001110000100010000001100001111000010100001000000001111

Now our machine only needs to be able to tell the difference between 2 things, 0 and 1. Of course, we don’t need to write them down on paper as 0 and 1, we can use anything that can be in one of two states. For example we can use the magnetism of a piece of metal, which can point in one of two directions (this is used in hard drives); we can use switches, which can be either on or off (this is used in RAM and USB drives); we can use the reflectivity of a surface, which either reflects or doesn’t (this is used in CDs and DVDs), and so on.

Now that we have a mechanical device that reads our incredibly simplified Maths notation, what does it do? Turing argued that brains aren’t magical things: people just follow certain rules that they’ve learned, or even things that they’ve read further back on the page. Thus people go forwards and backwards over the page, changing the contents of their brain as they read, and occasionally writing something down. Thus Turing’s machine just has to go forwards and backwards over its zeros and ones, called “the tape”, performing certain actions based on what it reads, and occasionally writing to the tape (setting a bit to be 0 or 1). The actions it takes define the machine, and Turing proved that some sets of instructions are able to mimic any other set of instructions. These types of machine are called Universal Turing Machines, and Turing proved all kinds of interesting things about them, for example that it’s impossible to know for certain whether a given machine will ever run out of actions to take or not (known as the Halting Problem).

An illustration of Turing’s machine is shown above, and Turing and Church showed that Universal Turing Machines are just as good at Maths as Church’s Lambda Calculus, ie. they can solve exactly the same problems. They put forward the argument that many other things can solve those exact problems too, but that nothing exists which can solve more than those. This is known as the Church-Turing Thesis, and was proved recently by Yuri Gurevich. Thus Turing’s simple little device, trundling back and forth over its tape, is actually the most powerful computer in the world. Of course, it’s in joint-first-place with every other computer, since the machines we use every day are equivalent in power to a Universal Turing Machine; they are known as Turing Complete.