Propagation of partial randomness

Kojiro Higuchi, W. M.Phillip Hudelson, Stephen G. Simpson, Keita Yokoyama

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)742-758
Number of pages17
JournalAnnals of Pure and Applied Logic
Volume165
Issue number2
DOIs
Publication statusPublished - 2014 Feb

Keywords

  • Effective Hausdorff dimension
  • Kolmogorov complexity
  • Martin-Löf randomness
  • Models of arithmetic
  • Partial randomness

Fingerprint

Dive into the research topics of 'Propagation of partial randomness'. Together they form a unique fingerprint.

Cite this