pith. sign in

arxiv: 1311.0724 · v1 · pith:VIX3BMBLnew · submitted 2013-11-04 · 🧮 math.LO

Propagation of partial randomness

classification 🧮 math.LO
keywords f-randomnessrelativeprovepa-degreestrongf-randomimpliespartial
0
0 comments X
read the original 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"of 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.