Alan Turing

Alan Turing, in full Alan Mathison Turing, (born June 23, 1912, London, England—died June 7, 1954, Wilmslow, Cheshire), British mathematician and logician who made major contributions to mathematics, cryptanalysis, logic, philosophy, and mathematical biology and also to the new areas later named computer science, cognitive science, artificial intelligence, and artificial life. 

The son of a civil servant, Turing was educated at a top private school. He entered the University of Cambridge to study mathematics in 1931. After graduating in 1934, he was elected to a fellowship at King’s College (his college since 1931) in recognition of his research in probability theory. In 1936 Turing’s seminal paper “On Computable Numbers, with an Application to the Entscheidungsproblem [Decision Problem]” was recommended for publication by the American mathematical logician Alonzo Church, who had himself just published a paper that reached the same conclusion as Turing’s, although by a different method. Turing’s method (but not so much Church’s) had profound significance for the emerging science of computing. Later that year Turing moved to Princeton University to study for a Ph.D. in mathematical logic under Church’s direction (completed in 1938). 

An important step in Turing’s argument about the Entscheidungsproblem was the claim, now called the Church-Turing thesis, that everything humanly computable can also be computed by the universal Turing machine. The claim is important because it marks out the limits of human computation. Church in his work used instead the thesis that all human-computable functions are identical to what he called lambda-definable functions (functions on the positive integers whose values can be calculated by a process of repeated substitution). Turing showed in 1936 that Church’s thesis was equivalent to his own, by proving that every lambda-definable function is computable by the universal Turing machine and vice versa. In a review of Turing’s work, Church acknowledged the superiority of Turing’s formulation of the thesis over his own (which made no reference to computing machinery), saying that the concept of computability by a Turing machine “has the advantage of making the identification with effectiveness…evident immediately.” 

Having returned from the United States to his fellowship at King’s College in the summer of 1938, Turing went on to join the Government Code and Cypher School, and, at the outbreak of war with Germany in September 1939, he moved to the organization’s wartime headquarters at Bletchley Park, Buckinghamshire. A few weeks previously, the Polish government had given Britain and France details of the Polish successes against Enigma, the principal cipher machine used by the German military to encrypt radio communications. As early as 1932, a small team of Polish mathematician-cryptanalysts, led by Marian Rejewski, had succeeded in deducing the internal wiring of Enigma, and by 1938 Rejewski’s team had devised a code-breaking machine they called the Bomba (the Polish word for a type of ice cream).  

In 1945, the war over, Turing was recruited to the National Physical Laboratory (NPL) in London to create an electronic computer. His design for the Automatic Computing Engine (ACE) was the first complete specification of an electronic stored-program all-purpose digital computer. Had Turing’s ACE been built as he planned, it would have had vastly more memory than any of the other early computers, as well as being faster. However, his colleagues at NPL thought the engineering too difficult to attempt, and a much smaller machine was built, the Pilot Model ACE (1950). 

Turing was a founding father of artificial intelligence and of modern cognitive science, and he was a leading early exponent of the hypothesis that the human brain is in large part a digital computing machine. He theorized that the cortex at birth is an “unorganised machine” that through “training” becomes organized “into a universal machine or something like it.” Turing proposed what subsequently became known as the Turing test as a criterion for whether an artificial computer is thinking (1950). 

Papers

turing_1936.pdf
Computability and λ-Definability.pdf

Videos