Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Turing_degree> ?p ?o. }
Showing items 1 to 21 of
21
with 100 items per page.
- Turing_degree abstract "In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems; the Turing degree of a set tells how difficult it is to solve the decision problem associated with the set. That is, to determine whether an arbitrary number is in the given set.Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered so that if the Turing degree of a set X is less than the Turing degree of a set Y then any (noncomputable) procedure that correctly decides whether numbers are in Y can be effectively converted to a procedure that correctly decides whether numbers are in X. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.The Turing degrees were introduced by Emil Leon Post (1944), and many fundamental results were established by Stephen Cole Kleene and Post (1954). The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the priority method.".
- Turing_degree wikiPageExternalLink History_of_Degrees.pdf.
- Turing_degree wikiPageID "764405".
- Turing_degree wikiPageRevisionID "598658409".
- Turing_degree hasPhotoCollection Turing_degree.
- Turing_degree subject Category:Computability_theory.
- Turing_degree subject Category:Theory_of_computation.
- Turing_degree comment "In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems; the Turing degree of a set tells how difficult it is to solve the decision problem associated with the set.".
- Turing_degree label "Grau de Turing".
- Turing_degree label "Turing degree".
- Turing_degree label "Turinggrad".
- Turing_degree label "チューリング次数".
- Turing_degree label "不可解度".
- Turing_degree sameAs Turinggrad.
- Turing_degree sameAs チューリング次数.
- Turing_degree sameAs Grau_de_Turing.
- Turing_degree sameAs m.039hr_.
- Turing_degree sameAs Q1527413.
- Turing_degree sameAs Q1527413.
- Turing_degree wasDerivedFrom Turing_degree?oldid=598658409.
- Turing_degree isPrimaryTopicOf Turing_degree.