7 found
Order:
  1.  26
    Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
    Osvald Demuth studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  21
    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.  25
    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 (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  18
    Deep classes.Laurent Bienvenu & Christopher P. Porter - 2016 - Bulletin of Symbolic Logic 22 (2):249-286.
    A set of infinite binary sequences ${\cal C} \subseteq 2$ℕ is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of ${\rm{\Pi }}_1^0 $ classes. In this paper, we introduce the notion of depth for ${\rm{\Pi }}_1^0 $ classes, which is a stronger form of negligibility. Whereas a negligible ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  10
    Degrees of randomized computability.Rupert Hölzl & Christopher P. Porter - 2022 - Bulletin of Symbolic Logic 28 (1):27-70.
    In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  6
    Rank and randomness.Rupert Hölzl & Christopher P. Porter - 2019 - Journal of Symbolic Logic 84 (4):1527-1543.
    We show that for each computable ordinal $\alpha > 0$ it is possible to find in each Martin-Löf random ${\rm{\Delta }}_2^0 $ degree a sequence R of Cantor-Bendixson rank α, while ensuring that the sequences that inductively witness R’s rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  21
    Randomness for computable measures and initial segment complexity.Rupert Hölzl & Christopher P. Porter - 2017 - Annals of Pure and Applied Logic 168 (4):860-886.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark