Kolmogorov complexity of initial segments of sequences and arithmetical definability
From MaRDI portal
Publication:719306
DOI10.1016/J.TCS.2011.06.006zbMATH Open1235.68087OpenAlexW2034673847MaRDI QIDQ719306FDOQ719306
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
Recommendations
- On initial segment complexity and degrees of randomness
- Kolmogorov complexity and computably enumerable sets
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Randomness for computable measures and initial segment complexity
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
Cites Work
- Algorithmic Randomness and Complexity
- Computability and randomness
- Lowness properties and randomness
- Lowness notions, measure and domination
- On initial segment complexity and degrees of randomness
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
- Randomness and Computability: Open Questions
- Randomness, lowness and degrees
- Kolmogorov Complexity and Solovay Functions
- Relative randomness and cardinality
- Kolmogorov complexity and the Recursion Theorem
- The Kolmogorov complexity of random reals
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Chaitin's halting probability and the compression of strings using oracles
- A minimal pair of 𝐾-degrees
- Oscillation in the initial segment complexity of random reals
- Elementary differences between the degrees of unsolvability and degrees of compressibility
- Title not available (Why is that?)
- Time-Bounded Kolmogorov Complexity and Solovay Functions
- On the number of infinite sequences with trivial initial segment complexity
Cited In (8)
- Universal computably enumerable sets and initial segment prefix-free complexity
- On effectively closed sets of effective strong measure zero
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Nullifying randomness and genericity using symmetric difference
- ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- Solovay functions and their applications in algorithmic randomness
- On the number of infinite sequences with trivial initial segment complexity
This page was built for publication: Kolmogorov complexity of initial segments of sequences and arithmetical definability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719306)
