Propagation of partial randomness

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

研究成果: Article査読

10 被引用数 (Scopus)

抄録

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.

本文言語English
ページ(範囲)742-758
ページ数17
ジャーナルAnnals of Pure and Applied Logic
165
2
DOI
出版ステータスPublished - 2014 2月
外部発表はい

ASJC Scopus subject areas

  • 論理

フィンガープリント

「Propagation of partial randomness」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル