On the gap between trivial and nontrivial initial segment prefix-free complexity

DOI10.1007/s00224-012-9400-9zbMath1261.68075MaRDI QIDQ1946508

Martijn Baartse, George Barmpalias

Publication date: 15 April 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9400-9

zbMATH Keywords

Kolmogorov complexity; \(K\)-triviality; initial segment prefix-free complexity; low for \(\varOmega \)

Mathematics Subject Classification ID

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

Related Items

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, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Depth, Highness and DNR Degrees, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER

Cites Work

• Unnamed Item
• Unnamed Item
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• On the number of infinite sequences with trivial initial segment complexity
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Turing degrees of reals of positive effective packing dimension
• Relative randomness and cardinality
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Information-theoretic characterizations of recursive infinite strings
• Compactness arguments with effectively closed sets for the study of relative randomness
• Algorithmic Randomness and Complexity
• A minimal pair of 𝐾-degrees
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Measures and their random reals
• Turing incomparability in Scott sets
• Using random sets as oracles