Complementation in the Turing degrees

DOI10.2307/2275022MaRDI QIDQ3032238zbMATH OpenOpenAlexFDO

Authors Theodore A. Slaman, John Steel

Publication date 1989

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275022

zbMATH Keywords

r.e. degreespair of complements

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Minimal complements for degrees below 0′
• A single minimal complement for the c.e. degrees
• Complementing below recursively enumerable degrees
• Generic degrees are complemented
• Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

Cites work

• On degrees of recursive unsolvability
• The impossibility of finding relative complements for recursively enumerable degrees
• The strong anticupping property for recursively enumerable degrees
• The upper semi-lattice of degrees of recursive unsolvability

Cited in

(24)

• The jump is definable in the structure of the degrees of unsolvability
• Generic degrees are complemented
• Minimal complements for degrees below 0′
• Complementing below recursively enumerable degrees
• Computably enumerable Turing degrees and the meet property
• The minimal complementation property above 0′
• Weak density and cupping in the d-r.e. degrees
• Extensions of embeddings below computably enumerable degrees
• A note on the join property
• Intervals containing exactly one c.e. degree
• The typical Turing degree
• Wtt-degrees and T-degrees of r.e. sets
• scientific article; zbMATH DE number 4051596 (Why is no real title available?)
• Turing Tumble is Turing-complete
• scientific article; zbMATH DE number 3861135 (Why is no real title available?)
• Turing-Completeness Totally Free
• A single minimal complement for the c.e. degrees
• Cupping with random sets
• Properly ?2 minimal degrees and 0? complementation
• Dynamic notions of genericity and array noncomputability
• \(\Sigma_2\) induction and infinite injury priority arguments. III: Prompt sets, minimal pairs and Shoenfield's conjecture
• Strong noncuppability in low computably enumerable degrees
• Generalized high degrees have the complementation property
• Strong Turing degrees for additive BSS RAM's

This page was built for publication: Complementation in the Turing degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3032238)