Chaitin's halting probability and the compression of strings using oracles
From MaRDI portal
Publication:3092881
DOI10.1098/rspa.2011.0031zbMath1319.03051OpenAlexW2052274014MaRDI QIDQ3092881
George Barmpalias, Andrew E. M. Lewis
Publication date: 11 October 2011
Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1098/rspa.2011.0031
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)
Related Items
Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Low upper bounds in the LR degrees ⋮ ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Cone avoidance and randomness preservation
Cites Work