Strong Medvedev reducibilities and the KL-randomness problem

DOI10.1007/978-3-031-08740-0_13MaRDI QIDQ2104264zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, David J. Webb

Publication date 7 December 2022

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

zbMATH Keywords

Martin-Löf randomnessMedvedev reducibilitytruth-table reducibility

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• KL-randomness and effective dimension under strong reducibility
• Randomized versions of Mazur lemma and Krein-Šmulian theorem
• scientific article; zbMATH DE number 3995648
• Reducibilities relating to Schnorr randomness
• Coarse reducibility and algorithmic randomness
• On completeness under random reductions
• Randomization of Sharkovskii-type theorems
• Strong reductions in effective randomness
• Randomness and Solovay degrees
• Strong jump-traceability and Demuth randomness

Cites work

• A van Lambalgen theorem for Demuth randomness
• Algorithmic randomness and complexity.
• Computability and Randomness
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• scientific article; zbMATH DE number 1390013 (Why is no real title available?)
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• KL-randomness and effective dimension under strong reducibility
• Kolmogorov-Loveland randomness and stochasticity

Cited in

(1)

• Strong Medvedev reducibilities and the KL-randomness problem

This page was built for publication: Strong Medvedev reducibilities and the KL-randomness problem

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