Switch to: References

Add citations

You must login to add citations.
  1. Intrinsic smallness.Justin Miller - 2021 - Journal of Symbolic Logic 86 (2):558-576.
    Recent work in computability theory has focused on various notions of asymptotic computability, which capture the idea of a set being “almost computable.” One potentially upsetting result is that all four notions of asymptotic computability admit “almost computable” sets in every Turing degree via coding tricks, contradicting the notion that “almost computable” sets should be computationally close to the computable sets. In response, Astor introduced the notion of intrinsic density: a set has defined intrinsic density if its image under any (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Nonexistence of minimal pairs for generic computability.Gregory Igusa - 2013 - Journal of Symbolic Logic 78 (2):511-522.
    A generic computation of a subset $A$ of $\mathbb{N}$ consists of a computation that correctly computes most of the bits of $A$, and never incorrectly computes any bits of $A$, but which does not necessarily give an answer for every input. The motivation for this concept comes from group theory and complexity theory, but the purely recursion theoretic analysis proves to be interesting, and often counterintuitive. The primary result of this paper is that there are no minimal pairs for generic (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Coarse reducibility and algorithmic randomness.Denis R. Hirschfeldt, Carl G. Jockusch, Rutger Kuyper & Paul E. Schupp - 2016 - Journal of Symbolic Logic 81 (3):1028-1046.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Asymptotic density and the Ershov hierarchy.Rod Downey, Carl Jockusch, Timothy H. McNicholl & Paul Schupp - 2015 - Mathematical Logic Quarterly 61 (3):189-195.
    We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • From Bi-Immunity to Absolute Undecidability.Laurent Bienvenu, Adam R. Day & Rupert Hölzl - 2009 - Journal of Symbolic Logic 78 (4):1218-1228.
  • The computational content of intrinsic density.Eric P. Astor - 2018 - Journal of Symbolic Logic 83 (2):817-828.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The degrees of bi-hyperhyperimmune sets.Uri Andrews, Peter Gerdes & Joseph S. Miller - 2014 - Annals of Pure and Applied Logic 165 (3):803-811.
    We study the degrees of bi-hyperhyperimmune sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any ∆02 function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation