Low (computability)

Article summary

In computability theory, a Turing degree [X] is low if its Turing jump [X′] = 0′. A subset S \subset \N is low if its Turing degree is low. In other words, X \subset \N is low iff the halting problem for Turing machines equipped with an oracle for X is exactly as difficult as the halting problem for Turing machines without any oracle. Thus, X being low says that its jump X′ has the least possible degree. Since every set is computable from its jump, all low set are in 0′, but the jump of sets computable in 0′ can bound any degree recursively enumerable in 0′ (Schoenfield Jump Inversion). In general, "lowness properties" are properties of sets that can accurately describe how useless they are at being an oracle for Turing machines, usually meaning that its jumps are as low as logically possible. For example: * A degree [X] is low n iff [X]^{(n)} = 0^{(n)} . * A set X is generalized low if it satisfies [X]' = [X] \or 0' , where \or is the join. * A degree [X] is generalized low n iff [X]^{(n)} = ([X] \or 0')^{(n-1)} . The low basis theorem states that any nonempty \Pi^0_1 class in 2^\omega 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.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.