Propagation of partial randomness
From MaRDI portal
Publication:386647
DOI10.1016/j.apal.2013.10.006zbMath1329.03078arXiv1311.0724MaRDI QIDQ386647
Keita Yokoyama, Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson
Publication date: 10 December 2013
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.0724
Kolmogorov complexity; models of arithmetic; Martin-Löf randomness; effective Hausdorff dimension; partial randomness
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D32: Algorithmic randomness and dimension
Related Items
A computable analysis of majorizing martingales, DEGREES OF RANDOMIZED COMPUTABILITY, Solovay reducibility and continuity, Randomness for computable measures and initial segment complexity, Energy randomness, Highness properties close to PA completeness, Cone avoidance and randomness preservation, The axiomatic power of Kolmogorov complexity, On effectively closed sets of effective strong measure zero, Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
- A nonstandard counterpart of WWKL
- Mass problems associated with effectively closed sets
- Effectively closed sets of measures and randomness
- On interpreting Chaitin's incompleteness theorem
- A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
- On partial randomness
- Lowness notions, measure and domination
- Effective Strong Nullness and Effectively Closed Sets
- MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
- Kolmogorov complexity and the Recursion Theorem
- Algorithmic Randomness and Complexity
- Mass Problems and Randomness
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- On initial segment complexity and degrees of randomness
- Mass Problems and Measure-Theoretic Regularity
- Information-Theoretic Limitations of Formal Systems
- Relations between varieties of kolmogorov complexities
- The importance of Π10 classes in effective randomness
- Almost everywhere domination and superhighness
- Comparing DNR and WWKL
- Π10 classes with complex elements
- ∏ 0 1 Classes and Degrees of Theories