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: 76,140

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

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.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
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.
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.
Concepts of randomness.Peter Kirschenmann - 1972 - Journal of Philosophical Logic 1 (3/4):395 - 414.

Analytics

Added to PP
2014-01-16

Downloads
25 (#465,168)

6 months
1 (#447,993)

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

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
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.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.

View all 19 references / Add more references