## Alan Turing: ahead of his time

June 2008

Alan Turing

Born in London in 1912, Turing was always ahead of his time. When he arrived at the exclusive Sherborne School, his inclination toward the sciences and mathematics was becoming apparent, much to the chagrin of the teachers. In the words of his headmaster: "If he is to be solely a scientific specialist, he is wasting his time at public school."

However, unperturbed by this rebuttal, Turing went on to become an extremely competent mathematician and scientist. He studied mathematics at King's College, Cambridge, eventually winning a scholarship. He became a fellow of the college four years later for his dissertation, in which he independently proved the central limit theorem, an important result in probability theory.

Turing's main contribution to mathematics, however, was his work on computation theory. Presaging the invention of the modern computer, Turing designed an abstract computing device known as the Turing machine — an entirely virtual construct which could perform calculations and follow instructions. This breakthrough enabled Turing to answer an important question that was bugging mathematicians at the time: is there an algorithm that can decide whether any other algorithm will eventually halt, or whether it will run forever. This question is known as the halting problem.

Initially, this problem seems easy — a program instructed to output the set of natural numbers will obviously run forever, whereas a program to find the set of positive integers less than 100 clearly will not. However, certain problems are not so clear-cut. Imagine an algorithm that searches for even integers greater than two which cannot be expressed as the sum of exactly two primes, halting if such a number is found. The first few even integers are easy to express in this form: 4=2+2, 6=3+3 8=5+3, and so on. It appears that the program will continue indefinitely, but is it possible to prove this more rigorously? The answer is, we don't know. The statement that any even number greater than two can be written as the sum of two primes is known as the Goldbach conjecture, and is one of the biggest open problems in mathematics today. If there were an algorithm able to decide whether our program eventually halts, then this would amount to settling the Goldbach conjecture: if it halts then the conjecture is false, if it doesn't, then it is true.

The example of the Goldbach conjecture highlights that the halting problem is much less straightforward than it at first appears. Indeed, as Turing demonstrated, an algorithm to determine whether a program will halt cannot exist. Using the novel method of representing algorithms as Turing machines, he proved that there is no algorithm that can determine if a given Turing machine will halt with a specific input. This is reassuring, since if it were possible to determine practically if a given program were to halt, a computer program could be constructed for any mathematical problem and analysed automatically by algorithm to determine whether it would terminate, putting mathematicians out of a job!

Talented in many fields, Turing contributed to information theory, mathematics and cryptography. His discoveries and ideas often bordered on the philosophical. His work Computing Machinery and Intelligence proposed a way of testing if a machine is "intelligent": a judge communicates with the machine and with another human in text form, being required to determine which of the two is the program and which is human. If a program can reliably emulate a human, it is said to be intelligent.

The Bombe at Bletchley Park. Image reproduced under the GNU Free Documentation License.

Turing's work on information theory was of great use in the Second World War, when he worked as a code breaker at Bletchley Park, decrypting German communications. Using his knowledge of mechanical computation, Turing constructed a machine named the bombe. This device checked potential variations of the German Enigma code to determine which was being used in a given instance. The machine led to the comparatively easy deciphering of transmissions and arguably to the allied victory. In addition, Turing invented a statistical technique called banburismus to detect promising combinations of encoded letters, based on the fact that two strings of text from a natural language written one under the other will have more letters in common than two strings of random letters.

Listen to our podcast on the Enigma code.

Sadly, Turing's work for his country was insufficient to prevent his prosecution. During an investigation into a break-in at his house, Turing let slip that he had been in a homosexual relationship with the criminal. This was illegal, and both men were charged with gross indecency. Turing had to decide between imprisonment and a year's course of oestrogen injections intended to reduce his libido. To avoid prison, Turing was forced to opt for the hormone treatment. This adversely affected his health, leading to enlarged breasts, and arguably to the emotional instability that lead to his apparent suicide in 1954 by cyanide poisoning, a half-eaten apple lying by his bed. It is believed that he poisoned the apple, killing himself in a manner reminiscent of Snow White, his favourite fairy tale. It is tragic that this remarkable individual's uniqueness contributed so much to society whilst at the same time condemning him to ridicule, such that he took his own life.

Despite being ostracised by the authorities, Turing's fame lives on — he is now regarded by many as the father of computing: Turing machines are still used to test the mathematics of algorithms and information theory, and Turing's ideas have maintained their usefulness to mathematicians and scientists, his passion for scientific endeavour inspiring and aiding those who share his dedication and continue the ideas he began many years ago.

Stefan Kopieczek is 17, lives in Buckinghamshire with his parents, brother and sister, and attends Dr. Challoner's Grammar School, Amersham. His favourite number is 1729, and his main ambition is to have an Erdos number less than infinity.

Recently caught sleep-talking about calculus, Stefan realised that he was destined for a life of mathematics, and hopes to study the subject at university. Currently in Year 12, he is studying A-level Maths, Further Maths, Electronics and Physics.

Plus would like to thank the London Mathematical Society and the Maths, Stats and Operational Research Network, as well as the journal Nature for their kind support of this competition.