Kolmogorov complexity of initial segments of sequences and arithmetical definability

DOI10.1016/j.tcs.2011.06.006zbMath1235.68087MaRDI QIDQ719306

George Barmpalias, C. S. Vlek

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

zbMATH Keywords

arithmetical complexity; \(K\)-degrees; relative randomness; prefix-free Kolmogorov complexity

Mathematics Subject Classification ID

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