Turing's Proof

Turing's proof is Alan Turing's argument, submitted in November 1936 and published in 1937 under the title On Computable Numbers, with an Application to the Entscheidungsproblem, that Hilbert's Entscheidungsproblem has a negative answer. It was the second proof of that negative result, after Godel's, and it shows that some decision problems are undecidable, in the sense that no single algorithm can correctly answer yes or no for every instance of the problem. Turing described his own result as distinct from Godel's incompleteness theorems, showing instead that there is no general method for deciding whether a given formula is provable within the system of Principia Mathematica.