6 found
Order:
See also
Christopher Porter
Drake University
  1.  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  
  2.  17
    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  
  3.  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  
  4.  11
    Deep Classes.Laurent Bienvenu & Christopher P. Porter - 2016 - Bulletin of Symbolic Logic 22 (2):249-286.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  10
    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  
  6.  4
    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