3 papers
math.LO2022
On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree
David J. Webb
We prove various results connected together by the common thread of computability theory. First, we investigate a new notion of algorithmic dimension, the inescapable dimension, wh…
math.LO2022
Strong Medvedev reducibilities and the KL-randomness problem
Bjørn Kjos-Hanssen, David J. Webb
While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether , Kjos-Hanssen and Webb (2021) sho…
math.LO2021
KL-randomness and effective dimension under strong reducibility
Bjørn Kjos-Hanssen, David J. Webb
We show that the (truth-table) Medvedev degree KLR of Kolmogorov--Loveland randomness coincides with that of Martin Löf randomness, MLR, answering a question of Miyabe. Next, an an…