On the gap between trivial and nontrivial initial segment prefix-free complexity
From MaRDI portal
Publication:1946508
DOI10.1007/s00224-012-9400-9zbMath1261.68075OpenAlexW2040912355MaRDI 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
Related Items (6)
Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Depth, Highness and DNR Degrees ⋮ ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER ⋮ On the number of infinite sequences with trivial initial segment complexity ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability
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
This page was built for publication: On the gap between trivial and nontrivial initial segment prefix-free complexity
