Propagation of partial randomness

Annals of Pure and Applied Logic 165 (2):742-758 (2014)
  Copy   BIBTEX

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-degree

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,726

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Luzin’s (n) and randomness reflection.Arno Pauly, Linda Westrick & Liang Yu - 2022 - Journal of Symbolic Logic 87 (2):802-828.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
On partial randomness.Cristian S. Calude, Ludwig Staiger & Sebastiaan A. Terwijn - 2006 - Annals of Pure and Applied Logic 138 (1):20-30.
Randomness notions and reverse mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.

Analytics

Added to PP
2014-01-16

Downloads
36 (#442,498)

6 months
8 (#528,488)

Historical graph of downloads
How can I increase my 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.
On effectively closed sets of effective strong measure zero.Kojiro Higuchi & Takayuki Kihara - 2014 - Annals of Pure and Applied Logic 165 (9):1445-1469.

Add more citations

References found in this work

Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.

View all 19 references / Add more references