Universal computably enumerable sets and initial segment prefix-free complexity
From MaRDI portal
Publication:391648
DOI10.1016/j.ic.2013.12.001zbMath1402.03059arXiv1110.1864MaRDI QIDQ391648
Publication date: 10 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.1864
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D25: Recursively (computably) enumerable sets and degrees
03D32: Algorithmic randomness and dimension
Cites Work
- Kolmogorov complexity and computably enumerable sets
- Oscillation in the initial segment complexity of random reals
- Elementary differences between the degrees of unsolvability and degrees of compressibility
- Kolmogorov complexity of initial segments of sequences and arithmetical definability
- Undecidability of the structure of the Solovay degrees of c.e. reals
- Relative randomness and cardinality
- Randomness and reducibility
- The Kolmogorov complexity of random reals
- Analogues of Chaitin's Omega in the computably enumerable sets
- Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Lowness properties and randomness
- Randomness, Computability, and Density
- Lowness notions, measure and domination
- Chaitin's halting probability and the compression of strings using oracles
- Algorithmic Randomness and Complexity
- A minimal pair of 𝐾-degrees
- On initial segment complexity and degrees of randomness
- Non-cupping, measure and computably enumerable splittings
- A Theory of Program Size Formally Identical to Information Theory
- The definition of random sequences
- New Computational Paradigms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item