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-degree
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2013.10.006
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,685
Through your library

References found in this work BETA

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.
[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.

View all 18 references / Add more references

Citations of this work BETA

Cone Avoidance and Randomness Preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
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

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 index
2014-01-16

Total views
18 ( #500,480 of 2,280,831 )

Recent downloads (6 months)
5 ( #249,587 of 2,280,831 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature