Switch to: References

Add citations

You must login to add citations.
  1. Levels of Uniformity.Rutger Kuyper - 2019 - Notre Dame Journal of Formal Logic 60 (1):119-138.
    We introduce a hierarchy of degree structures between the Medvedev and Muchnik lattices which allow varying amounts of nonuniformity. We use these structures to introduce the notion of the uniformity of a Muchnik reduction, which expresses how uniform a reduction is. We study this notion for several well-known reductions from algorithmic randomness. Furthermore, since our new structures are Brouwer algebras, we study their propositional theories. Finally, we study if our new structures are elementarily equivalent to each other.
    Download  
     
    Export citation  
     
    Bookmark  
  • Inside the Muchnik degrees II: The degree structures induced by the arithmetical hierarchy of countably continuous functions.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (6):1201-1241.
    It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • A hierarchy of immunity and density for sets of reals.Takayuki Kihara - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 384--394.
    Download  
     
    Export citation  
     
    Bookmark