Low (computability)
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.
Wikipage disambiguates
Link from a Wikipage to another Wikipage
primaryTopic
Low (computability)
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.
has abstract
In computability theory, a Tur ...... strength of Ramsey's theorem.
@en
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
711,626,350
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
In computability theory, a Tur ...... ibility for the jump of a set.
@en
label
Low (computability)
@en