4 papers
A Note on Lowness for -Immunity
David J. Webb
We show that the only degree which cannot co-enumerate a non-trivial -immune real is , resolving a conjecture of the author. The main ingredient is that if a real…
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…
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…
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…