On the complexity of random strings

DOI10.1007/3-540-60922-9_3zbMath1379.68187OpenAlexW109076699MaRDI 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

Mathematics Subject Classification ID

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

Related Items (10)

Randomness, Computation and Mathematics ⋮ On the Turing degrees of minimal index sets ⋮ An excursion to the Kolmogorov random strings ⋮ The Complexity of Complexity ⋮ Things that can be made into themselves ⋮ On the computational power of random strings ⋮ Index sets and universal numberings ⋮ Kolmogorov entropy in the context of computability theory ⋮ What can be efficiently reduced to the Kolmogorov-random strings? ⋮ Bounded Immunity and Btt-Reductions

This page was built for publication: On the complexity of random strings