Alan Turing

In 1936, a twenty-three year old Cambridge mathematician named Alan Turing published a paper with the unpromising title On Computable Numbers, with an Application to the Entscheidungsproblem. Its purpose was narrow and technical: to answer a question posed by the mathematician David Hilbert about whether there exists a mechanical procedure that could decide, for any mathematical statement, whether it is provable. Turing's method for answering it created something far more consequential than the answer itself.

To make precise what a mechanical procedure even meant, Turing described an imaginary device, now called a Turing machine, consisting of an infinitely long tape divided into cells, a read-write head that could move along the tape one cell at a time, and a simple table of rules determining what the machine did next based on the symbol it read and its current internal state. Despite its extreme simplicity, Turing showed that such a machine could, in principle, carry out any calculation that could be carried out by following an explicit set of rules at all, a claim now known as the Church-Turing thesis after Turing and the logician Alonzo Church, who had reached a related result independently at almost the same time using a different mathematical approach.

Turing used the machine to prove that Hilbert's decision problem has no general solution, by showing that no algorithm can determine in advance, for every possible machine and input, whether that machine will ever stop running, the halting problem. The proof was itself an early triumph of computer science before any computer existed. Every general-purpose computer built since, from the earliest vacuum-tube machines to a modern laptop, is, in the strict mathematical sense Turing defined, equivalent to the abstract machine he described eleven years before the first stored-program computer ran.

During the Second World War, Turing worked at Bletchley Park, Britain's codebreaking center, where he led the team responsible for breaking the German navy's Enigma cipher, building on foundational work done before the war by Polish cryptologists Marian Rejewski, Jerzy Rozycki, and Henryk Zygalski. Turing designed the Bombe, an electromechanical machine that could search through the vast number of possible Enigma settings far faster than any human, and the intelligence it produced, codenamed Ultra, is widely credited by historians with shortening the war, though by precisely how much remains genuinely debated.

Turing's postwar career continued at the National Physical Laboratory and the University of Manchester, where he worked on some of the earliest stored-program computers and wrote a landmark 1950 paper proposing what became known as the Turing test, a practical way to ask whether a machine could be said to think. In 1952 he reported a burglary to the police and, in the course of the investigation, disclosed a sexual relationship with another man, homosexual acts were then a criminal offense in Britain, and Turing was convicted of gross indecency. Offered a choice between prison and a course of hormone treatment intended to suppress his libido, he accepted the treatment, which was administered for a year and had significant physical side effects.

Turing died in June 1954 of cyanide poisoning, an inquest at the time ruled it suicide, and most historians accept that verdict, though a minority have argued the death could have been accidental, from cyanide fumes produced by an experiment he was known to be running at home. The British government issued a formal apology for his treatment in 2009 and a royal pardon in 2013, in 2017 a law informally called the Alan Turing law posthumously pardoned thousands of other men convicted under the same since-repealed statute.