\(\Pi_1^0 \) classes, LR degrees and Turing degrees

DOI10.1016/j.apal.2008.06.004zbMath1156.03040OpenAlexW2014288728MaRDI QIDQ958483

Andrew E. M. Lewis, George Barmpalias, Frank Stephan

Publication date: 5 December 2008

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2008.06.004

zbMATH Keywords

Turing degree\(\Pi_1^0\) classrelative randomnessLR degree

Mathematics Subject Classification ID

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

Related Items

Randomness notions and partial relativization, Characterizing strong randomness via Martin-Löf randomness, Low upper bounds in the LR degrees, On the gap between trivial and nontrivial initial segment prefix-free complexity, Elementary differences between the degrees of unsolvability and degrees of compressibility, The importance of Π₁⁰ classes in effective randomness, Reductions between types of numberings

Cites Work

• Unnamed Item
• Unnamed Item
• Randomness and universal machines
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• The ibT degrees of computably enumerable sets are not dense
• Lowness properties and randomness
• Lowness notions, measure and domination
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness and Computability: Open Questions
• Randomness, lowness and degrees
• A minimal degree not realizing least possible jump
• Recursively enumerable sets and degrees
• A Cappable Almost Everywhere Dominating Computably Enumerable Degree
• Almost everywhere domination and superhighness
• Low for random reals and positive-measure domination
• Turing incomparability in Scott sets