|
 Alan Turing
was an
English
mathematician,
logician, and
cryptographer.
He provided an
influential formalization of the concept of the
algorithm and computation with the
Turing machine, formulating the now widely
accepted "Turing" version of the
Church–Turing
thesis,
namely that any practical computing model has either the
equivalent or a subset of the capabilities of a Turing machine. With the
Turing test, he made a significant and
characteristically provocative contribution to the debate regarding
artificial intelligence: whether it will ever be possible to say that
a machine is
conscious
and can
think.
He later worked at the
National Physical Laboratory, creating one of the first designs for a
stored-program computer, although it was never actually built. In 1948 he moved
to the
University of Manchester to work on the
Manchester Mark I, then emerging as one of
the world's earliest true computers.
During the
Second World War Turing worked at
Bletchley Park,
 Britain's
code breaking center, and was for a time
head of
Hut 8, the section responsible for
German naval cryptanalysis. He devised a
number of techniques for breaking German ciphers, including the method of the
bombe, an electromechanical machine that could find settings
for the
Enigma machine.
A picture of the Enigma is on the left.
His parents enrolled him at St Michael's, a day school, at the age of six. The
headmistress recognized his genius early on, as did many of his subsequent
educators. In 1926, at the age of 14, he went on to
Sherborne School in
Dorset. His first day of term coincided with
General Strike in England, but so determined was he to attend his
first day that he rode his bike unaccompanied more than 60 miles from
Southampton to school, stopping overnight
at an inn.
Turing's natural inclination toward mathematics and science did not earn him
respect with the teachers at Sherborne, a famous and expensive
public school, whose definition of education placed more emphasis on
the
classics.
|
His headmaster wrote to his parents: "I hope
he will not fall between two schools. If he is to stay at public school,
he must aim at becoming educated. If he is to be solely a Scientific
Specialist, he is wasting his time at a public school".
Despite this, Turing continued to show remarkable ability in the studies he
loved, solving advanced problems in 1927 without having even studied elementary
calculus. In 1928, aged 16, Turing
encountered
Albert Einstein's
work; not only did he grasp it, but he extrapolated Einstein's questioning of
Newton's laws of motion from a text in which this was never made
explicit.
Turing's unwillingness to work as hard on his classical studies as on science
and mathematics meant he failed to win a scholarship to
Trinity College, Cambridge, and went on to the college of his second
choice,
King's College, Cambridge.
Turing was an undergraduate at King's College from 1931 to 1934,
graduating with a distinguished degree, and in 1935 was elected a fellow at
King's on the strength of a dissertation on the
central limit theorem.
In his momentous paper "On Computable Numbers, with an Application to the
Entscheidungsproblem" (submitted on
28 May
1936), Turing reformulated
Kurt Gödel's 1931 results on the limits of
proof and computation, replacing Gödel's universal arithmetic-based formal
language with what are now called
Turing machines, formal and simple devices. He proved that such a machine would be capable of performing any conceivable
mathematical problem if it were representable as an
algorithm, even if no actual Turing machine
would be likely to have practical applications, being much slower than
alternatives.
Bletchley Park
Turing machines are to this day the central object of study in
theory of computation. He went on to prove
that there was no solution to the Entscheidungsproblem by first showing
that the
halting problem
for Turing machines is
undecidable:
it is not possible to decide, in general, algorithmically whether a given Turing
machine will ever halt.
While his proof was published subsequent to
Alonzo Church's equivalent proof in respect
to his
lambda calculus,
Turing's work is considerably more accessible and intuitive. It was also novel
in its notion of a "Universal (Turing) Machine", the idea that such a machine
could perform the tasks of any other machine. The paper also introduces the
notion of
definable numbers.
During the
Second World War,
Turing was a main participant in the efforts at
Bletchley Park to break German ciphers.
Building on cryptanalysis work carried out in
Poland before the war, he contributed several insights into
breaking both the
Enigma machine
and the
Lorenz SZ 40/42
(a teletype cipher attachment codenamed "Tunny" by the British), and was, for a
time, head of
Hut 8, the section
responsible for reading
German naval signals.
Within weeks of arriving at Bletchley Park, Turing had designed an
electromechanical machine which could help break Enigma: the
bombe, named after and building upon the original
Polish-designed
bomba.
They were also referred to as "Bronze Goddesses" because their cases were made
of bronze, but they were more prosaically described by operators as being "like
great big metal bookcases". The bombe, with an enhancement
suggested by mathematician
Gordon Welchman, became one of the primary
tools, and the major automated one, used to attack Enigma-protected message
traffic.
|
