Turing degrees
E679185
equivalence classes under Turing reducibility
mathematical concept
structure in computability theory
Turing degrees are an abstract classification of sets of natural numbers or decision problems according to their relative level of algorithmic unsolvability or computational complexity under Turing reducibility.
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
equivalence classes under Turing reducibility
ⓘ
mathematical concept ⓘ structure in computability theory ⓘ |
| basedOn | Turing reducibility NERFINISHED ⓘ |
| captures |
relative algorithmic unsolvability
ⓘ
relative computational complexity ⓘ |
| connectedTo |
effective descriptive set theory
ⓘ
set of reals under Turing reducibility ⓘ |
| definedOn |
decision problems
ⓘ
sets of natural numbers ⓘ |
| equivalenceClassOf | sets of natural numbers mutually Turing reducible to each other ⓘ |
| equivalenceRelation | mutual Turing reducibility ⓘ |
| field |
computability theory
ⓘ
mathematical logic ⓘ recursion theory ⓘ |
| formalizedIn | second-order arithmetic ⓘ |
| hasBottomElement | degree of computable sets ⓘ |
| hasOpenProblems |
automorphism group of the Turing degrees
ⓘ
exact lattice-theoretic properties of the degrees ⓘ |
| hasOperation | join ⓘ |
| hasProperty |
contains high and low degrees
ⓘ
contains incomparable degrees ⓘ contains minimal degrees ⓘ every nonzero degree bounds a minimal degree ⓘ not a lattice under Turing reducibility ⓘ uncountable set of degrees ⓘ |
| hasStructure | upper semilattice ⓘ |
| hasTopElement | degree of the halting problem ⓘ |
| introducedInField | mid 20th century computability theory ⓘ |
| namedAfter | Alan Turing NERFINISHED ⓘ |
| orderType | partial order under Turing reducibility ⓘ |
| relatedTo |
Medvedev degrees
NERFINISHED
ⓘ
Muchnik degrees NERFINISHED ⓘ Turing jump NERFINISHED ⓘ arithmetical hierarchy NERFINISHED ⓘ degrees of unsolvability ⓘ hyperarithmetical hierarchy ⓘ many-one degrees ⓘ truth-table degrees ⓘ |
| studiedBy |
Alan Turing
NERFINISHED
ⓘ
Emil Post NERFINISHED ⓘ Lachlan NERFINISHED ⓘ Sacks NERFINISHED ⓘ Shore NERFINISHED ⓘ Slaman NERFINISHED ⓘ Stephen Kleene NERFINISHED ⓘ |
| symbol | D_T ⓘ |
| usedFor |
analyzing the structure of unsolvable problems
ⓘ
classifying decision problems by relative computability ⓘ studying relative computability of real numbers ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.