1.  21
    Computing K-Trivial Sets by Incomplete Random Sets.Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies & Dan Turetsky - 2014 - Bulletin of Symbolic Logic 20 (1):80-90.
    EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.
    Direct download (3 more)  
    Export citation  
    Bookmark   5 citations  
  2.  23
    The Computable Lipschitz Degrees of Computably Enumerable Sets Are Not Dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
    The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   4 citations  
  3.  45
    Indifferent Sets for Genericity.Adam R. Day - 2013 - Journal of Symbolic Logic 78 (1):113-138.
    This paper investigates indifferent sets for comeager classes in Cantor space focusing of the class of all 1-generic sets and the class of all weakly 1-generic sets. Jockusch and Posner showed that there exist 1-generic sets that have indifferent sets [10]. Figueira, Miller and Nies have studied indifferent sets for randomness and other notions [7]. We show that any comeager class in Cantor space contains a comeager class with a universal indifferent set. A forcing construction is used to show that (...)
    Direct download (5 more)  
    Export citation  
    Bookmark   1 citation  
  4.  11
    Independence, Relative Randomness, and PA Degrees.Adam R. Day & Jan Reimann - 2014 - Notre Dame Journal of Formal Logic 55 (1):1-10.
  5.  8
    From Bi-Immunity to Absolute Undecidability.Laurent Bienvenu, Adam R. Day & Rupert Hölzl - 2009 - Journal of Symbolic Logic 78 (4):1218-1228.
  6.  9
    Jump Operations for Borel Graphs.Adam R. Day & Andrew S. Marks - 2018 - Journal of Symbolic Logic 83 (1):13-28.
    Direct download (2 more)  
    Export citation  
  7.  12
    On the Computational Power of Random Strings.Adam R. Day - 2009 - Annals of Pure and Applied Logic 160 (2):214-228.
    There are two fundamental computably enumerable sets associated with any Kolmogorov complexity measure. These are the set of non-random strings and the overgraph. This paper investigates the computational power of these sets. It follows work done by Kummer, Muchnik and Positselsky, and Allender and co-authors. Muchnik and Positselsky asked whether there exists an optimal monotone machine whose overgraph is not tt-complete. This paper answers this question in the negative by proving that the overgraph of any optimal monotone machine, or any (...)
    Direct download (5 more)  
    Export citation