Propagation of partial randomness

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

zbMATH Keywords

Kolmogorov complexity; models of arithmetic; Martin-Löf randomness; effective Hausdorff dimension; partial randomness

Mathematics Subject Classification ID

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 Π₁⁰ classes in effective randomness
• Almost everywhere domination and superhighness
• Comparing DNR and WWKL
• Π₁⁰ classes with complex elements
• ∏ 0 1 Classes and Degrees of Theories