Elementary differences between the degrees of unsolvability and degrees of compressibility
From MaRDI portal
Publication:636334
DOI10.1016/J.APAL.2009.11.004zbMATH Open1227.03054OpenAlexW2072474105MaRDI QIDQ636334FDOQ636334
Authors: George Barmpalias 
Publication date: 26 August 2011
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.2009.11.004
Recommendations
Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Cites Work
- Title not available (Why is that?)
- A formal theory of inductive inference. Part I
- Computability and randomness
- Title not available (Why is that?)
- A Theory of Program Size Formally Identical to Information Theory
- Lowness properties and randomness
- Lowness notions, measure and domination
- Randomness, lowness and degrees
- Almost everywhere domination and superhighness
- Low for random reals and positive-measure domination
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- Relative randomness and cardinality
- Non-cupping, measure and computably enumerable splittings
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- A minimal degree less than 0’
- A minimal pair of recursively enumerable degrees
- Tracing and domination in the Turing degrees
Cited In (5)
- Universal computably enumerable sets and initial segment prefix-free complexity
- Low upper bounds in the LR degrees
- Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Kolmogorov complexity of initial segments of sequences and arithmetical definability
This page was built for publication: Elementary differences between the degrees of unsolvability and degrees of compressibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q636334)
