sourced story
1936 CEReputable source · 2 sourcesWell documented

Turing Defines Computability and the Limits of Machines

An abstract machine on paper answers a question Godel's work had left open, and lays the theoretical ground for every computer since

On the timeline · around 1936 CE · Modern MathematicsModern MathematicsTuring Defines Computability and the Limits of Machines18751900192519501975

Quick facts

Turing's dates
1912-1954
Key paper
On Computable Numbers, 1936
Wartime role
Codebreaking at Bletchley Park
Death
1954, cyanide poisoning; circumstances disputed by family

What happened

Alan Turing, born in 1912 in London, published On Computable Numbers, with an Application to the Entscheidungsproblem in 1936, defining a computable number as a real number whose decimal expansion could be produced by an abstract machine, later called a Turing machine, starting from a blank tape. Turing had come to the problem after attending a course by Max Newman covering Godel's incompleteness results and Hilbert's Entscheidungsproblem, the decision problem asking whether an algorithm could determine the truth of any mathematical statement, and his 1936 paper showed that no such general algorithm can exist, since some well-defined computational questions are simply undecidable. During the Second World War, Turing's codebreaking work at Bletchley Park, including machines built to help break German ciphers, is credited with saving lives by shortening the war. Turing died in 1954 of cyanide poisoning; an inquest ruled it self-administered, though his mother maintained it was accidental.

Why it matters

Turing's 1936 paper defined, in precise mathematical terms, exactly what it means for a problem to be computable at all, a question that had to be answered before anyone could build a general-purpose computing machine, and the abstract Turing machine remains the theoretical basis for computer science's understanding of computation to this day. His result extended Godel's incompleteness findings into the newer language of computation, showing that undecidability is a fundamental limit on what any machine, however powerful, could ever calculate.

How we know

Turing's 1936 paper survives as a published text in the Proceedings of the London Mathematical Society, and his wartime work at Bletchley Park, though classified for decades, has since been documented through declassified records and the testimony of colleagues who worked alongside him.

Sources

See something wrong? . Corrections with a source get fixed fastest.

Part of a timelineHistory of Mathematics26 events · A number system built for taxes, a theorem older than the man it's named for, a proof too long for a margin, and an infinity too big to countView all →
Turing Defines Computability and the Limits of Machines · History of Mathematics · SourcedStory