On the complexity of random strings
From MaRDI portal
Publication:4593915
DOI10.1007/3-540-60922-9_3zbMath1379.68187MaRDI QIDQ4593915
No author found.
Publication date: 16 November 2017
Published in: STACS 96 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60922-9_3
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D32: Algorithmic randomness and dimension
Related Items
Kolmogorov entropy in the context of computability theory, Index sets and universal numberings, An excursion to the Kolmogorov random strings, Things that can be made into themselves, On the computational power of random strings, On the Turing degrees of minimal index sets, What can be efficiently reduced to the Kolmogorov-random strings?, Randomness, Computation and Mathematics, The Complexity of Complexity, Bounded Immunity and Btt-Reductions