Alan Turing was born on 23 June 1912. His scientific work, in three completely different areas has had an important, and continuing effect on all our lives.
Yet Turing died aged only 42, and for a very long time his name was not well known outside the field of theoretical computer science. And still his name goes largely unrecognised by the giant companies that have made their fortunes from computers, the devices that he played an important role in inventing.
Gödel had proved in 1931 that no consistent formal mathematical system that included addition and multiplication of the integers could be complete; there would be statements that could be made in the system for which neither a proof nor a disproof existed. An example of such a statement would be “This statement has no proof in this system”. If the system is consistent the statement can clearly neither be proved nor disproved. Gödel's genius was to show that it was impossible to exclude the making of self-referential statements like this by showing that they could be encoded, by numbering statements and proofs, as statements about the integers resembling “This arithmetic formula cannot have this result given whole number inputs”.
The problem that remained to fully answer the question about the foundation of mathematics that Hilbert had posed was, “can we tell which statements these unprovable statements are?” In other words, can we find some general procedure that will tell us if a statement in a formal mathematical system has a proof? This required a definition of what we might mean by “some general procedure”. Turing's first major step, made at the age of 23, was to propose a machine, later to be called the Turing machine that would embody the idea of a general procedure. He then proved that if we accepted this definition of a general procedure that we could not decide which statements had proofs. This was a major achievement. Unfortunately for Turing, the American logician Alonzo Church published a proof that the decision problem was unsolvable before Turing. Church's proof involved a very different definition of a “general procedure”. He invented an abstraction, called the lambda calculus, that resembled a very high level programming language and proved the unsolvability of the decision problem using this. After the Cambridge mathematician M H A Newman wrote to Church about the unfortunate eclipse of Turing's discovery, Turing went to Princeton to work with Church.
Turing proved that what Church now called the “Turing Machine” could compute exactly what the lambda calculus could calculate. He did this by writing what we would now recognise as an interpreter for the lambda calculus, treated as a programming language, that ran on a Turing machine.
The original definition of a Turing machine was a machine that only carried out one sort of calculation. The calculation was wired into the finite state automaton in the Turing machine. Turing made on more step. He proposed a universal machine that would read a description of one of these particular machines and then carry out exactly the computation that that machine would have carried out. This “Universal Turing Machine” is the exact analogue of all programmable computers, and even resembles their organisation.
Turing had developed two things that any modern computer scientist would recognise – a programming language interpreter and a hardware emulator.
Turing's work with Church on uniting their two views of computation is the reason that that fundamental claim of Computer Science – that these two views, Turing Machine and Lambda Calculus express what we mean by computation - is known as the “Church-Turing thesis”.
On his return to Britain Turing was drafted into the work to break the Enigma code used by the German and Japanese military in the second world war. His role in this work is more widely known now, after many years in which it was still a state secret, so I will only mention it briefly. Turing built on the work of Polish mathematicians who had cracked the German Army code to crack the German Naval code, believed up to then to be uncrackable.
The work was the precursor of what we would now regard as the study of computational complexity. A massively exponential combinatorial problem had to be reduced by the use of clever theoretical insights to the size where a fast machine could then search the problem space and find a solution.
Turing worked as part of a team of mathematicians at Bletchley Park, the centre where the code breaking was done. The others should also be given credit – M H A Newman, Turing's old teacher from Cambridge University was one, the Polish mathematicians were also important. Turing showed his strength as a mathematician and his willingness to tackle problems that others considered unsolvable.
Turing wrote the first major paper discussing the idea that machines could be considered to think. He proposed a test in which a referee (hakem) communicates with a computer, using what we would now recognise as a chat room. It is widely stated only that the test Turing proposed was that the referee had to be persuaded that the chat was with a human. If you read Turing's 1950 paper, “Computing Machinery and Intelligence”, you will find he starts from the problem of persuading a referee that a chat of this type was with a woman. A very significant difference. And a very significant distortion of Turing's sophistication that this very important cultural twist to the Turing test has been systematically ignored.
Turing turned his attention to a biological problem, the problem of morphogenesis, the creation of shape. Almost all living organisms, including human beings start out as a single symmetrical cell. This cell divides repeatedly again creating a completely symmetrical undifferentiated ball of cells. And then “something” happens and this organism takes shape. Turing's single paper on this subject discusses a simple mechanism which would allow the formation of repeating structures. These could be the tiger's stripes, our vertebrae or our five fingers. He proposed a mechanism in which two antagonistic chemicals compete and cause the formation of a repeating pattern. This involves a process that we would now regard as part of chaos theory. If you search any database of scholarly articles in biology you will find thousands of articles with Turing's name in the title, because of this ground breaking pattern formation theory. In the last few months a study of the formation of ridges in the roof of a mouse mouth was the first to show the exact mechanism at work and the two competing chemicals involved.
Born in Paddington London, Turing's family were British officials in colonial India, so he was brought up by relatives until he was 14 years old and then attended boarding school. During his school years he showed an early interest in Chemistry, Biology and Quantum Physics. He studied mathematics as an undergraduate at King's College, Cambridge. There he found intellectual stimulation and also an environment where his homosexuality was accepted. Not long after graduating he was made a Fellow of Kings, then left to do his doctorate at Princeton with Alonzo Church as his supervisor. Church had beaten Turing to publishing the solution to the “Decision Problem”, but Church was careful to give full credit to Turing for the discovery of what Church called the “Turing Machine”. Turing was offered a job at Princeton, but returned to Britain and worked during the war on cryptography at Bletchley Park.
After the war Turing's contribution to the construction of the very first electronic computers suffered from bureaucratic delays and obstruction. He designed the ACE computer at the National Physical Laboratory, but as development slowed, he moved to Manchester to work on the very first fully electronic programmable computer, the Manchester Mark 1. Turing published his papers on Artificial Intelligence and one seminal paper on Morphogenesis.
Turing was also an active and successful long distance runner. He had beaten the British runner who won the silver medal in the 1948 London Olympics Marathon in a race the year before. Turing could himself have run in the Olympics, but he was ruled out because of an injury.
In 1952, police were investigating a robbery at Turing's house. Turing mentioned a homosexual relationship. The police arrested Turing, because at that time homosexuality was a criminal offence in Britain. The only evidence against him was his own honest statement of his sexuality. He was convicted and sentenced to one year in prison, but offered the alternative of treatment with hormones to “cure” his homosexuality, a form of chemical castration. The hormone treatment caused his physical and psychological condition to decline. In 1954, at the age of 42, Alan Turing committed suicide by eating an apple coated with cyanide. In 2009 the British Prime Minister apologised for the treatment of Alan Turing by the British state. However appeals to have his conviction cancelled have been rejected.
Turing's 100th birthday is now the subject of world wide effort to bring the recognition of the achievements of this brilliant scientist who was treated so brutally because of his sexuality.
The dreadful record of the computer industry on recognition of Turing's work has only partly been corrected by really rather small donations by companies like Google to the restoration and preservation of Bletchley Park.
The computer industry has a long and dishonourable tradition of ignoring the theoretical foundations of computer science. It is one of the reasons that computer systems, by and large, work so badly.
Two prejudices, one against people who choose a sexuality different from the “accepted norm”, the other against “theory” have obstructed recognition of Alan Turing's work for much of the last 60 years.
These prejudices continue to hold back human progress today. To honour Alan Turing's memory, we should fight against them both.