Kolmogorov complexity of initial segments of sequences and arithmetical definability
From MaRDI portal
Publication:719306
DOI10.1016/j.tcs.2011.06.006zbMath1235.68087MaRDI QIDQ719306
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.006
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
Related Items
Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, Universal computably enumerable sets and initial segment prefix-free complexity, Solovay functions and their applications in algorithmic randomness, On the number of infinite sequences with trivial initial segment complexity, On the gap between trivial and nontrivial initial segment prefix-free complexity, Nullifying randomness and genericity using symmetric difference, On effectively closed sets of effective strong measure zero, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER
Cites Work
- Unnamed Item
- Unnamed Item
- Oscillation in the initial segment complexity of random reals
- Elementary differences between the degrees of unsolvability and degrees of compressibility
- On the number of infinite sequences with trivial initial segment complexity
- Relative randomness and cardinality
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
- The Kolmogorov complexity of random reals
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Lowness properties and randomness
- Lowness notions, measure and domination
- Chaitin's halting probability and the compression of strings using oracles
- Kolmogorov complexity and the Recursion Theorem
- Algorithmic Randomness and Complexity
- Time-Bounded Kolmogorov Complexity and Solovay Functions
- A minimal pair of 𝐾-degrees
- Randomness and Computability: Open Questions
- Randomness, lowness and degrees
- On initial segment complexity and degrees of randomness
- Kolmogorov Complexity and Solovay Functions