---
title: 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=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.