Turing's proof
Turing's proof is a proof by Alan Turing submitted on 12 November 1936 and first published in 1937 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:
Turing's proof is a proof by Alan Turing submitted on 12 November 1936 and first published in 1937[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.…
saved by
related reading
- The Turing Test (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Turing Machinessamwho.dev
- alan turing - computing machinery and intelligencecourses.cs.umbc.edu
- Gödel's incompleteness theorems - Wikipediaen.wikipedia.org
- Church–Turing thesis - Wikipediaen.wikipedia.org
- Halting problem - Wikipediaen.wikipedia.org
- Turing completeness - Wikipediaen.wikipedia.org
- Turing machine - Wikipediaen.wikipedia.org
- Nondeterministic Turing machine - Wikipediaen.wikipedia.org
- A Theory That Proves Its Own Inconsistency · Yan Sheng's siteangyansheng.github.io
- Turing Machines | Brilliant Math & Science Wikibrilliant.org