From 0 to Infinity in 26 Centuries (17 page)

Memory machine

Prior to the First World War, Turing was a mathematics fellow at Cambridge University. He worked on the Entscheidungsproblem, a challenge set by the German mathematician David
Hilbert (see
here
) that asked whether it is possible to turn any problem in mathematics into an algorithm that will produce a ‘true’ or ‘false’ answer that doesn’t
require a proof. Turing was able to show that it is not possible by introducing the concept of an idealized computer called a
Turing machine
.

A Turing machine is a computer that has an infinite memory that can be fed an infinite amount of data. The machine can then modify the data according to a simple set of mathematical rules to
give an output. Turing showed that it was not possible to tell whether a Turing machine would reach an answer to the Entscheidungsproblem, or whether the machine would carry on working out the
problem for ever.

The theoretical Turing machine was very important in establishing computer science. Turing’s research into computing took him to Princeton University in the United States, where he
worked towards a PhD in mathematics. Here Turing built one of the first electrical computers using Boolean logic (see
here
), a crucial development towards what came
next.

Unpicking the code

Turing was part of the Government Code and Cipher school based at Bletchley Park in Milton Keynes, UK, during the Second World War, where he was set to work on breaking the
Enigma cipher. While there Turing developed something called the
Bombe
, an electro-mechanical machine that could work its way through the huge number of possible settings of the Enigma
machine far faster than a human cryptanalyst could. The Bombe relied on the fact that the Enigma would never encrypt a letter as itself – if you typed the letter ‘q’ into the
Enigma, ‘q’ wouldn’t be given as an output. The Bombe would try each setting, and when the output letter matched the input letter that setting would be eliminated and the next one
tried. The second trick was to use a
crib
: making an educated guess as to what the first words of an intercepted message might be.

The work of Turing and others at Bletchley Park was hugely important to the Allies and certainly shortened the war. However, the work was top secret and Turing could therefore receive little
recognition for his efforts.

Man v machine

After the war Turing continued his work on electronic computers, turning his hand to Artificial Intelligence – whether or not a
sufficiently
powerful and fast computer could be considered intelligent. During his investigations, Turing devised what has become known as the
Turing test
. The test states that a computer is to be
considered intelligent if a human being communicating with it does not notice that the computer is not a human being. Turing’s work in computers laid the foundations for the digital
revolution we now enjoy (and also take for granted). The computer I’m typing this book on, for example, has its origins in a Turing machine.

Unfortunately, in 1952 Turing was convicted of gross indecency for homosexual acts, which were deemed illegal at that time. Turing chose to undertake a
course of oestrogen injections over a prison sentence. Horrific side effects to the injections led Turing to become depressed, and in 1954 he was found dead of cyanide poisoning. Turing, the
founder of modern computing, the unsung war hero, was dead, most likely by his own hand, at the age of forty-one. We can only ponder what discoveries were denied to us by his tragically premature
demise.

M
APPING
T
HINGS
O
UT

Computers were not immediately adopted by mathematicians because many detractors felt that an elegant proof of a problem should be shown formally, rather than by
number-crunching. One of the first conjectures proved with the assistance of computing power was called the
four-colour theorem
.

In the nineteenth century South African mathematician Francis Guthrie (1831–99) was shading in a map of England’s counties when he noticed that each county could be defined from its
neighbouring county using just four colours. Guthrie posited this as the four-colour conjecture, which, when put more formally, states that in the instance of a flat two-dimensional map, on which
any regions that share a border cannot be the same colour, no more than four colours are ever needed. It is important to note that regions meeting across a point do not share a border and therefore
can be the same colour, and that all the countries on the map are independent, so they can
be any colour required (unlike the part of Russia where old Königsberg
is).

One of the main difficulties with this problem lies in the fact that it is highly visual; there must be an infinite number of maps one could draw to test the theory. However, we
can visualize each region as a point using
graph theory
(much like Euler used with the Königsberg problem).

This allowed mathematicians to start tackling the problem in earnest because various different maps could be shown to have effectively the same graph. Serbian mathematician
Danilo Blanusa (1903–87) discovered two maps that needed more than three colours. These elusive maps are known as
snarks
and they helped to demonstrate that the minimum number of
colours required must be four or more. There are eight known snarks, the last of which was discovered in 1989.

Without a doubt

In the 1970s two researchers in the United States, Kenneth Appel (1932–) and Wolfgang Haken (1928–), then tackled the four-colour conjecture. They discovered that
the most complicated part of any map – any area that might need lots of colours, and which might, therefore, disprove the four-colour conjecture – could always be shown as one of 1,936
possible situations. All of these 1,936 situations could be modelled as a graph and, using a computer, Appel and Haken showed that they could all be drawn using just four colours.

So, Appel and Haken showed that any map could be shown to be one of the 1,936 standard ones, so no counter-examples exist.

This was the first theorem proved with the assistance of a computer, but many mathematicians were unimpressed because the exhaustive proof required hundreds of pages of calculations. This meant
that checking the proof would take so long it was necessary to trust that the computer’s work was correct, which was not an assumption many mathematicians would make at the time.

A P
IECE OF THE
P
IE

π, as every schoolchild knows, is a special number that you get by dividing a circle’s
circumference
(perimeter) by its
diameter
(the distance across the
middle of the circle). Because all circles are mathematically
similar
(in proportion) you always generate the same value, no matter the size of the circle.

Mathematicians have always been fascinated by π. It is an irrational number (see
here
) and it is a very useful constant in mathematics that occurs not only in
questions about circles but also in all kinds of problems in geometry and calculus. Throughout the history of mathematics we have seen people trying to calculate π to increasing levels of
accuracy (see box
here
). My calculator says:

Since the advent of mechanical and electrical computers, the ability to perform the necessary calculations quickly and accurately has improved exponentially. The Chudnovsky
brothers from the USA were the first to get π to 1 billion decimal places using a homemade super-computer in the 1980s. The record is currently owned by Japanese mathematician Yasumasa Kanada,
who reached 2.7 trillion (2,700,000,000,000) decimal places in 2010.

Into the unknown

Chaos theory
is the branch of mathematics that deals with unpredictable behaviour. Although this field has really opened up since the advent of computers, chaotic
equations were first noticed during Newton’s time.

One of the main aims of Newton’s work was to create a system of equations that explained the motion of the planets. As we know, the planets move around the sun in almost circular orbits.
Astronomers had noticed, however, that the orbits would wobble slightly, apparently at random, from time to time.

Leonard Euler (see
here
) developed a concept that became known as the
three-body problem
in an attempt to predict the somewhat irregular orbit of the moon. The reason for this
irregularity is because the moon’s orbit is influenced by the gravity of both the earth and the sun. The force the sun exerts on the moon varies according to where the moon is in its orbit
around the earth, and as a result the moon’s orbit fluctuates. Euler was able to work out the governing equations for the situation in which two of the bodies (the earth and the sun) are in a
fixed relationship when compared to the third (the moon). French mathematician Henri Poincaré (1854–1912) tried to extend this to a more general solution that could be applied to the
whole solar system. He did not succeed, but he was able to show that the orbits would never settle into a regular pattern.

The motion of the planets was not the only phenomenon scientists had observed to be irregular. The mathematics of
turbulence
had long eluded mathematicians. When a gas or a liquid flows,
the motion of a particle within it can be explained
mathematically under certain circumstances – when the speed of the fluid is relatively low. However, as the speed
increases, the motion of a particle, particularly around an obstacle, becomes impossible to predict. This turbulence is highly chaotic. The study of the motion of gases and liquids is called
fluid mechanics
and is important to human beings in all sorts of situations, including transport, electricity generation, and even in understanding the flow of blood around our bodies.

The weather is perhaps the biggest earthly example of turbulence. In the 1960s American meteorologist Edward Lorenz (1917–2008) was modelling the movement of air using a computer when he
noticed that, if he changed the initial conditions of his simulations by a negligible amount, as time went by the weather predicted by his simulations would vary widely. This led Lorenz to coin the
term ‘the butterfly effect’: the notion that a minuscule change in an air pattern, much like the change induced by a butterfly flapping its wings, could lead to a hurricane happening
elsewhere in the world.