Turing's proof
Proof by Alan Turing / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Turing's proof?
Summarize this article for a 10 year old
Turing's proof is a proof by Alan Turing, first published in November 1936[1] with the title "On Computable Numbers, with an Application to the Entscheidungsproblem". It was the second proof (after Church's theorem) of the negation of Hilbert's Entscheidungsproblem; that is, the conjecture that some purely mathematical yes–no questions can never be answered by computation; more technically, that some decision problems are "undecidable" in the sense that there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem. In Turing's 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 [Principia Mathematica]".[2]
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (September 2022) |
Turing followed this proof with two others. The second and third both rely on the first. All rely on his development of typewriter-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine".