| dbo:abstract
|
- 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 (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]". 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". (en)
- Dowód Turinga – dowód przedstawiony przez Alana Turinga w 1937 w pracy "On Computable Numbers, With an Application to the Entscheidungsproblem" pokazujący, że pewne ogólne klasy problemów są nierozstrzygalne, to znaczy nie istnieje uniwersalny algorytm rozwiązujący każdą instancje problemów z tych klas. W szczególności dowód daje negatywną odpowiedź na . (pl)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 42064 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Dowód Turinga – dowód przedstawiony przez Alana Turinga w 1937 w pracy "On Computable Numbers, With an Application to the Entscheidungsproblem" pokazujący, że pewne ogólne klasy problemów są nierozstrzygalne, to znaczy nie istnieje uniwersalny algorytm rozwiązujący każdą instancje problemów z tych klas. W szczególności dowód daje negatywną odpowiedź na . (pl)
- 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 (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]". (en)
|
| rdfs:label
|
- Turing's proof (en)
- Dowód Turinga (pl)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
