On the gap between trivial and nontrivial initial segment prefix-free complexity
From MaRDI portal
Publication:1946508
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
Kolmogorov complexity; \(K\)-triviality; initial segment prefix-free complexity; low for \(\varOmega \)
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