Alan Turing (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer.

Turing is often considered to be the father of modern computer science. Turing 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 codebreaking centre, 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.

In 1952, Turing was convicted of "acts of gross indecency" after admitting to a sexual relationship with a man in Manchester. He was placed on probation and required to undergo hormone therapy. Turing died after eating an apple laced with cyanide in 1954. His death was ruled a suicide.

Cryptanalysis

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.

Since September 1938, Turing had been working part-time for the Government Code and Cypher School (GCCS), the British codebreaking organisation. He worked on the problem of the German Enigma machine, and collaborated with Dilly Knox, a senior GCCS codebreaker. On 4 September 1939, the day after Britain declared war on Germany, Turing reported to Bletchley Park, the wartime station of GCCS.

The Turing-Welchman bombe

Within weeks of arriving at Bletchley Park, Turing had devised an electromechanical machine which could help break Enigma: the bombe, named after the Polish-designed bomba. Also referred to as “Bronze Goddesses” as their cases were made wholly of bronze, they were more prosaically described by operators as “like great big metal bookcases.” The bombe, with an enhancement suggested by mathematician Gordon Welchman, became the primary tool used to read Enigma traffic.

Professor Jack Good, cryptanalyst working at the time with Turing at Bletchley Park, later said: "Turing's most important contribution, I think, was of part of the design of the bombe, the cryptanalytic machine. He had the idea that you could use, in effect, a theorem in logic which sounds to the untrained ear rather absurd; namely that from a contradiction, you can deduce everything."

The bombe searched for the correct settings of the Enigma rotors, and required a suitable "crib": a piece of matching plaintext and ciphertext. For each possible setting of the rotors (which had of the order of 1019 states, or 1022 for the U-Boat Enigmas which had an extra wheel), the bombe performed a chain of logical deductions based on the crib, implemented electrically. The bombe detected when a contradiction had occurred, and ruled out that setting, moving onto the next. Most of the possible settings would cause contradictions and be discarded, leaving only a few to be investigated in detail. Turing's bombe was first installed on 18 March 1940. Over 200 bombes were in operation by the end of the war.