Propagation of partial randomness
Annals of Pure and Applied Logic 165 (2):742-758 (2014)
Abstract
Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degreeDOI
10.1016/j.apal.2013.10.006
My notes
Similar books and articles
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Fixed point theorems on partial randomness.Kohtaro Tadaki - 2012 - Annals of Pure and Applied Logic 163 (7):763-774.
Reviewed Work(s): Lowness properties and randomness. Advances in Mathematics, vol. 197 by André Nies; Lowness for the class of Schnorr random reals. SIAM Journal on Computing, vol. 35 by Bjørn Kjos-Hanssen; André Nies; Frank Stephan; Lowness for Kurtz randomness. The Journal of Symbolic Logic, vol. 74 by Noam Greenberg; Joseph S. Miller; Randomness and lowness notions via open covers. Annals of Pure and Applied Logic, vol. 163 by Laurent Bienvenu; Joseph S. Miller; Relativizations of randomness and genericity notions. The Bulletin of the London Mathematical Society, vol. 43 by Johanna N. Y. Franklin; Frank Stephan; Liang Yu; Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 by George Barmpalias; Joseph S. Miller; André Nies. [REVIEW]Johanna N. Y. Franklin - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
On partial randomness.Cristian S. Calude, Ludwig Staiger & Sebastiaan A. Terwijn - 2006 - Annals of Pure and Applied Logic 138 (1):20-30.
Mass problems and almost everywhere domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.
Randomness Through Computation: Some Answers, More Questions.Hector Zenil (ed.) - 2011 - World Scientific.
Concepts of randomness.Peter Kirschenmann - 1972 - Journal of Philosophical Logic 1 (3/4):395 - 414.
Randomness and perceived-randomness in evolutionary biology.William C. Wimsatt - 1980 - Synthese 43 (2):287 - 329.
Analytics
Added to PP
2014-01-16
Downloads
25 (#465,168)
6 months
1 (#447,993)
2014-01-16
Downloads
25 (#465,168)
6 months
1 (#447,993)
Historical graph of downloads
Citations of this work
Cone avoidance and randomness preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
Degrees of randomized computability.Rupert Hölzl & Christopher P. Porter - 2022 - Bulletin of Symbolic Logic 28 (1):27-70.
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.
On effectively closed sets of effective strong measure zero.Kojiro Higuchi & Takayuki Kihara - 2014 - Annals of Pure and Applied Logic 165 (9):1445-1469.
The axiomatic power of Kolmogorov complexity.Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux & Stijn Vermeeren - 2014 - Annals of Pure and Applied Logic 165 (9):1380-1402.
References found in this work
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.