Order:
  1.  2
    Lebesgue Density and Classes.Mushfeq Khan - 2016 - Journal of Symbolic Logic 81 (1):80-95.
    Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: thepositive density pointswith respect toeffectively closed sets of reals, and a proper subclass, thedensity-one points. Bienvenu, Hölzl, Miller, and Nies have shown that the Martin-Löf random positive density points are exactly the ones that do not compute the halting problem. Treating this theorem (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  2.  6
    The Strength of the Grätzer-Schmidt Theorem.Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen, William A. Lampe, Paul Kim Long V. Nguyen & Richard A. Shore - 2016 - Archive for Mathematical Logic 55 (5-6):687-704.
    No categories
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  3.  17
    Shift-Complex Sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.
    A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment $\sigma$ has prefix-free Kolmogorov complexity $K$ at least $|\sigma| - c$, for some constant $c \in \omega$. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a sequence be uniformly (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark