Turing's proof [SEP] named after
Turing's proof
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
machine" would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the "decision problem" by first showing that the halting problem for Turing machines is undecidable: It is not possible to decide algorithmically whether a Turing machine will ever halt.
Although Turing's proof was published shortly after Alonzo Church's equivalent proof using his lambda calculus, Turing's approach is considerably more accessible and intuitive than Church's. It also included a notion