Turing's proof, is a proof by Alan Turing, first published in January 1937 with the title On Computable Numbers, With an Application to the Entscheidungsproblem. It was the second proof of the assertion (Alonzo Church's proof was first) that some decision problems are "undecidable": there is no single algorithm that infallibly gives a correct YES or NO answer to each instance of the problem. In his own words: "...what I shall prove is quite different from the well-known results of Gödel ... I shall now show that there is no general method which tells whether a given formula U is provable in K ..." (Undecidable p. 145).
Turing preceded this proof with two others. The second and third both rely on the first. All rely on his development of type-writer-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine".
Read more about Turing's Proof: Richard's Paradox, Complications, Summary of The Proofs, Summary of The First Proof, Summary of The Second Proof, Summary of Proof #3, Details of Proof #3
Famous quotes containing the word proof:
“It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
—William Shakespeare (1564–1616)