In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′, which is the least possible degree in terms of Turing reducibility for the jump of a set. Since every set is computable from its jump, any low set is computable in 0′. A set is low if it has low degree. More generally, a set X is generalized low if it satisfies X′ ≡T X + 0′.

PropertyValue
dbpprop:abstract
  • In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′, which is the least possible degree in terms of Turing reducibility for the jump of a set. Since every set is computable from its jump, any low set is computable in 0′. A set is low if it has low degree. More generally, a set X is generalized low if it satisfies X′ ≡T X + 0′.
dbpprop:hasPhotoCollection
rdfs:comment
  • In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′, which is the least possible degree in terms of Turing reducibility for the jump of a set. Since every set is computable from its jump, any low set is computable in 0′. A set is low if it has low degree. More generally, a set X is generalized low if it satisfies X′ ≡T X + 0′.
rdfs:label
  • Low (computability)
owl:sameAs
skos:subject
foaf:page