Alan Mathison Turing

FRS OBE (born 23 June 1912 at 2 Warrington Crescent, London W9, died 7 June 1954 at his home in Wilmslow, Cheshire) contributed to mathematics, cryptanalysis, logic, philosophy, biology, and formatively to computer science, cognitive science, Artificial Intelligence and Artificial Life.

Educated at Sherborne School in Dorset, Turing went up to King's College, Cambridge in October 1931 to read Mathematics. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. A Turing machine consists of a potentially infinite paper tape, on which is written a finite number of discrete (e.g. binary) symbols, and a scanner that moves back and forth along the tape symbol by symbol, reading what it finds and writing further symbols. Turing proved that a single machine, known as the universal Turing machine, can be programmed to simulate any other Turing machine.

Turing and the American logician Alonzo Church argued that every effective mathematical method can be carried out by the universal Turing machine, a proposition now known as the Church-Turing thesis. A mathematical method is 'effective' if it can be set out as a list of instructions able to be followed by a human clerk who works obediently with paper and pencil, for as long as is necessary, but without insight or ingenuity. The Church-Turing thesis was hailed as a 'fundamental discovery' concerning the 'mathematicizing power of Homo Sapiens' (Emil Post's words in 1936). In a review of Turing's work, Church generously acknowledged the superiority of Turing's formulation of the thesis over his own, saying that the concept of computability by Turing machine 'has the advantage of making the identification with effectiveness ... evident immediately'.

Working independently, Turing and Church had both shown that - contrary to mathematical opinion of the day - there are well-defined mathematical problems that cannot be solved by effective methods; each published this result in 1936. This, in conjunction with the work of the Austrian logician Kurt Godel, put paid to the Hilbert programme in mathematics. David Hilbert, who in 1900 set the agenda for much of 20th century mathematics, asserted that mathematicians should seek to express mathematics in the form of a consistent, complete and decidable formal system. A consistent system is one that contains no contradictions; 'complete' means that every true mathematical statement is provable in the system; and 'decidable' means that there is an effective method for telling, of each mathematical statement, whether or not the statement is provable in the system. Hilbert's point was that if we came to possess such a formal system, then ignorance would be banished from mathematics forever. Given any mathematical assertion, we would be able to tell whether the assertion is true or false by determining whether or not it is provable in the system. That the formal system be decidable was an important condition: an undecidable system could not serve fully to banish ignorance, since we could not always be confident of being able to determine whether or not the assertion in question is provable in the system. Likewise, an incomplete system would be unsatisfactory, since the assertion in question might be true and yet unprovable in the system.

In 1931, Godel proved that Hilbert's ideal is impossible to satisfy, even in the case of simple arithmetic. There can be no consistent, complete formal system of arithmetic. This result is known as Godel's first incompleteness theorem. Godel's theorem says nothing about decidability, however. That aspect was addressed by Turing and Church. They showed independently, in 1936, that no consistent formal system of arithmetic is decidable; indeed, they showed that not even the weaker system known as first-order predicate logic is decidable. The Hilbertian dream lay in total ruin.

During 1936-1938 Turing continued his studies, now at Princeton University. He completed a PhD in mathematical logic under Church's direction, analysing the notion of 'intuition' in mathematics and introducing the idea of oracular computation, now fundamental in mathematical recursion theory. An 'oracle' is an abstract device able to solve mathematical problems too difficult for the universal Turing machine.

In the summer of 1938 Turing returned to his Fellowship at King's. At the outbreak of hostilities with Germany in September 1939 he left Cambridge for the wartime headquarters of the Government Code and Cypher School (GC&CS) at Bletchley Park, Buckinghamshire. Building on earlier work by Polish cryptanalysts, Turing contributed crucially to the design of electro-mechanical machines ('bombes') used to decipher Enigma, the code by means of which the German armed forces sought to protect their radio communications. Thanks to the bombes, by early 1942 GC&CS was decoding about 39,000 intercepted messages each month, rising subsequently to over 84,000 messages a month - approximately two every minute. Turing's work on the version of Enigma used by the German navy was vital to the battle for supremacy in the North Atlantic. He also contributed to the attack on the cyphers known as 'Fish'. Based on binary teleprinter code, Fish was used during the latter part of the war in preference to morse-based Enigma for the encryption of high-level signals, for example messages from Hitler and members of the German High Command. It is estimated that the work of GC&CS shortened the war in Europe by at least two years. Turing received the Order of the British Empire for the part he played. See also Alan Turing: Codebreaker and Computer Pioneer.

In 1945, the war over, Turing was recruited to the National Physical Laboratory (NPL) in London, his brief to design and develop an electronic computer - a concrete form of the universal Turing machine. Turing's report setting out his design for the Automatic Computing Engine (ACE) was the first relatively complete specification of an electronic stored-program general-purpose digital computer. Turing saw that speed and memory were the keys to computing. His design had much in common with today's RISC architectures and called for a high-speed memory of roughly the same capacity as an early Macintosh computer (enormous by the standards of his day). Had Turing's ACE been built as planned it would have been in a different league from the other early computers. However, his colleagues at NPL thought the engineering work too difficult to attempt, and a considerably smaller machine was built, the Pilot Model ACE. With a clock speed of 1 MHz this was for some time the fastest computer in the world. Computers deriving from Turing's original design remained in use until about 1970 (including the Bendix G15, arguably the first personal computer).

Delays beyond Turing's control resulted in NPL's losing the race to build the world's first working electronic stored-program digital computer - an honour that went to the Royal Society Computing Machine Laboratory at Manchester University, in June 1948. Discouraged by the delays at NPL, Turing took up the Deputy Directorship of the Royal Society Computing Machine Laboratory in that year (there was no Director). His theoretical work of 1935-36 had been a fundamental influence on the Manchester computer project from its inception. Turing's principal practical contribution at Manchester was to design the programming system of the Ferranti Mark I, the world's first commercially available electronic digital computer.

Turing was a founding father of modern cognitive science and a leading early exponent of the hypothesis that the human brain is in large part a digital computing machine, theorising that the cortex at birth is an 'unorganised machine' which through 'training' becomes organised 'into a universal machine or something like it'. He pioneered Artificial Intelligence (AI): his work in this area, including his anticipation of modern connectionist approaches, is described elsewhere on this site.

Turing spent the rest of his short career at Manchester University, being appointed to a specially created Readership in the Theory of Computing in May 1953. He was elected a Fellow of the Royal Society of London in March 1951 (a high honour). In March 1952 he was prosecuted for his homosexuality, then a crime in Britain, and sentenced to a period of twelve months hormone 'therapy' - shabby treatment from the country he had helped save, which he seems to have borne with amused fortitude.

From 1951 Turing worked on what would now be called Artificial Life, using the Ferranti Mark I computer to model aspects of biological growth, in particular a chemical mechanism by which the genes of a zygote could determine the anatomical structure of the resulting animal or plant. He died in the midst of this groundbreaking work.