Kolmogorov complexity of initial segments of sequences and arithmetical definability

DOI10.1016/J.TCS.2011.06.006MaRDI QIDQ719306zbMATH OpenOpenAlexFDO

Authors 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\)-degreesrelative randomnessprefix-free Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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

• scientific article; zbMATH DE number 4068853 (Why is no real title available?)
• A minimal pair of 𝐾-degrees
• Algorithmic randomness and complexity.
• Chaitin's halting probability and the compression of strings using oracles
• Computability and randomness
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Kolmogorov complexity and solovay functions
• Lowness notions, measure and domination
• Lowness properties and randomness
• On initial segment complexity and degrees of randomness
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• On the number of infinite sequences with trivial initial segment complexity
• Oscillation in the initial segment complexity of random reals
• Randomness and Computability: Open Questions
• Randomness, lowness and degrees
• Relative randomness and cardinality
• The Kolmogorov complexity of random reals
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Time-Bounded Kolmogorov Complexity and Solovay Functions

Cited in

(11)

• Universal computably enumerable sets and initial segment prefix-free complexity
• Kolmogorov complexity and computably enumerable sets
• On effectively closed sets of effective strong measure zero
• Resolute sequences in initial segment complexity
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Oreals with \(\Delta_2^0\)-bounded complexity and compressive power
• Nullifying randomness and genericity using symmetric difference
• Mass problems and initial segment complexity
• 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)