Elementary differences between the degrees of unsolvability and degrees of compressibility
From MaRDI portal
Publication:636334
DOI10.1016/j.apal.2009.11.004zbMath1227.03054OpenAlexW2072474105MaRDI QIDQ636334
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
Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (4)
Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Low upper bounds in the LR degrees ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tracing and domination in the Turing degrees
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- Relative randomness and cardinality
- Lowness properties and randomness
- Lowness notions, measure and domination
- A minimal degree less than 0’
- Randomness, lowness and degrees
- Non-cupping, measure and computably enumerable splittings
- A Theory of Program Size Formally Identical to Information Theory
- Almost everywhere domination and superhighness
- Low for random reals and positive-measure domination
- A minimal pair of recursively enumerable degrees
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- A formal theory of inductive inference. Part I
This page was built for publication: Elementary differences between the degrees of unsolvability and degrees of compressibility