Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Turing_degree> ?p ?o }
Showing triples 1 to 70 of
70
with 100 triples per page.
- Turing_degree abstract "In computer science and mathematical logic the Turing degree (named after Alan Turing) 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 wikiPageLength "16962".
- Turing_degree wikiPageOutDegree "36".
- Turing_degree wikiPageRevisionID "705040833".
- Turing_degree wikiPageWikiLink Alan_Turing.
- Turing_degree wikiPageWikiLink Annals_of_Mathematics.
- Turing_degree wikiPageWikiLink Bulletin_of_the_American_Mathematical_Society.
- Turing_degree wikiPageWikiLink Category:Computability_theory.
- Turing_degree wikiPageWikiLink Category:Theory_of_computation.
- Turing_degree wikiPageWikiLink Computability_theory.
- Turing_degree wikiPageWikiLink Computer_science.
- Turing_degree wikiPageWikiLink Countable_set.
- Turing_degree wikiPageWikiLink Decision_problem.
- Turing_degree wikiPageWikiLink Dense_order.
- Turing_degree wikiPageWikiLink Emil_Leon_Post.
- Turing_degree wikiPageWikiLink Equivalence_class.
- Turing_degree wikiPageWikiLink Equivalence_relation.
- Turing_degree wikiPageWikiLink Gerald_Sacks.
- Turing_degree wikiPageWikiLink Halting_problem.
- Turing_degree wikiPageWikiLink Join_and_meet.
- Turing_degree wikiPageWikiLink Leo_Harrington.
- Turing_degree wikiPageWikiLink Many-one_reduction.
- Turing_degree wikiPageWikiLink Martin_measure.
- Turing_degree wikiPageWikiLink Mathematical_logic.
- Turing_degree wikiPageWikiLink Muchnik.
- Turing_degree wikiPageWikiLink Oracle_machine.
- Turing_degree wikiPageWikiLink Partially_ordered_set.
- Turing_degree wikiPageWikiLink Recursively_enumerable_set.
- Turing_degree wikiPageWikiLink Robert_I._Soare.
- Turing_degree wikiPageWikiLink Semilattice.
- Turing_degree wikiPageWikiLink Stephen_Cole_Kleene.
- Turing_degree wikiPageWikiLink Theodore_Slaman.
- Turing_degree wikiPageWikiLink Turing_jump.
- Turing_degree wikiPageWikiLink Turing_reduction.
- Turing_degree wikiPageWikiLink File:Rehasse.png.
- Turing_degree wikiPageWikiLinkText "Post's problem and the priority method".
- Turing_degree wikiPageWikiLinkText "Post's problem".
- Turing_degree wikiPageWikiLinkText "Turing degree".
- Turing_degree wikiPageWikiLinkText "Turing degree#Post's problem and the priority method".
- Turing_degree wikiPageWikiLinkText "Turing equivalent".
- Turing_degree wikiPageWikiLinkText "Turing-equivalent".
- Turing_degree wikiPageWikiLinkText "Turing_degree#Post's problem and the priority method".
- Turing_degree wikiPageWikiLinkText "degree".
- Turing_degree wikiPageWikiLinkText "degrees of unsolvability".
- Turing_degree wikiPageWikiLinkText "other Post's problem".
- Turing_degree wikiPageWikiLinkText "priority method".
- Turing_degree wikiPageWikiLinkText "turing degree".
- Turing_degree wikiPageUsesTemplate Template:Citation.
- Turing_degree wikiPageUsesTemplate Template:Main.
- Turing_degree wikiPageUsesTemplate Template:MathSciNet.
- Turing_degree wikiPageUsesTemplate Template:Redirect.
- Turing_degree subject Category:Computability_theory.
- Turing_degree subject Category:Theory_of_computation.
- Turing_degree type Area.
- Turing_degree type Area.
- Turing_degree type Redirect.
- Turing_degree comment "In computer science and mathematical logic the Turing degree (named after Alan Turing) 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.".
- Turing_degree label "Turing degree".
- Turing_degree sameAs Q1527413.
- Turing_degree sameAs Степен_на_Тюринг.
- 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 不可解度.
- Turing_degree wasDerivedFrom Turing_degree?oldid=705040833.
- Turing_degree isPrimaryTopicOf Turing_degree.