Propagation of partial randomness
Propagation of partial randomness
复制标题
DOI：
10.1016/j.apal.2013.10.006
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Kojiro Higuchi;W. M. P. Hudelson;S. G. Simpson;K. Yokoyama
中科院分区：
文献类型：
--
作者：
Kojiro Higuchi;W. M. P. Hudelson;S. G. Simpson;K. Yokoyama
令 f 为从 0 和 1 的有限序列到实数的可计算函数。我们证明，强 f 随机性意味着相对于 PA 度而言，强 f 随机性。我们还证明：如果 X 是强 f 随机的，并且图灵可约简到 Y，其中 Y 相对于 Z 是 Martin-Löf 随机的，那么 X 相对于 Z 是强 f 随机的。此外，我们还证明了其他部分随机性概念的类似传播结果，包括非 K-平凡性和自复杂性。我们证明，相对于 PA 度的 f 随机性意味着强 f 随机性，因此 f 随机性并不意味着相对于 PA 度的 f 随机性。
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.