On the computational power of C-random strings

DOI10.1007/978-3-031-95908-0_23MaRDI QIDQ6897642zbMATH OpenFDO

Authors Alexey Milovanov

Publication date 19 November 2025

Full work available at URL https://doi.org/10.1007/978-3-031-95908-0_23

zbMATH Keywords

computabilitycomputation complexityKolmogorov complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• Kolmogorov Complexity and Algorithmic Randomness
• Kolmogorov entropy in the context of computability theory
• Limits on the computational power of random strings
• On the complexity of random strings
• Power from Random Strings
• Random strings and truth-table degrees of Turing complete c.e. sets
• Some games on Turing machines and power from random strings
• Unexpected hardness results for Kolmogorov complexity under uniform reductions
• What can be efficiently reduced to the Kolmogorov-random strings?

This page was built for publication: On the computational power of C-random strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6897642)