Universal computably enumerable sets and initial segment prefix-free complexity
From MaRDI portal
Publication:391648
DOI10.1016/J.IC.2013.12.001zbMath1402.03059arXiv1110.1864OpenAlexW2963582254MaRDI 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
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Universal computably enumerable sets and initial segment prefix-free complexity
