Cupping with random sets

DOI10.1090/S0002-9939-2014-11997-6MaRDI QIDQ3189590zbMATH OpenFDO

Authors Adam R. Day, Joseph S. Miller

Publication date 12 September 2014

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.1603

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We prove that a set is K-trivial if and only if it is not weakly ML-cuppable. Further, we show that a set below zero jump is K-trivial if and only if it is not ML-cuppable. These results settle a question of Kuv{c}era, who introduced both cuppability notions.

Recommendations

• Two more characterizations of \(K\)-triviality
• Strong jump-traceability. I: The computably enumerable case
• Non-cupping and randomness
• Cuppability of simple and hypersimple sets
• Strong jump-traceability. II: K-triviality

Cites work

• Algorithmic randomness and complexity.
• Almost everywhere domination and superhighness
• Complementation in the Turing degrees
• Computability and randomness
• Degrees joining to 0′
• Degrees of Unsolvability. (AM-55)
• Difference randomness
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 4051596 (Why is no real title available?)
• Lowness for the class of random sets
• Lowness notions, measure and domination
• Lowness properties and randomness
• Non-cupping and randomness
• Randomness and Computability: Open Questions
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• The Denjoy alternative for computable functions
• Using random sets as oracles

Cited in

(9)

• Two more characterizations of \(K\)-triviality
• Lowness for difference tests
• Cuppability of simple and hypersimple sets
• Lebesgue density and \(\Pi _1^0\) classes
• Non-cupping and randomness
• Higher randomness and genericity
• scientific article; zbMATH DE number 7204368 (Why is no real title available?)
• Using almost-everywhere theorems from analysis to study randomness
• Random non-cupping revisited

This page was built for publication: Cupping with random sets

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