12 found
Order:
  1.  20
    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.  13
    On the Interplay Between Effective Notions of Randomness and Genericity.Laurent Bienvenu & Christopher P. Porter - 2019 - Journal of Symbolic Logic 84 (1):393-407.
    In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence. We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence. Moreover, we prove that for every (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  8
    Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
    We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  4.  13
    Continuous Higher Randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
    We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see text]-trivial sets by higher (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  5.  3
    Randomness and Lowness Notions Via Open Covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
  6.  11
    Characterizing Lowness for Demuth Randomness.Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies & Dan Turetsky - 2014 - Journal of Symbolic Logic 79 (2):526-560.
    We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  12
    Constructive Equivalence Relations on Computable Probability Measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
    A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  8
    From Bi-Immunity to Absolute Undecidability.Laurent Bienvenu, Adam R. Day & Rupert Hölzl - 2009 - Journal of Symbolic Logic 78 (4):1218-1228.
  9.  10
    University of California at Berkeley Berkeley, CA, USA March 24–27, 2011.G. Aldo Antonelli, Laurent Bienvenu, Lou van den Dries, Deirdre Haskell, Justin Moore, Christian Rosendal Uic, Neil Thapen & Simon Thomas - 2012 - Bulletin of Symbolic Logic 18 (2).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  11
    Deep Classes.Laurent Bienvenu & Christopher P. Porter - 2016 - Bulletin of Symbolic Logic 22 (2):249-286.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  20
    Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
    A semimeasure is a generalization of a probability measure obtained by relaxing the additivity requirement to superadditivity. We introduce and study several randomness notions for left-c.e. semimeasures, a natural class of effectively approximable semimeasures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semimeasures is the most compelling, as it best reflects Martin-Löf randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive answer to which would (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  12.  11
    Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010, Xxviii + 855 Pp. [REVIEW]Laurent Bienvenu - 2012 - Bulletin of Symbolic Logic 18 (1):126-128.