Switch to: Citations

Add references

You must login to add references.
  1. Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
    The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts (...)
    Download  
     
    Export citation  
     
    Bookmark   22 citations  
  • A Perfect Set of Reals with Finite Self-Information.Ian Herbert - 2013 - Journal of Symbolic Logic 78 (4):1229-1246.
    We examine a definition of the mutual information of two reals proposed by Levin in [5]. The mutual information iswhereK is the prefix-free Kolmogorov complexity. A realAis said to have finite self-information ifI is finite. We give a construction for a perfect Π10class of reals with this property, which settles some open questions posed by Hirschfeldt and Weber. The construction produces a perfect set of reals withK≤+KA+f for any given Δ20fwith a particularly nice approximation and for a specific choice of (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
    Let ω be the set of natural numbers. For functions f, g: ω → ω, we say f is dominated by g if f < g for all but finitely many n ∈ ω. We consider the standard “fair coin” probability measure on the space 2ω of in-finite sequences of 0's and 1's. A Turing oracle B is said to be almost everywhere dominating if, for measure 1 many X ∈ 2ω, each function which is Turing computable from X is (...)
    Download  
     
    Export citation  
     
    Bookmark   23 citations