Switch to: References

Add citations

You must login to add citations.
  1. Randomness via infinite computation and effective descriptive set theory.Merlin Carl & Philipp Schlicht - 2018 - Journal of Symbolic Logic 83 (2):766-789.
    We study randomness beyond${\rm{\Pi }}_1^1$-randomness and its Martin-Löf type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between${\rm{\Pi }}_1^1$and${\rm{\Sigma }}_2^1$that is given by the infinite time Turing machines introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randomness notions defined via effective descriptive set theory such as${\rm{\Pi (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • (1 other version)Luzin’s (n) and randomness reflection.Arno Pauly, Linda Westrick & Liang Yu - 2020 - Journal of Symbolic Logic:1-27.
    We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f$ is R-random, then x is R-random as well. If additionally f is known to have (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • (1 other version)Luzin’s (n) and randomness reflection.Arno Pauly, Linda Westrick & Liang Yu - 2022 - Journal of Symbolic Logic 87 (2):802-828.
    We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f$ is R-random, then x is R-random as well. If additionally f is known to have (...)
    Download  
     
    Export citation  
     
    Bookmark