\(\Pi_1^0 \) classes, LR degrees and Turing degrees
From MaRDI portal
Publication:958483
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
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 Π10 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