# 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 * 5*y* = 12*y* = −3*x*?

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.