Low (computability) (original) (raw)
In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable in 0′ can bound any degree r.e. in 0′ (Schoenfield Jump Inversion). X being low says that its jump X′ has the least possible degree in terms of Turing reducibility for the jump of a set. There are various related properties to low degrees:
| Property | Value |
|---|---|
| dbo:abstract | In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable in 0′ can bound any degree r.e. in 0′ (Schoenfield Jump Inversion). X being low says that its jump X′ has the least possible degree in terms of Turing reducibility for the jump of a set. There are various related properties to low degrees: * A degree is lown if its n'th jump is the n'th jump of 0. * A set X is generalized low if it satisfies X′ ≡T X + 0′, that is: if its jump has the lowest degree possible. * A degree d is generalized low n if its n'th jump is the (n-1)'st jump of the join of d with 0′. More generally, properties of sets which describe their being computationally weak (when used as a Turing oracle) are referred to under the umbrella term lowness properties. By the Low basis theorem of Jockusch and Soare, any nonempty class in contains a set of low degree. This implies that, although low sets are computationally weak, they can still accomplish such feats as computing a completion of Peano Arithmetic. In practice, this allows a restriction on the computational power of objects needed for recursion theoretic constructions: for example, those used in the analyzing the proof-theoretic strength of Ramsey's theorem. (en) |
| dbo:wikiPageID | 9767106 (xsd:integer) |
| dbo:wikiPageLength | 2696 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121018996 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Reverse_mathematics dbr:Low_Basis_Theorem dbr:Low_basis_theorem dbr:High_(computability) dbc:Computability_theory dbr:Ramsey's_theorem dbr:Turing_jump dbr:PA_degree dbr:Turing_degree dbr:Turing_reducibility dbr:Springer-Verlag dbr:Recursion_theory |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:Mathlogic-stub |
| dcterms:subject | dbc:Computability_theory |
| rdfs:comment | In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable in 0′ can bound any degree r.e. in 0′ (Schoenfield Jump Inversion). X being low says that its jump X′ has the least possible degree in terms of Turing reducibility for the jump of a set. There are various related properties to low degrees: (en) |
| rdfs:label | Low (computability) (en) |
| owl:sameAs | freebase:Low (computability) wikidata:Low (computability) https://global.dbpedia.org/id/4qy1r |
| prov:wasDerivedFrom | wikipedia-en:Low_(computability)?oldid=1121018996&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Low_(computability) |
| is dbo:wikiPageDisambiguates of | dbr:Low |
| is dbo:wikiPageWikiLink of | dbr:Reverse_mathematics dbr:Kőnig's_lemma dbr:Generic_property dbr:Low_basis_theorem dbr:High_(computability) dbr:Low dbr:Low_(complexity) dbr:Turing_degree |
| is foaf:primaryTopic of | wikipedia-en:Low_(computability) |