ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER

DOI10.1017/jsl.2015.68zbMath1364.03061arXiv1410.3615OpenAlexW2520901609MaRDI QIDQ2976366

Ian Herbert

Publication date: 28 April 2017

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.3615

zbMATH Keywords

Kolmogorov complexityalgorithmic randomness\(K\)-triviality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Information-theoretic characterizations of recursive infinite strings
• Randomness and reducibility
• The Kolmogorov complexity of random reals
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Lowness properties and randomness
• Chaitin's halting probability and the compression of strings using oracles

This page was built for publication: ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER